Find the sum of all numbers that can be written as pandigital products.

Also known as Project Euler problem 32. Yes, I am still slowly working my way through these and – in this case – I am quite pleased with myself for having a solution, not least because I had to read the problem twice before I actually understood it.

The problem is this:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

That hint turns out to be useful.

My first thought was that I need a function to identify whether a number is pandigital. This turned out to be easier than I thought and I quickly came up with this:

def is_pandigital(integer):
    """ Returns True if ingeger is pandigital, else false
        A pandigital integer of length n is one that contains all
        digits from 1 to n exactly once
        integer is (obviously) an integer """
    text = list(str(integer))
    text.sort()
    for n in range (0, len(text)):
        if str(n + 1) != text[n]:
            return False
    return True

Now that I can test for pandigitality (is that a word?) I need to figure out what numbers to test. It was at this point that I realised that I already had a list_divisors function, written to solve an earlier problem. Handy, and a bit of trial and error established that I only need to check for four digit products if I want the product and its divisors to total 9 digits in length.

So…

from euler import is_pandigital, list_divisors

products = []

for n in range(1111, 9999):
    divisors = list_divisors(n)
    for m1 in divisors:
        m2 = n / m1
        as_text = str(n) + str(m1) + str(m2)
        if len(as_text) == 9:
            if is_pandigital(int(as_text)) == True:
                products.append(n)
                break

print reduce(lambda x, y: x+y, products)

The hint helps because once I have established that a product and its divisors amount to a pandigital number, I can stop checking (hence the break).

This is probably not the fastest solution available, but it works and it’s very easy to understand.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s