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 d₁ be the 1st digit, d₂ be the 2nd digit, and so on. In this way, we note the following:

• d₂d₃d₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=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) =
    [1..7]
    |> 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)

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

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