Detailed mathematical approach

Problem Summary

A multiplicand \(a\), a multiplier \(b\), and a product \(p=ab\) form a valid identity when the decimal digits of \(a\), \(b\), and \(p\) together use each of \(1,2,\dots,9\) exactly once. The task is to find every such identity and sum the distinct product values, counting the same product only once even if it has more than one factorization.

The standard example is \(39\times 186=7254\), because the concatenation \(391867254\) is a permutation of \(123456789\).

Mathematical Approach

The solution is a finite search, but it is not an arbitrary brute-force search. A short digit-length argument collapses the problem to two search families, and a simple invariant decides whether a candidate identity is truly 1-to-9 pandigital.

The digit-length equation leaves only two possibilities

Let \(x=d(a)\), \(y=d(b)\), and \(z=d(p)\), where \(d(n)\) is the number of decimal digits of \(n\). A valid pandigital identity uses exactly nine digits overall, so

$x+y+z=9.$

For the product of an \(x\)-digit number and a \(y\)-digit number, the result has either \(x+y-1\) digits or \(x+y\) digits. Therefore

$z\in\{x+y-1,\ x+y\}.$

If \(z=x+y\), then \(9=2(x+y)\), which is impossible because the left-hand side is odd. So the only remaining case is \(z=x+y-1\), giving

$9=x+y+(x+y-1)=2(x+y)-1,$

hence \(x+y=5\) and \(z=4\). After ordering the two factors by size of digit-length, the only admissible triples are

$ (x,y,z)\in\{(1,4,4),(2,3,4)\}. $

That exact deduction explains why the implementations search only the cases \(1\)-digit \(\times\) \(4\)-digit and \(2\)-digit \(\times\) \(3\)-digit. No other digit pattern can succeed.

The pandigital condition as a digit-usage invariant

For any candidate \((a,b,p)\), scan the decimal digits of \(a\), then \(b\), then \(p\). The triple is valid if and only if three conditions all hold: no digit is \(0\), no digit is repeated, and exactly nine digits are seen in total. Once those three conditions are satisfied, the digit set must be exactly \(\{1,2,\dots,9\}\).

The implementations encode this with a ten-entry boolean table indexed by the digit. Encountering a zero or a repeated digit causes immediate rejection, so most bad candidates fail before the full scan is finished.

Why distinct products must be deduplicated

The problem asks for the sum of distinct products, not the sum over successful factorizations. This matters because one product can arise from more than one pandigital identity. A well-known example is

$12\times 483=5796,\qquad 42\times 138=5796.$

Both identities are valid, but the product \(5796\) must contribute only once. That is why the implementations store successful products in a set before taking the final sum.

Worked examples

The positive checkpoint

$39\times 186=7254$

belongs to the \((2,3,4)\) case. Its digits are \(3,9,1,8,6,7,2,5,4\): there is no zero, no repetition, and the total count is nine, so it is valid.

The negative checkpoint

$12\times 34=408$

fails immediately because the product contains the digit \(0\). It also has only \(2+2+3=7\) digits altogether, so it cannot possibly be a 1-to-9 pandigital identity.

How the Code Works

Enumerating the only viable search regions

The C++, Python, and Java implementations run two nested-loop searches matching the two digit patterns above. The first search tests every \(a\in\{1,\dots,9\}\) against every four-digit \(b\in\{1234,\dots,9876\}\). The second tests every two-digit \(a\in\{12,\dots,98\}\) against every three-digit \(b\in\{123,\dots,987\}\). This removes impossible factor-length shapes such as \(3\)-digit \(\times\) \(3\)-digit before the digit checker is ever called.

Validating digits with a shared test

For each pair, the implementation computes \(p=ab\) and feeds \(a\), \(b\), and \(p\) into the same digit-usage test. The loops deliberately keep simple rectangular ranges instead of pre-filtering zeros or repeated digits inside the factors; the shared validator rejects those cases in constant time. A wrong product length is also handled naturally: if the combined digit count is not exactly nine, the candidate fails at the end of the scan.

Deduplication, summation, and sanity checks

Whenever a candidate passes the digit test, its product is inserted into a set. After both searches finish, the program sums the set elements to obtain the required answer. Before the main computation, each implementation also performs two small checkpoints: one known valid pandigital identity and one known invalid identity.

Complexity Analysis

The first search examines \(9\times 8643=77{,}787\) pairs, and the second examines \(87\times 865=75{,}255\) pairs, so the total number of tested products is \(153{,}042\). Each test performs one multiplication and a scan of at most ten decimal digits, so the work per candidate is \(O(1)\). For this fixed problem instance, the running time is therefore tiny.

The digit validator itself uses constant working memory. The only growing structure is the set of successful products, and for Problem 32 that set remains very small. In practice the computation completes essentially instantly.

Footnotes and References

1. Problem page: Project Euler 32 - Pandigital products
2. Pandigital numbers: Wikipedia - Pandigital number
3. Decimal positional notation: Wikipedia - Positional notation
4. Sets and distinct elements: Wikipedia - Set (mathematics)