Problem #12. What is the value of the first triangle number to have over five hundred divisors?

번역: 500개가 넘는 (양의) 약수를 가진 첫번째 triangle number는 ?

먼저 triangle number의 수열은 아래와 같이 구할 수 있다.

Version1. 정의에 가까운 가장 직관적인 방식..

let triangle_numbers =

    let rec triangle_number =

        function 0 -> 1 | n -> (n + 1 + triangle_number (n-1))

    Seq.init_infinite triangle_number



Version 2. Recursive call을 제거..

let triangle_numbers = Seq.unfold (fun (n, i) -> Some(n, (n+i, i+1))) (1, 2)



Version 3. 최적화.

let triangle_numbers = Seq.init_infinite (fun n -> (n+2)*(n+1) / 2)



triangle number의 수열을 구했으니 답을 구하면..

let factorize n =

    let rec factorize_horse n factor count result =

        if (n <= 1) then

            count::result

        else

            match (n % factor) with

            | 0 -> (factorize_horse (n/factor) factor (count+1) result)

            | _ -> (factorize_horse n (factor+1) 0 (count::result))          

    factorize_horse n 2 0 []

        |> List.filter (fun x -> x<>0)

 

let factor_count n =

    factorize n

        |> List.map (fun x -> x+1 )

        |> List.fold_left (*) 1

 

triangle_numbers

    |> Seq.filter (fun x -> 500 < (factor_count x))

    |> Seq.hd

    |> printfn "Problem #12 = %d"



약수의 개수를 빨리 구하려고, 소인수 분해를 하였다.
약수 개수를 구하기 위해 모든 약수가 무엇인지 다 파악한다면..
얼마나 느릴지는 장담할 수 없음. ㅋ



Posted by U∙Seung