60 Days of Euler in F# - Problem 43

The Problem

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

  • d2d3d4=406 is divisible by 2
  • d3d4d5=063 is divisible by 3
  • d4d5d6=635 is divisible by 5
  • d5d6d7=357 is divisible by 7
  • d6d7d8=572 is divisible by 11
  • d7d8d9=728 is divisible by 13
  • d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

The Solution

So, this problem is fairly simple, but it might be one of those tricky ones where the obvious solution isn't fast enough. But let's try the obvious solution and see where that gets us.

First, we'll declare a list with our prime divisors.

let divisors = [ 2; 3; 5; 7; 11; 13; 17 ]

Next, we'll write a function to take a list of digits and turn that into a number.

let toNumber (l : int list) =
    int64 (System.String.Join("", l |> List.map (fun x -> x.ToString())))

Now we need a function to determine if a given list of numbers is "special" according to the problem definition.

let isSpecial (n : int list) =
    |> Seq.map (fun x -> n.[x] * 100 + n.[x+1] * 10 + n.[x+2])
    |> Seq.zip divisors
    |> Seq.forall (fun (d,n) -> n % d = 0)

The problem definition starts counting d at 1, but we're in .NET-land where things are 0-based. The list [1..7] represents the starting d.

Next, Seq.map takes that d and the two right after it and turns it into a 3-digit number.

Seq.zip creates a new sequence of each 3-digit number and all the divisors.

Finally, Seq.forAll determines if is the sequence isSpecial by ensuring each number is divisible by all the divisors.

Now we can solve the problem.

let rec distribute e = function
    | [] -> [[e]]
    | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]
let rec permute = function
    | [] -> [[]]
    | e::xs -> List.collect (distribute e) (permute xs)

permute [0..9]
|> Seq.filter isSpecial
|> Seq.sumBy toNumber

We start with the pair of functions we used in Problem 41 for generating permutations.

Next, we get all the permutations of the digits 0..9. We filter out any of those that aren't "special", convert the ones that are into numbers, and take the sum. The sum is the answer to the problem.

Other Posts in This Series