Skip to content

Project Euler Problem 51

November 28, 2011

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
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: