Skip to content

Project Euler Problem 60

December 15, 2011

I did not manage solving Project Euler Problem 60 in an exciting way. The solution is based on few strong and pretty weakly grounded assumptions: that the sought sequence would begin at one of few lowest primes {7,11,13,17} and end with a prime lower, than 10000. The approach is very straightforward – build all pairs, then triplets, etc… Of all 5-member sequences pick one with minimal sum of members.

open System

#nowarn "40"

let rec primes = 
    Seq.cache <| seq { yield 2; yield! Seq.unfold nextPrime 3 }
and nextPrime n =
    if isPrime n then Some(n, n + 2) else nextPrime(n + 2)
and isPrime n =
    if n >= 2 then
        primes 
        |> Seq.tryFind (fun x -> n % x = 0 || x * x > n)
        |> fun x -> x.Value * x.Value > n
    else false

let concatenate n1 n2 =
    Int32.Parse(n1.ToString() + n2.ToString())

let rec canAdd xs x =
    match xs with
    | [] -> true
    | h :: t -> if isPrime (concatenate x h) && isPrime (concatenate h x) then
                    canAdd t x
                else false

let subSequence lower upper =
    Seq.skipWhile ((>=) lower) >> Seq.takeWhile ((>) upper)

let seed lower upper =
    primes
    |> subSequence lower upper
    |> Seq.map (fun x -> [x])
    |> Seq.toList

let nextLevelItem ls upper =
    primes |> subSequence (List.head ls) upper
    |> Seq.zip (Seq.initInfinite (fun x -> ls))
    |> Seq.filter (fun (xs,x) -> canAdd xs x)
    |> Seq.map (fun (xs,x) -> x :: xs) |> Seq.toList

let rec nextLevel ps upper =
    match ps with
    | [] -> []
    | h :: t -> List.append (nextLevelItem h upper) (nextLevel t upper)

let problem060 () =
    nextLevel (nextLevel (nextLevel (nextLevel (seed 7 19) 10000) 10000) 10000) 10000
    |> List.map List.sum
    |> List.min

Interesting that the code above yields exactly one sequence that begins with 13. Changing upper limit to 20000 yields just another one sequence with greater sum of members that begins with 7.

Speaking of specific F# techniques, I came up with pretty elegant polymorphic way of getting a subsequence of comparable subSequence : ‘a -> ‘a -> (seq -> seq) when ‘a : comparison

let subSequence lower upper =
    Seq.skipWhile ((>=) lower) >> Seq.takeWhile ((>) upper)
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: