# Project Euler Problem 51

Project Euler Problem 51 really made me sweat. Interesting that this is the first “aged” problem with relatively small amount of solutions..

First, few considerations that narrow the solution space. The number of recurring digits to check is 3, because both for 2 and for 4 recurring digits if we take 8 such digits to build the sought sequence at least one member will be divisible by 3. Next, I made an educated guess to look for candidates among 6-digit numbers, i.e. ones greater, than 100000, but smaller than 1000000.

The solution itself is not mind-blowing. First we build the list of **candidates** of primes within 6 digit range having 3 or more recurring 0, or 1, or 2, because at least one of these should be the part of 8 combinations. Of those of having 3 recurring ones we exclude ending on 1 for the apparent reason of non-prime transforms. Then for each consecutive member of this pretty short list of candidates (less, than 2000) we transform it substituing the recurring number with other digits collecting only prime transformations. As soon as 7 such transformations are found the original member is the solution. This selection performs function **has7Transforms**.

Few coding tricks that I enjoyed building the solution. First, I chose to manipulate string presentation of numbers, retreating to numeric values only for checking if a string represents a prime number. Second, number of occurencies of a char in a string can be found using .NET **String.Split** method – it is one less, than number of empty and non-empty substrings after the split. Third, I like implementation of **has7Transforms** with representing **variant** as a tuple and calculating it via if-then-elif-else; then using the parts of this tuple in sequence comprehension, finally using this comprehension as argument to library function yielding the boolean return value. How succinct F# could be!

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 of3Digits0To2 (s: string) = let counts = [| (s.Split('0').Length - 1); (s.Split('1').Length - 1); (s.Split('2').Length - 1); |] if counts.[1] = 3 && s.Substring(5) = "1" then false else counts.[0] >= 3 || counts.[1] >= 3 || counts.[2] >= 3 let candidates = primes |> Seq.takeWhile ((>) 1000000) |> Seq.filter ((<) 100000) |> Seq.map string |> Seq.filter of3Digits0To2 let has7Transforms (s: string) = let variant = if s.Split('0').Length - 1 >= 3 then ("0",["1";"2";"3";"4";"5";"6";"7";"8";"9"]) elif s.Split('1').Length - 1 >= 3 then ("1",["0";"2";"3";"4";"5";"6";"7";"8";"9"]) else ("2",["0";"1";"3";"4";"5";"6";"7";"8";"9"]) Seq.length (seq { for i in (snd variant) do let candidate = Int32.Parse(s.Replace((fst variant), i)) if isPrime candidate && candidate >= 100000 then yield candidate }) >= 7 let problem051 () = candidates |> Seq.find has7Transforms