4
\$\begingroup\$

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.

Project Euler 43

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())[0])
        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)
\$\endgroup\$
  • \$\begingroup\$ Can the first digit in a number be 0, i.e., is every nine-digit number consisting of the digits 1 through 9 a base-10 pandigital number because you can stick 0 on the front? \$\endgroup\$ – David Harkness May 16 '14 at 22:01
  • 2
    \$\begingroup\$ I believe it can't start with a 0. \$\endgroup\$ – Joshua May 17 '14 at 14:38
5
\$\begingroup\$

You can make a few quick improvements without altering the algorithm significantly:

  • Remove one of the redundant calls to timer().

  • Store the list of primes instead of calculating it for every call to follows_property.

  • Convert the digits to strings in the list passed to permutations so you can simplify the calculation of num.

  • Run through all permutations instead of 9-tuples and remove the Counter and missing parts.

These are minor changes, but they clean up the code a bit. I also renamed ans to sum to clarify what it holds. They also cut the running time by more than half.

from itertools import permutations
from primes import primes_upto
from collections import Counter
from timeit import default_timer as timer

divisors = primes_upto(17)

def follows_property(n):
    for k in range(7):
        if int(n[k+1:(k+4)]) % divisors[k] != 0:
            return False
    return True

sum = 0
start = timer()

for combo in permutations([str(x) for x in range(10)]):
    num = ''.join(combo)
    if follows_property(num):
        sum += int(num)

elapsed_time = (timer() - start) * 1000 # s --> ms

print("Found %d in %r ms." % (sum, elapsed_time))
\$\endgroup\$
  • \$\begingroup\$ I just posted another answer to this question @DavidHarkness. I originally wanted to just post the idea as a comment on your answer because I liked your answer. However, my ideas would have been too jumbled in a comment. So please feel free to use any code you see fit from my answer to augment yours. +1 \$\endgroup\$ – BeetDemGuise May 16 '14 at 23:26
4
\$\begingroup\$

Instead of brute-forcing 10! permutations, I'd recommend going other way around: construct the necessary ones.

You know already that the last 3 digits must form a multiple of 17 - there's just 50 or so such numbers, provided that all 3 digits shall be different. Then prepend each of them with one of remaining 7 digits (350 things to try) eliminating those which do not yield a multiple of 13. Proceed with one more digit, etc.

I hope you see the point.

\$\endgroup\$
0
\$\begingroup\$

@DavidHarkness detailed nicely what needs to be done. However, I would add a couple more checks to ensure that any unnecessary permutations aren't processed:

for combo in permutations([str(x) for x in range(10)]):
    num = ''.join(combo)

    # This ensures that the second triple of numbers is even and the 
    # fourth triplet is divisible by 5.
    if int(num[3]) % 2 == 0 and num[5] in ['0', '5']:
        if follows_property(num):
            found += 1
            sum += int(num)
\$\endgroup\$
  • \$\begingroup\$ Are those digit-tests backwards? Are you sure there are nine numbers that satisfy the condition? \$\endgroup\$ – David Harkness May 16 '14 at 23:31
  • \$\begingroup\$ You were right, they were backwards. Thanks for the catch. And for the numbers, it must be true for the problem to be solvable. The only way a number would fit is if its 2nd triplet is divisible by 2 (i.e. must end in an even number) and if the 4th triple is divisible by 5 (i.e. must end in a 0 or a 5) \$\endgroup\$ – BeetDemGuise May 16 '14 at 23:37
  • \$\begingroup\$ My second question was referring to "If we have found all 9 numbers, stop." \$\endgroup\$ – David Harkness May 16 '14 at 23:48
  • \$\begingroup\$ Oops. I misread the problem statement. I thought they said that there were only 9 possible permutations. Will fix accordingly. \$\endgroup\$ – BeetDemGuise May 16 '14 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.