# Project Euler Problem 43: Sub-string divisibility

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 1st digit, $d_2$ be the 2nd digit, and so on. In this way, we note the following:

$d_2d_3d_4=406$ is divisible by 2

$d_3d_4d_5=063$ is divisible by 3

$d_4d_5d_6=635$ is divisible by 5

$d_5d_6d_7=357$ is divisible by 7

$d_6d_7d_8=572$ is divisible by 11

$d_7d_8d_9=728$ is divisible by 13

$d_8d_9d_{10}=289$ is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

#### Version 1: Brute-Force¶

In [1]:
from itertools import permutations, islice, tee
from six.moves import map, range, reduce, zip

In [2]:
list(islice(permutations(range(10)), 20))

Out[2]:
[(0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
(0, 1, 2, 3, 4, 5, 6, 7, 9, 8),
(0, 1, 2, 3, 4, 5, 6, 8, 7, 9),
(0, 1, 2, 3, 4, 5, 6, 8, 9, 7),
(0, 1, 2, 3, 4, 5, 6, 9, 7, 8),
(0, 1, 2, 3, 4, 5, 6, 9, 8, 7),
(0, 1, 2, 3, 4, 5, 7, 6, 8, 9),
(0, 1, 2, 3, 4, 5, 7, 6, 9, 8),
(0, 1, 2, 3, 4, 5, 7, 8, 6, 9),
(0, 1, 2, 3, 4, 5, 7, 8, 9, 6),
(0, 1, 2, 3, 4, 5, 7, 9, 6, 8),
(0, 1, 2, 3, 4, 5, 7, 9, 8, 6),
(0, 1, 2, 3, 4, 5, 8, 6, 7, 9),
(0, 1, 2, 3, 4, 5, 8, 6, 9, 7),
(0, 1, 2, 3, 4, 5, 8, 7, 6, 9),
(0, 1, 2, 3, 4, 5, 8, 7, 9, 6),
(0, 1, 2, 3, 4, 5, 8, 9, 6, 7),
(0, 1, 2, 3, 4, 5, 8, 9, 7, 6),
(0, 1, 2, 3, 4, 5, 9, 6, 7, 8),
(0, 1, 2, 3, 4, 5, 9, 6, 8, 7)]
In [3]:
def nwise(iterable, n=2):
iters = tee(iterable, n)
for i, it in enumerate(iters):
for _ in range(i):
next(it, None)
return zip(*iters)

In [4]:
iterable_to_int = lambda iterable: reduce(lambda x, y: 10*x+y,iterable)

In [5]:
def pandigital_substring_divisible(digits, substring_size, divisors):
"""
Given n unique digits and specified substring
size of m, a list of n-m+1 divisors are expected
"""
for num in permutations(digits):
subs = map(iterable_to_int, nwise(num, substring_size))
if any(map(lambda n, m: n%m, subs, divisors)):
continue
else:
yield num

In [6]:
next(pandigital_substring_divisible(range(10), 3, [1, 2, 3, 5, 7, 11, 13, 17]))

Out[6]:
(1, 4, 0, 6, 3, 5, 7, 2, 8, 9)
In [7]:
pandigital_nums = list(pandigital_substring_divisible(range(10), 3, [1, 2, 3, 5, 7, 11, 13, 17])); pandigital_nums

Out[7]:
[(1, 4, 0, 6, 3, 5, 7, 2, 8, 9),
(1, 4, 3, 0, 9, 5, 2, 8, 6, 7),
(1, 4, 6, 0, 3, 5, 7, 2, 8, 9),
(4, 1, 0, 6, 3, 5, 7, 2, 8, 9),
(4, 1, 3, 0, 9, 5, 2, 8, 6, 7),
(4, 1, 6, 0, 3, 5, 7, 2, 8, 9)]
In [8]:
sum(map(iterable_to_int, pandigital_nums))

Out[8]:
16695334890

#### Version 2: Search space pruning with divisibility tests¶

In [9]:
# TODO