Skip to content

Project Euler Problem 64

December 20, 2011

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

From → Project Euler

One Comment

Trackbacks & Pingbacks

  1. Project Euler Problem 66 « In F# Major

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: