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