Detailed mathematical approach

Problem Summary

We seek the largest 10-digit number \(P\) that uses the digits \(0,1,\dots,9\) exactly once and can be written as a concatenation of decimal products

$P=(m x_1)\Vert(m x_2)\Vert\cdots\Vert(m x_t),\qquad t\ge 2,$

for some positive integer multiplier \(m\) and positive integers \(x_1,\dots,x_t\). The input-side concatenation

$I=m\Vert x_1\Vert x_2\Vert\cdots\Vert x_t$

must also be 0-to-9 pandigital. All numbers are interpreted in ordinary decimal notation, so a multi-digit block may not begin with 0.

Mathematical Approach

The crucial simplification is to search from the output side. Instead of guessing \(m\) and the multiplicands first, the implementation scans possible 10-digit pandigital outputs in descending order and asks whether each one can be decomposed into valid product blocks.

From a two-sided identity to a one-sided search

Take a candidate output string \(Y\). If \(Y\) is valid, then some choice of block boundaries turns it into decimal integers

$Y=p_1\Vert p_2\Vert\cdots\Vert p_t,$

where each block satisfies

$p_i=m x_i.$

So the entire problem becomes: choose a 10-digit pandigital output \(Y\), choose block boundaries, and check whether there exists a common multiplier \(m\) making the reconstructed input \(m\Vert x_1\Vert\cdots\Vert x_t\) pandigital as well.

Choosing the product blocks

A 10-digit string has 9 gaps between consecutive digits. Any nonempty subset of those gaps can be declared to be block boundaries, so there are

$2^9-1=511$

nontrivial partitions to test. This matches the decimal concatenation exactly: every valid identity produces one of these contiguous blockings, and every blocking gives a concrete list of product candidates \(p_1,\dots,p_t\).

Whenever a block would have more than one digit and start with 0, that partition is impossible in standard decimal notation and is discarded immediately.

The gcd invariant for the common multiplier

Once a partition \(p_1,\dots,p_t\) is fixed, the multiplier is heavily constrained. Since \(p_i=m x_i\) for every \(i\), the multiplier must divide every block, hence

$m\mid p_i\quad\text{for all }i,$

and therefore

$m\mid g,\qquad g=\gcd(p_1,p_2,\dots,p_t).$

This is the key invariant used by all three implementations. It turns an open-ended search over possible multipliers into a finite divisor search. For a fixed partition, every feasible multiplier must be a divisor of one specific integer \(g\).

Reconstructing the input side uniquely

The gcd condition is not only necessary; it also tells us exactly what to test. If \(d\) is a divisor of \(g\), then the only possible multiplicands are

$x_i=\frac{p_i}{d}.$

So a fixed partition and a fixed divisor \(d\mid g\) produce exactly one candidate input concatenation:

$I_d=d\Vert\frac{p_1}{d}\Vert\frac{p_2}{d}\Vert\cdots\Vert\frac{p_t}{d}.$

No further freedom remains. Therefore the validation step is simple: compute \(g\), enumerate its divisors, rebuild \(I_d\), and check whether \(I_d\) uses the digits \(0\) through \(9\) exactly once. If it does, the chosen output partition is a genuine solution.

Worked example

The classic 1-to-9 sample already shows the whole mechanism. Consider

$763859124=7638\Vert59124.$

With this partition,

$g=\gcd(7638,59124)=6.$

So the only possible common multipliers are the divisors of 6. Testing \(d=6\) gives

$x_1=\frac{7638}{6}=1273,\qquad x_2=\frac{59124}{6}=9854,$

hence the input-side concatenation

$6\Vert1273\Vert9854=612739854,$

which is 1-to-9 pandigital. Problem 170 asks for the same phenomenon with all ten digits \(0,\dots,9\) used exactly once. The code applies the same gcd-and-divisors argument to every 10-digit pandigital output candidate.

Why the first accepted output is the maximum

The outer search visits pandigital outputs in descending order. Because every candidate is a 10-digit number with nonzero leading digit, descending lexicographic order is the same as descending numeric order. The search is exhaustive for each output: every valid identity determines a unique output string, one of the 511 partitions of that string, and a multiplier among the divisors of the partition gcd. So when the algorithm finds the first valid output, no larger valid output can still be waiting later in the scan.

How the Code Works

Enumerating output candidates

The C++, Python, and Java implementations all iterate over the digits \(9,8,\dots,0\) in descending permutation order and interpret each permutation as a candidate output string. Any permutation beginning with 0 is skipped, since it would not represent a 10-digit number.

Testing every decimal partition

For each output candidate, the implementation inspects every nonempty split mask on the 9 digit gaps. Each mask determines a contiguous partition into product blocks. Partitions that create a multi-digit block with a leading zero are rejected on the spot, and the remaining blocks are parsed as decimal integers.

Filtering multipliers with the gcd

After forming the product blocks, the implementation computes their gcd. It then enumerates the divisors of that gcd in descending order. For each divisor, it divides every block by that candidate multiplier, concatenates the multiplier and the resulting quotients, and performs a pandigital check on the 10-character input string.

If the reconstructed input is 0-to-9 pandigital, the output candidate is valid and the whole search stops immediately. The C++ and Java versions walk the descending permutations directly; the Python version reaches the same order by generating permutations and scanning them in reverse-sorted order. The mathematical test is identical in all three languages.

Complexity Analysis

There are at most \(10!=3{,}628{,}800\) permutations of the digits \(0,\dots,9\), although candidates with leading zero are skipped. For each candidate output, the implementation examines all

$2^9-1=511$

nontrivial contiguous partitions. For one partition, it computes a gcd over a small number of blocks, enumerates the divisors of that gcd by trial division, and performs constant-size string checks because both the input and output concatenations always have length 10.

If \(M\) denotes the largest block value in a partition, a simple worst-case description is

$O\!\left(10!\cdot 2^9\cdot \sqrt{M}\right),$

with \(M\le 987654321\) because at least one split is always present. The memory usage is \(O(1)\) apart from short temporary lists of blocks and divisors. In practice the runtime is much smaller than the pessimistic bound because the scan terminates as soon as the largest valid output is found.

Footnotes and References

1. Project Euler problem page: Project Euler 170
2. Pandigital numbers: Wikipedia - Pandigital number
3. Permutations and lexicographic order: Wikipedia - Permutation
4. Greatest common divisor: Wikipedia - Greatest common divisor
5. Euclidean algorithm: Wikipedia - Euclidean algorithm