Project Euler Problem 38

14 Aug 2012

Just solved problem 38 a few days ago, here is some notes about my algorithm:

Step 1: Permute string “987654321” in descending order.

Step 2: For every permutation, use its first few digits (could be 1-, 2-, 3-, or 4-digits) as a base integer to generate a 9-digit concatenated product, if possible; otherwise continue with next permutation.

Step 3: Test if that generated concatenated product is equal to the current permutation, if it is, you found an answer; otherwise, repeat from Step 2.

Here is my code in Python:

def p38():
    def print_concat_product(x):
        for i in xrange(2, 5):
            concat_product = x[0:i]
            n, base = 2, int(concat_product)
            while len(concat_product) <= 9:
                concat_product += str(base*n)
                if len(concat_product) == 9 and concat_product == x:
                    print x, "and its base:", str(base)
                    break
                n += 1

    # print out all pandigital 9-digit numbers whose first digit is 9
    # in the order of permutation, which is from biggest to smallest
    permute("9", "87654321", print_concat_product)

P.S. permute() is a function to gernerate permutations of a string