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)
permute() is a function to gernerate permutations of a string