(2 votes, average: 5.00 out of 5)

## Project Euler Problem 43 Solution

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

#### Analysis

There are only 9 x 9! (3,265,920) possible 0-9 ten-digit pandigital numbers. Simply generate the possibilities and check each three-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 ten-digit number.

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

Rule 2: Since d4d5d6 has to be divisible by 5 then d6 has to be from the set {0, 5}.

Rule 3: d6d7d8 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 d6 = {5}.

Rule 5: Since d7d8d9 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 d8d9d10 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 d6 through d10:
d6 = {5}
d7d8d9 = {286, 390, 728}
d8d9d10 = {289, 867, 901}

d6d7d8d9d10 = {52867, 53901, 57289}

Rule 7: d5d6d7 must be divisible by 7 and end with {52, 53, 57} yields {357, 952}

Rule 1: Amend Rule 1 to d4 = {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.

```from Euler import factorial, perm   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```

## Discussion

### 5 Responses to “Project Euler Problem 43 Solution”

1. there is an error in the code, the check function, should be s[1:4] and s[2:5]

Posted by lhz | January 22, 2010, 1:01 AM
2. Thanks to LHZ! Very observant and proper correction! The above code is now correct.

Posted by Mike | January 22, 2010, 3:45 AM
3. Thanks a lot!!
only 20 seconds for me, before your beautiful explanation.

Bye

Posted by bancaldo | December 6, 2012, 4:34 AM