notebook.community

Edit and run

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?



In [2]:

    
// attempt 1 - abuse Seq.unfold to work an infinite sequence of (number, triangle) until 
//             we hit the right number of factors
let isFactor x y = (x % y = 0)

let countFactors n = 
    [  1 .. n ]
    |> List.filter (fun x -> isFactor n x)
    |> List.length
    
let minFactors = 5

let baseNum =
    Seq.unfold (fun state -> 
        if ((countFactors (snd state) > minFactors)) 
        then None 
        else Some((fst state, snd state), ((fst state)+1, 1+ (snd state + fst state)))
    ) (1,1)
    |> Seq.map fst
    |> Seq.toArray
    |> Array.last   

[1 .. (1+baseNum)]
|> List.sum









    Out[2]:





28



In [28]:

    
// attempt 2 - use recursion, threading the index and current triangle number to each call.
//             less memory intensive, shouldn't be too terrible on stack (tail recursion)
//             but the "countFactors" function sticks out as a little nasty

let minFactors = 5
// let minFactors = 500

let isFactor x y = (x % y = 0UL)

let countFactors n = 
    [ 1UL.. 1UL + (n/2UL) ]
    |> List.filter (isFactor n)
    |> List.length    
    
let rec prob20 n triangle =
    if (countFactors triangle) >= minFactors
    then triangle
    else prob20 (n+1UL) (triangle+n+1UL)

prob20 1UL 1UL









    Out[28]:





28UL



In [6]:

    
// attempt 3 - above still took forever with minFactors>400-ish. Maybe a simple while loop
//          instead

let minFactors = 150
// let minFactors = 500

let isFactor x y = (x % y = 0UL)

let countFactors n = 
    [ 1UL.. 1UL + (n/2UL) ]
    |> List.filter (isFactor n)
    |> List.length    

let mutable i = 1UL
let mutable tri = 1UL
let mutable numFactors = 0

while numFactors < minFactors do    
    i <- i + 1UL
    tri <- tri + i    
    numFactors <- countFactors tri
    
printfn "%u" tri
tri









    Out[6]:





749700UL



In [65]:

    
// attempt 4 - oops ... when calculating factors use [0..sqrt(n)] instead of [0..n/2]

let minFactors = 500

let isFactor x y = (x % y = 0UL)

let square x = x * x

let sqrtExactlyDivideAdjust n endN numFactors = 
    if square endN = n then (numFactors - 1)
    else numFactors

let countFactors n = 
    let endN = uint64(sqrt(double(n)))
    [ 1UL .. (endN) ]
    |> List.map (fun x -> if isFactor n x then 2 else 0)
    |> List.sum
    |> sqrtExactlyDivideAdjust n endN
    
let rec prob12 n triangle =
    if (countFactors triangle) >= minFactors
    then triangle
    else prob12 (n + 1UL) (triangle + n + 1UL)

prob12 1UL 1UL









    Out[65]:





76576500UL



In [ ]: