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 d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
- d2d3d4=406 is divisible by 2
- d3d4d5=063 is divisible by 3
- d4d5d6=635 is divisible by 5
- d5d6d7=357 is divisible by 7
- d6d7d8=572 is divisible by 11
- d7d8d9=728 is divisible by 13
- d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property.
from itertools import permutations from primes import primes_upto from collections import Counter from timeit import default_timer as timer start = timer() def follows_property(n): divisors = primes_upto(17) for k in range(7): if int(n[k:(k+3)]) % divisors[k] != 0: return False return True ans = 0 digits = Counter(range(10)) start = timer() for combo in permutations(range(10), 9): num = ''.join([str(x) for x in list(combo)]) if follows_property(num): missing = int(list((digits - Counter(sorted([int(k) for k in str(num)]))).elements())) num = int(num) ans += int("%d%d" % (missing, num)) elapsed_time = (timer() - start) * 1000 # s --> ms print "Found %d in %r ms." % (ans, elapsed_time)