# 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