Problem 032

Project Euler

Pandigital products

Problem 32

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.

First, let’s analyze the number of ways to arrange 1-9, x, and = as a permutation. There are 11 slots and 11 unique symbols, thus, the number of ways to arrange them is 11!. That’s almost 40 million ways to arrange them but not all them will be valid.

Let’s look at some of these constraint. First, the leading value must be a digit and the multiple sign must be before the equal sign with the last slot must be a digit as well which cut the original number over 100 fold but it is still a big number. Notice that one digit number multiple another digit number can not produce a 7-digits numbers because there are 9 digits to consider. Thus, using this deduction, we notice there is only 4 possible ways to produce a valid result:

  1. d x dddd = dddd
  2. dd x ddd = dddd
  3. ddd x dd = dddd
  4. dddd x d = dddd

The first and forth, second and third are the exact same solution because multiplication is communicative. Furthermore, for case 1, digit 1 cannot be the lone digit at the beginning because 1xn = n and it will not result in 1-9 pandigital. Therefore,

Case 1: a x bddd = cddd

where a can only be 2, 3 and b can be 1 and up to (10-2)/a with c must be at least axb and up to ax(b+1)-1 but not exceed 9. There are 10 ways to build case 1 with the remaining 5 digits to search for (10 x 6! =7200 possibility to search). Using similar logic, we can deduce case 2 as follow:

Case 2: ad x bdd = cddd

where a can be 1-8, b can be 1 and up to (10-2)/a and c must be at least axb and up to (a+1)x(b+1)-1 but not exceed 9. (52 x 6! for 37440 possibility to search). Limiting the searches will speed up the nested loops that produces the choices for multiplicands and multipliers and thus, speed up the program.