Problem #57 says:

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

The fastest way to attack this one is to treat it as a sequence and find the pattern required to expand it. for the numerator to take the previous denominator and multiple it by two then add the previous numerator to it, for the denominator you just add the previous numerator and denominator together. This gets really big really fast so we’ll use the biginteger class in .net 4. then we just check the string length of the numerator and denominator and see which is larger. wash rinse and repeat.

Solution in f# and requires .net 4.0 Runs in (5* (10^-6)) seconds or 65 ticks on my netbook.

open System
open System.Diagnostics

let sw = new Stopwatch()
sw.Start()

let num n d = (2I*d)+n
let den n d = n+d

let rec Answer n d c count =
    if c > 1000 then
        count
    else
        if n.ToString().Length > d.ToString().Length then
            Answer (num n d) (den n d) (c+1) (count+1)
        else
            Answer (num n d) (den n d) (c+1) count

sw.Stop()
Console.WriteLine(Answer 3I 2I 0 0)
Console.WriteLine(sw.Elapsed.Ticks)
Console.ReadLine() |> ignore