# Project Euler Problem 64

Project Euler Problem 64 solution below is based on a detailed consideration of the method of computing square roots known as continued fraction expansion. The code preserves naming of members of recurrent equation from there.

let oddLengthPeriod s = let a0= int (sqrt (float s)) if a0 * a0 = s then false else Seq.initInfinite id |> Seq.scan (fun (d, m, _) i -> let d = (s - m * m) / d in (d, ((a0 + m) / d) * d - m, i + 1)) (1, a0, 0) |> Seq.skip 1 |> Seq.skipWhile (fun (d, _, _) -> d <> 1) |> Seq.head |> fun (_, _, p) -> p % 2 = 1 let problem064 () = [2..10000] |> Seq.filter oddLengthPeriod |> Seq.length

There is an interesting F# feature has being applied in lines 7 – 8 above that allows for simultaneous use of old and new values of recurrent variable without making it mutable.

Advertisements

## Trackbacks & Pingbacks