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   

Problem #99 says:

Comparing two numbers written in index form like 2^(11) and 3^(7) is not difficult,
as any calculator would confirm that 2^(11) = 2048 < 3^(7) = 2187.

However, confirming that 632382^(518061) > 519432^(525806) would be much more difficult,
as both numbers contain over three million digits.

Using base_exp.txt (right click and ‘Save Link/Target As…’), a 22K text file containing one
thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

This is a problem that seems kinda complicated at first. Each of the base exponent sets creates a number that easily dwarfs anything a computer can currently handle. The solution is to do something else that still lets us compare them to one another. So instead of expanding the exponent base pair what we do is multiply the exponent by the natural log of the base and use that value. Using this method reading the file in is almost harder than solving the task.

Solution in F# requires .net 4, runs in under one second.

open System
open System.IO
open System.Diagnostics

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

let test b e =
    e * Math.Log(b)    

let CheckSets =
    let f = new StreamReader("base_exp.txt")
    let mutable lines = []
    let mutable line = f.ReadLine()
    while line <> null do
        lines <- lines @ [line]
        line <- f.ReadLine()
    lines

let mutable mv = 0.0
let mutable ml = 0
let mutable ln = 0

let FindAnswer =
    for s in CheckSets do
        ln <- ln + 1
        let ss = s.Split(",".ToCharArray())
        let b = float ss.[0]
        let e = float ss.[1]
        if (test b e) > mv then
            mv <- (test b e)
            ml <- ln
FindAnswer
Console.WriteLine(ml)
sw.Stop()
Console.WriteLine(sw.Elapsed)
Console.ReadLine() |> ignore

Here are some random snippets of f# code I had lying around. mostly simple stuff for basic stats calculations. Not the most complex stuff but maybe its useful to somebody trying to learn f#.

// Learn more about F# at http://fsharp.net
open System
open System.Net

//basic arithmetic mean
let Mean (x:List<float>) =
    let sum = x |> Seq.sum
    let items = x |>Seq.length
    sum / (float items)

//basic variance method
let Variance x =
    let m = Mean x
    let deviation =
        x
        |> Seq.map (fun x -> Math.Pow((x-m), 2.))
        |> Seq.toList
    Mean deviation

//Calculates standard deviation using above variance method
let StandardDeviation x =
    Math.Sqrt(Variance x)

//recursively calculates the factorial of x
//will overflow long before running into recursion limits
//at larger values it will wrap back around to 0
let rec Factorial x =
    if x = 0I then
        1I
    else
        x * Factorial(x-1I)

//calculates combinations
let Combinations n r =
    (Factorial n)/ ((Factorial r)*(Factorial (n-r)))

//calculates permutations
let Permutations n r =
    (Factorial n)/ (Factorial (n-r))

//uses Euclids formula for the greatest common divisor
let rec GCD a b =
    if b = 0UL then
        a
    else
        GCD b (a%b)

//returns an array representing the binary version of x
let toBinary (x:uint64) =
    let rec con (x:uint64) r =
        if x = 0UL then
            r
        else
            con (x/2UL) ([x%2UL] @ r)
    con x []

// gets ticker price using yahoo
let GetTickerPrice (ticker:string) =
    let url =
        "http://download.finance.yahoo.com/d/quotes.csv?s="+
        ticker+
        "&f=sl1d1t1c1ohgv&e=.csv"
    let wc = new WebClient()
    let info = wc.DownloadString(url).Split([|','|])
    float info.[1] // info.[1] is the current price will return 0.0 on invalid ticker

Problem #73 says:

Consider the fraction, n/d, where n and d are positive integers. If n

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

First off brute forcing this problem isn’t hard, and you can do it in well under a minute. However there is an elegant solution so readily available that it would be a shame not to go with it. The elegant method involves calculating a Farey Sequence (http://en.wikipedia.org/wiki/Farey_sequence) then counting the results. Alternatively we can just count how many results we would have without calculating the actual results.

Solution in f# and runs in ~.32 seconds. Requires .net 4 and fsharp.

#light
module ProjectEuler

open System
open System.Diagnostics

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

let rec FareySeq denom1 denom2 max =
    if (denom1+denom2) > max then
        0.0
    else
        1.0 + (FareySeq denom1 (denom1+denom2) max)+(FareySeq (denom1+denom2)denom2 max)

Console.WriteLine(FareySeq 3 2 12000)
watch.Stop()
Console.WriteLine(watch.Elapsed)
Console.Beep() |> ignore
Console.ReadKey() |> ignore

Problem #58 says:

Starting with 1 and spiraling anticlockwise in the following way, a square spiral with side length 7 is formed.

It is interesting to note that the odd squares lie along the bottom right diagonal,
but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime;
that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed.
If this process is continued, what is the side length of the square spiral for which the ratio of
primes along both diagonals first falls below 10%?

The below solution simply counts the offset between corners and checks that number to see if its prime or composite then the next cycle after its check it updates the offset amount and continues this way until its collected a list of prime and composite numbers that have less than 10% prime numbers. very simple, no optimizations applied. The solution could be made faster by using a simpler test and also by not keeping a list of composite numbers but a counter instead.

Solution in f# and requires the .net 4.0 run-time. runs in ~50 seconds.

#light
module ProjectEuler

open System
open System.Diagnostics
open Microsoft.FSharp.Linq
open Microsoft.FSharp.Collections
open Microsoft.FSharp.Math
open System.Numerics

let toBinary (n:BigInteger) =
    let mutable m = n
    let mutable r = []
    while m > BigInteger.Zero do
        r <- r @ [(m % (BigInteger 2))]
        m <- m / BigInteger 2
    r

let test (a:BigInteger) (n:BigInteger) =
    let (b:List<BigInteger>) = toBinary (n - BigInteger.One)
    let mutable d = BigInteger.One
    let mutable Prime = false
    let CheckList = [0 .. b.Length-1 ] |> List.rev
    for i in CheckList do
        let x = d
        d <- (d*d) % n
        if (d = BigInteger.One && x <> BigInteger.One && x <> n-BigInteger.One) then
            Prime <- true // complex
        if b.[i] = BigInteger.One then
            d <- (d*a) % n
    if d <> BigInteger.One then
        Prime <- true //complex
    Prime //if its still false then prime

let MillerRabin (n:uint64) (s:int) =
    let Rand = new System.Random()
    let mutable Prime = true
    if n < Convert.ToUInt64(Int32.MaxValue) then
        for j in [1 .. s+1] do
            let a = Rand.Next(1, Convert.ToInt32(n)-1)
            if (test (BigInteger a) (BigInteger n)) then
                Prime <- false
    else
        for j in [1 .. s+1] do
            let a = Rand.Next(1, Int32.MaxValue)
            if (test (BigInteger a) (BigInteger n)) then
                Prime <- false
    Prime

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

let rec Answer (currentnum:uint64) (step:uint64) (prime:List<uint64>) (composite:List<uint64>) (tick:bool) =
    let check = (float prime.Length)/((float composite.Length)+(float prime.Length))
    if check < 0.1 && currentnum > 100UL  then
        step-1UL
    else
        if (tick) then
            if (MillerRabin currentnum 10) then
                Answer (currentnum+step) step (currentnum::prime) composite (false)
            else
                Answer (currentnum+step) step (prime) (currentnum::composite) (false)
        else
            if (MillerRabin currentnum 10) then
                Answer (currentnum+step) (step+1UL) (currentnum::prime) composite (true)
            else
                Answer (currentnum+step) (step+1UL) (prime) (currentnum::composite) (true)

Console.WriteLine(Answer 3UL 2UL [] [1UL] true )
watch.Stop()
Console.WriteLine(watch.Elapsed)
Console.Beep() |> ignore
Console.ReadKey() |> ignore