Project Euler Problem 43 Solution: Sub-string divisibility

Project Euler Problem 43 Statement

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.

Solution

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: If 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 Observation 1, has to start with a {0, 5}. Well, it can’t start with 0 as that would yield non-unique digits {011, 022, ..., 099}, so it has to start with 5: d₆ = 5.
d₆d₇d₈ = {506, 517, 528, 539, 561, 572, 583, 594}

Since this is a closed ended problem a simple brute force search works very well. The observations are used to help minimize the search range.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 43

HackerRank Project Euler 43 extends the requirement from jhust 0-9 pandigital numbers to 0-3 to 0-9 pandigital numbers.

Python Source Code

from itertools import permutations
N = int(input("Number of pandigital digits 3-9? "))
q = [(1,2),(2,3),(3,5),(4,7),(5,11),(6,13),(7,17)]
s = 0
for p in permutations('0123456789'[:N+1]):
    if N>6 and p[5]!='5': continue
    if all(not int(''.join(p[px:px+3])) % pn for px,pn in q[:N-2]):
        s+= int(''.join(p))
print("Sum of all",N,"digit pandigital numbers with the sub-string divisibility property", s)

Last Word

You could continue to make observations that would reduce the search space. Here are a few:

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}

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}