We say that is a pandigital product if and the string “abn” obtained by concatenating the base-10 representations of , , and contains all of the digits 1-9 exactly once (with no 0s). In problem 32 we are asked to find the sum of all pandigital products.
I ended up being not particularly fancy about this problem. Loop through enough values for , and, for each , loop through enough values for , and see if you get a pandigital product with , , and . We know that it is enough for to venture up to , but what about bounds on ? If has 5 digits, then to be a pandigital product, with factors and , the factors must be either 1 and 3 digits, or 2 and 2 digits. But 9*999 and 99*99 aren’t 5 digit numbers, so we know we can stop looking for once we get to 10000. Similar reasoning shows that must have more than 3 digits, and so, in fact, to be a pandigital product, must have 4 digits (and since they must not be 0, and must be distinct, 1234 is the smallest possibility).
The following code seems to get the job done:
def ispandigprod(a,b,n): """ assumes a*b==n """ # consider the digits in the string "abn" # remove 0s and duplicates (with filter, set) # if you've still got 9 elements, you're pandigital return len(set(filter(lambda t:t, map(int, "%s%s%s" % (a,b,n))))) == 9 def solve(): """ return the sum of the pandigital products """ ret = 0 for n in xrange(1234,9876+1): a = 1 included = False while(a < n**.5 + 1 and not included): if(n % a == 0): b = n//a if(ispandigprod(a,b,n)): ret += n included = True a += 1 return ret
I’d honestly like a nicer solution for this problem. The loop I have is pretty stupid, and loops through far more choices than is worthwhile. In particular, I’d like to not think about any or that have a digit that is 0. To ignore with a 0 digit, one could replace the “included = False” line (apparently line 10) with
included = str(n).count("0") > 0
This seems to cut the run-time down by about 20% (or more), so is maybe worthwhile. I still expect this code could be improved by a bit, but I think I’ll stop here for now.
Tags: prob32
Leave a comment