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₁ 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 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₄d₅d₆ must be divisible by 5 then:
d₆ = {0, 5}.

Observation 2: d₆d₇d₈ 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₆ = 5.
d₆d₇d₈ = {506, 517, 528, 539, 561, 572, 583, 594}

Observation 3: d₇d₈d₉ 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₇d₈d₉ = {286 390 728 832}

Observation 4: d₈d₉d₁₀ must be divisible by 17, begin with {28, 32, 86, 90} by Obs. 3, contain no 5s and have only unique digits:
d₈d₉d₁₀ = {289, 867, 901}

Observation 5: d₅d₆d₇ must be divisible by 7, end with {52, 53, 57, 58} by Obs. 2 & 3 and have only unique digits:
d₅d₆d₇ = {357, 952}

We have reduced our possibilities for the last 6 digits using our 5 observations to:
d₅d₆d₇d₈d₉d₁₀ = {357289, 952867}

Finishing the problem

Observation 6: d₃d₄d₅ 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₃d₄d₅ = {063, 309, 603}

This forces d₁d₂ 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