# Project Euler Problem 60

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)