Skip to content

Project Euler Problem 73

January 28, 2012

We build our Project Euler Problem 73 solution upon Farey sequences: the length of subsequence taken from Farey sequence of n = 12000 members between 1/3 and 1/2 would be the answer.
Now, knowing the member of this particular Farey sequence preceding 1/3 we can easily generate the sequence to the right until producing member that equals 1/2, then the answer would be number of produced members less 1. How to produce a member of Farey sequence knowing two preceding members can be found there.
Finally, finding the member of Farey sequence of n=12000 preceding 1/3 is easy, we have solved a similar problem there.

let ``preceding1/3`` =
    [1..12000]
    |> List.map (fun x -> (x - 1) / 3, x)
    |> List.maxBy (fun (x,y) -> (float x) / (float y))
   
let problem073() =
    Seq.unfold (fun ((a,b),c,d) ->
        if (c,d) = (1,2) then None
        else
            let temp = int((float (12000 + b)) / (float d)) in
                Some(1, ((c,d),temp*c - a, temp*d - b)))
            (``preceding1/3``, 1, 3)
    |> Seq.sum |> (+) -1
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: