## Project Euler 43: Find the sum of all pandigital numbers with an unusual sub-string divisibility property.

#### Project Euler 43 Problem Description

Project Euler 43: 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*_{1} be the 1^{st} digit, *d*_{2} be the 2^{nd} digit, and so on. In this way, we note the following:

*d*_{2}*d*_{3}*d*_{4}=406 is divisible by 2*d*_{3}*d*_{4}*d*_{5}=063 is divisible by 3*d*_{4}*d*_{5}*d*_{6}=635 is divisible by 5*d*_{5}*d*_{6}*d*_{7}=357 is divisible by 7*d*_{6}*d*_{7}*d*_{8}=572 is divisible by 11*d*_{7}*d*_{8}*d*_{9}=728 is divisible by 13*d*_{8}*d*_{9}*d*_{10}=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 may take too long to run.

We can make some observations to reduce the number of possibilities. 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.

### Some observations

**Observation 1:** *d*_{4}*d*_{5}*d*_{6} must be divisible by 5 then:

*d*_{6} = {0, 5}.

**Observation 2:** *d*_{6}*d*_{7}*d*_{8} must to be divisible by 11 and, according to Obs. 1, has to start with a {0, 5}. Well, it can’t start with 0 as that would yield non-unique digits, so it has to start with 5, i.e., ** d_{6} = 5**.

*d*

_{6}

*d*

_{7}

*d*

_{8}= {506, 517, 528, 539, 561, 572, 583, 594}

**Observation 3:** *d*_{7}*d*_{8}*d*_{9} must be divisible by 13, begin with {06, 17, 28, 39, 61, 72, 83, 94} by Obs. 2, contain no 5s and have only unique digits:

*d*_{7}*d*_{8}*d*_{9} = {286 390 728 832}

**Observation 4:** *d*_{8}*d*_{9}*d*_{10} must be divisible by 17, begin with {28, 32, 86, 90} by Obs. 3, contain no 5s and have only unique digits:

*d*_{8}*d*_{9}*d*_{10} = {289, 867, 901}

**Observation 5:** *d*_{5}*d*_{6}*d*_{7} must be divisible by 7, end with {52, 53, 57, 58} by Obs. 2 & 3 and have only unique digits:

*d*_{5}*d*_{6}*d*_{7} = {357, 952}

We have reduced our possibilities for the last 6 digits using our 5 observations to:

*d*_{5}*d*_{6}*d*_{7}*d*_{8}*d*_{9}*d*_{10} = {357289, 952867}

### Finishing the problem

**Observation 6:** *d*_{3}*d*_{4}*d*_{5} must be divisible by 3, not contain {2, 5, 7, 8} since they have been place, end in {3, 9}, have all unique digits and an even middle number:

*d*_{3}*d*_{4}*d*_{5} = {063, 309, 603}

This forces *d*_{1}*d*_{2} to {14, 41}

Our final set is: {1406357289, 1430952867, 1460357289, 4106357289, 4130952867, 4160357289}

#### Afterthoughts

- Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A050278: Pandigital numbers: numbers containing the digits 0-9. Version 1: each digit appears exactly once.
- 0 to 3 pandigital is 22212
- 0 to 4 pandigital is 711104

*Project Euler 43 Solution last updated*

2-liner, same code

from itertools import permutations

print(sum(int(”.join(x)) for x in permutations(‘0123456789’, 10) if all([not int(”.join(x)[n[0]:n[1]]) % n[2] for n in [(1, 4, 2), (2, 5, 3), (3, 6, 5), (4, 7, 7), (5, 8, 11), (6, 9, 13), (7, 10, 17)][:7]])))

Dude, that is cool. About as fast too. Thanks for sharing this!

another rule:

Since d3d4d5 has to be divisible by 3 and d5 is {3,9}, (d3+d4) have to be divisible by 3.

When d5d6d7d8d9d10 is 952867,d3d4 can only be 30 ,then we have two numbers with this property.

when d5d6d7d8d9d10 is 357289,d3d4 can be 06 or 60, then we have four numbers with this property.

Sum all these six numbers, we get the answer.

Thanks for finishing the analysis for doing it without a computer. Good solution.

Thanks a lot!!

only 20 seconds for me, before your beautiful explanation.

Bye

Thanks for the comment Bancaldo, glad it could help you.