Skip to content

Project Euler Problem 66

December 24, 2011

After some hesitation between Chakravala method for solving Pell’s equation and another one based on continued fractions I decided to base my solution of Project Euler Problem 66 on the latter as it allows to reuse what was already done when solving Problem 64 and Problem 65.

let floorSqrt = float >> sqrt >> int

let isSquare x =
    let sqRoot = floorSqrt x
        in sqRoot * sqRoot = x

let continuedFractionExpansion s =
    if isSquare s then
        failwithf "s = %d is a perfect square" s

    let a0 = floorSqrt s
    Seq.unfold (fun (d, m) ->
        let d = (s - m * m) / d in
        Some ((a0 + m) / d, (d, ((a0 + m) / d) * d - m)))
        (1, a0)
    |> Seq.append [a0]

let solvePellEq s = 
    continuedFractionExpansion s
    |> Seq.scan (fun (``h(n)``,``k(n)``,``h(n-1)``,``k(n-1)``) ``a(n)`` ->
                     ((bigint ``a(n)``) * ``h(n)`` + ``h(n-1)``,
                      (bigint ``a(n)``) * ``k(n)`` + ``k(n-1)``,
                      ``h(n)``,``k(n)``))
                     (1I,0I,0I,1I)
    |> Seq.skip 1
    |> Seq.find (fun (h,k,_,_) -> h*h - (bigint s)*k*k = 1I)
    |> fun (x,y,_,_) -> (x,y)

let problem066 () =
    (Seq.initInfinite >> Seq.skip 2) id
    |> Seq.filter (isSquare >> not)
    |> Seq.takeWhile ((>=) 1000)
    |> Seq.map (fun x -> (((solvePellEq >> fst) x), x))
    |> Seq.maxBy fst
    |> snd

The solution is very straightforward and does not carry any F# specific techniques despite pleasant notation in lines 20-23 for reflection of recurrence when calculating convergents.
The solution is pretty fast delivering the result in 62ms on a mediocre laptop.

Advertisements

From → Project Euler

Leave a Comment

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: