Project Euler 38: Pandigital Multiples

Question

I just solved Project Euler 38 and was wondering if you guys could provide some suggestions on how to speed it up. I've tried adding extra conditions but they increase the time. Any ideas on how to optimize the numbers I'm checking would be appreciated.

from timeit import default_timer as timer

def create_pandigital_multiple(original_number):
    num = str(original_number)
    digits = range(1, 10)
    if len(num) >= 5:
        return 0
    else:
        temp = 2
        while len(num) < 9:
            num += str(original_number * temp)
            temp += 1
        if sorted([int(x) for x in num]) == digits:
            return int(num)
        else: 
            return 0

start = timer()
ans = 0
for k in range(9, 10**5):
    if create_pandigital_multiple(k) > greatest:
        ans = create_pandigital_multiple(k)

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

print "Found %d in %r ms." % (ans, elapsed_time)

Answer 1

• Checking if len(num) >= 5 is redundant because you only call the function with k < 10**5
• Instead of sorted([int(x) for x in num]) you could compute just sorted(num) and compare that to a DIGITS = [str(i) for i in range(1, 10)] constant that you can compute outside the function.
• Most of the multiples end up longer than 9 digits. Testing len(num) == 9 before sorting the digits should be faster.
• You could take advantage of the example 918273645 provided in the problem statement. The number you are looking for must be greater or equal to that. For one thing, the first two digits must be in range 91 to 98, which is a small fraction of all the two-digit numbers you try.

Answer 2

Ok first off we can narrow the range by making the following observations coupled with the obvious fact the number must begin with a 9.

• \$x\$ is not 9
• if \$90 \leq x <100\$, then \$n1+n2+n3 \approx 90180360\$ an 8 digit number, so we can exclude this range as well

• if \$900 \leq x <1000\$, then \$\approx 90018003600\$; too many so they can be eliminated.

• Finally if \$9000 \leq x < 10000\$, we have \$n1 + n2 \approx 900018000\$; a 9 digit

So we can narrow the range to 9000 to 9999. That brings your run time down to about 9.7 ms from 100 ms

Here is a more efficient way to find 1-9 pandigitals by observing from above that n has a max value of 2 which eliminates the need for a nested loop by directly creating the number to check like this:

def problem38():
    largest=int()      
    for i in xrange(9000,10000):
        temp=str(i)+str(i*2)
        if "0" not in temp:
            if len(set(temp))==9:
                if int(temp)>largest:
                    largest=int(temp)

    return largest 

By testing if the number contains 0 then testing the set length we know the number is pandigital.

This algorithm runs in 1.3 ms

Answer 3

Instead of

if create_pandigital_multiple(k) > greatest:
    ans = create_pandigital_multiple(k)

you can use

ans = max(ans, create_pandigital_multiple(k))