Project Euler – Problem 26 Solution

Problem

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

¹/₂ = 0.5

¹/₃ = 0.(3)

¹/₄ = 0.25

¹/₅ = 0.2

¹/₆ = 0.1(6)

¹/₇ = 0.(142857)

¹/₈ = 0.125

¹/₉ = 0.(1)

¹/₁₀ = 0.1

Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that ¹/₇ has a 6-digit recurring cycle.

Find the value of d < 1000 for which ¹/_d contains the longest recurring cycle in its decimal fraction 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