Problem 43 - Find the sum of all pandigital numbers with an unusual sub-string divisibility property.

링크

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.

python - brute force

import itertools sum = 0 primes = [2,3,5,7,11,13,17] for p in itertools.permutations("1023456789"): n = "".join(p) ok = True for k in range(7): nn = int(n[k+1:k+4]) if nn % primes[k] != 0: ok = False break if ok: sum += int(n) print sum

python - effective

primes = [2,3,5,7,11,13,17] digits = [0]*10 use = [0]*10 def go(index, digit, num): if (index == 10): return num if (use[digit] == 1): return 0 res = 0 digits[index] = digit use[digit] = 1 ok = True if index >= 3: n = digits[index-2]*100 + digits[index-1]*10 + digit if n % primes[index-3] == 0: ok = True else: ok = False if ok: for i in range(0, 10): res += go(index+1, i, num*10 + digit) use[digit] = 0 return res print sum(go(1, x, x) for x in range(1, 10))