Problem Description

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 1^st digit, d₂ be the 2^nd 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.

Analysis

There are only 9 x 9! (3,265,920) possible 0-9 10-digit pandigital numbers. Simply generate the possibilities and check each 3-digit section to be divisible by the appropriate prime number. But even on a fast computer this method broke the one minute limitation.

Clearly something had to be done to reduce the number of permutations and upon closer inspection some rules were discovered. Keep in mind we are dealing with 3 digit numbers that must have unique digits in order to qualify as part of a 0-9 pandigital 10-digit number.

Rule 0: Can’t start with {0}.

Rule 1: Since d₄ has to be divisible by 2 then d₄ has to be from the set {0, 2, 4, 6, 8}.

Rule 2: Since d₄d₅d₆ has to be divisible by 5 then d₆ has to be from the set {0, 5}.

Rule 3: d₆d₇d₈ has to be divisible by 11 and, according to Rule 2, has to start with a {0, 5}. Well, it can’t start with 0 as that would yield invalid numbers such as {011, 022, … 099}, so it has to start with 5 and have only unique digits. The set is
{506, 517, 528, 539, 561, 572, 583, 594}.

New Rule 2: Amend Rule 2 to d₆ = {5}.

Rule 5: Since d₇d₈d₉ must be divisible by 13, begin with {06, 17, 28, 39, 61, 72, 83, 94}, contain no 5s and no repeated digits our set becomes {286, 390, 728, 832}.

Rule 6: Since d₈d₉d₁₀ must be divisible by 17, begin with {28, 32, 86, 90}, contain no 5s and no repeated digits our set becomes {289, 867, 901}.

Let’s review what we have and what combinations are possible for d₆ through d₁₀:
d₆ = {5}
d₇d₈d₉ = {286, 390, 728}
d₈d₉d₁₀ = {289, 867, 901}

d₆d₇d₈d₉d₁₀ = {52867, 53901, 57289}

Rule 7: d₅d₆d₇ must be divisible by 7 and end with {52, 53, 57} yields {357, 952}

Rule 1: Amend Rule 1 to d₄ = {0, 4, 6}.

Our solution set ends with {….357289 or ….952867}

You could finish the problem furthering this technique, but we reduced it enough to have the computer solve the rest.

Solution

Runs < 1 second in Python.

def fact(n):
  return reduce(lambda x,y:x*y,range(1,n+1),1)
 
def perm(n, s):
  if len(s)==1: return s
  q, r = divmod(n, fact(len(s)-1))
  return s[q] + perm(r, s[:q] + s[q+1:])
 
def check(n):
  s = str(n)
  return int(s[1:4]) % 2 == 0 and int(s[2:5]) % 3 == 0
 
s = 0
for i in range(0,18):
  a = int( perm(i,'4310')+'952867')
  if check(a): s += a
  a = int( perm(i,'6410')+'357289')
  if check(a): s += a
print "Answer to PE43 = ", s

Comments