Project Euler — Problem 26 Solution

Problem

A unit frac­tion con­tains 1 in the numer­a­tor. The dec­i­mal rep­re­sen­ta­tion of the unit frac­tions with denom­i­na­tors 2 to 10 are giv­en:

1/2 = 0.5

1/3 = 0.(3)

1/4 = 0.25

1/5 = 0.2

1/6 = 0.1(6)

1/7 = 0.(142857)

1/8 = 0.125

1/9 = 0.(1)

1/10 = 0.1

Where 0.1(6) means 0.166666…, and has a 1-dig­it recur­ring cycle. It can be seen that 1/7 has a 6-dig­it recur­ring cycle.

Find the val­ue of d < 1000 for which 1/d con­tains the longest recur­ring cycle in its dec­i­mal frac­tion part.

Solution

let naturalNumbers = Seq.unfold (fun state -> Some(state, state+1)) 1

let rec cycleLength n =
    if n % 2I = 0I then cycleLength (n/2I)
    else
        if n % 5I = 0I then cycleLength (n/5I)
        else
            naturalNumbers
            |> Seq.filter (fun x -> ((pown 10I x) - 1I) % n = 0I)
            |> Seq.head

let answer = [1I..999I] |> Seq.maxBy cycleLength