Project Euler 32: Find the sum of all numbers that can be written as pandigital products
Problem Description
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.
Analysis
This is a perfect application for a simple brute force program that iterates through the possibilities and produces a solution.
The only thought of optimization was to generate as many 4 digit products as necessary in order to keep the concatenation of the factors and product at the required 9 digits.
The only possible combinations that accomplish this are a 1 digit number times a 4 digit number (like 1 x 2345 = 2345 and concatenates to 123452345; a nine digit number), or a 2 digit number times a 3 digit number (like 12 x 345 = 4140 and concatenates to 123454140; a nine digit number).
You must keep the factors form exceeding 4 digit products such as 56 x 789 = 44184 and that’s where the 10000//i comes in. The double slash (//) specifies integer (or floor) division.
A set is used to ignore duplicate products.
Project Euler 32 Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 32 Solution Python 2.7 source.
Afterthoughts
- Function
is_pandigitalis listed in Common Functions and Routines for Project Euler - This solution took 21,139 iterations.
- Of the 9 sets found, the last one was 48 × 159 = 7632
I checked my problem many times cannot find the problem.
4 * 1738 = 6952
4 * 1963 = 7852
12 * 483 = 5796
18 * 297 = 5346
27 * 198 = 5346
28 * 157 = 4396
39 * 186 = 7254
42 * 138 = 5796
48 * 159 = 7632
My answer is 56370, anybody know what’s wrong with my answer?
Posted by Yi | July 19, 2011, 4:32 AMHi Yi,
You need to ignore duplicate products. So,
56370 – 5346 – 5796 = 45228.
Posted by Mike | July 19, 2011, 4:45 AMOk lol that’s y… I didn’t even notice that. =]
Posted by Yi | July 19, 2011, 4:50 AMThe correct answer is actually 45228
Posted by Dimitar | July 1, 2011, 8:22 PMYes, yes it is Dimitar. And by running the program that answer is calculated.
Posted by Mike | July 10, 2011, 1:34 AMDid you submit this answer? It seems to me that it’s not right. Don’t you need to consider cases like 4*3=12? And at the end don’t you have to check if there are repeated products? I’ve spent over an hour on this problem and I can’t get the right answer… Thanks!
Posted by Ilan | August 20, 2009, 7:41 PMThe ‘set’ data type in Python takes care of repeated products so the solution is simply adding the set. I ran the app again and it produces a correct answer.
Please understand that the problem is looking for a 1-9 pandigital sequence so all digits 1-9 must be used once. 4*3=12 leaves out 5,6,7,8 and 9.
Posted by Mike | August 24, 2009, 6:41 PM