Detailed mathematical approach

Problem Summary

We seek the smallest positive integer \(x\) such that the decimal digits of \(x\), \(2x\), \(3x\), \(4x\), \(5x\), and \(6x\) are exactly the same up to reordering. In other words, each multiple from \(2x\) through \(6x\) must be a digit permutation of the original number. The smallest such value is \(142857\), but the point of the problem is to justify why a direct search is so small and why a simple exact test is enough.

Mathematical Approach

The three implementations all rely on one exact invariant: two integers satisfy the condition precisely when their decimal digits have the same multiset. Everything else is a consequence of that observation.

Digit Signatures Give the Exact Condition

Define the digit signature \(\sigma(n)\) to be the string obtained by sorting the decimal digits of \(n\) into nondecreasing order. Then

$x \text{ and } y \text{ are digit permutations } \Longleftrightarrow \sigma(x)=\sigma(y).$

So Problem 52 is equivalent to the system

$\sigma(x)=\sigma(2x)=\sigma(3x)=\sigma(4x)=\sigma(5x)=\sigma(6x).$

This formulation is stronger than checking only digit sums or congruences: it remembers the full multiplicity of every decimal digit, including zeros.

The Same-Length Window

If \(x\) has \(d\) decimal digits, then every permutation of its digits also has \(d\) digits. In particular, \(6x\) must still have \(d\) digits. Therefore any \(d\)-digit candidate must satisfy

$10^{d-1} \le x \le \left\lfloor \frac{10^d-1}{6} \right\rfloor.$

This is the main structural restriction of the problem. It says that only the first sixth of each \(d\)-digit block can possibly work. For a fixed digit length, the number of candidates is

$\left\lfloor \frac{10^d-1}{6} \right\rfloor - 10^{d-1} + 1.$

For \(d=6\), this gives the interval \(100000 \le x \le 166666\), which contains only \(66667\) candidates. The actual implementations do not hard-code this bound, but it explains why the first solution appears in a very narrow region.

A Useful Consequence Modulo \(9\)

Permuting decimal digits preserves their sum, so if \(\sigma(kx)=\sigma(x)\), then \(kx\) and \(x\) have the same digit sum and hence the same residue modulo \(9\). Taking \(k=2\) gives

$2x \equiv x \pmod 9,$

so every valid solution must satisfy

$x \equiv 0 \pmod 9.$

This is only a necessary condition, not a full characterization. Many multiples of \(9\) still fail the signature test, so the implementations keep the exact sorted-digit comparison rather than relying on weaker filters.

Worked Examples

The checkpoint example used by the implementations is \(125874\), because

$2 \cdot 125874 = 251748,$

and both numbers have the same sorted signature \(124578\). That shows the basic idea on a single multiple.

The complete solution is

$x=142857,$

for which

$2x=285714,\quad 3x=428571,\quad 4x=571428,\quad 5x=714285,\quad 6x=857142.$

Sorting the digits of any of these six numbers always gives the same signature \(124578\). Because the search is performed in increasing order, the first successful candidate is automatically the smallest possible answer.

How the Code Works

Shared Search Pattern

The C++, Python, and Java implementations all follow the same structure. They start at \(x=1\) and test candidates in increasing order. For each candidate, the implementation sorts the digits of \(x\) once, then compares that signature with the sorted digits of \(2x\), \(3x\), and so on up to the chosen upper multiplier. As soon as one comparison fails, the candidate is rejected immediately and the search moves on.

This means the code uses the exact criterion \(\sigma(kx)=\sigma(x)\) directly. It does not build frequency tables, it does not pre-split the search by digit length, and it does not use congruence pruning. The benefit is simplicity: the code is short, and the early break makes the brute-force search fast enough.

Checkpoint and Configurability

All three implementations also include a small built-in validation step. Before solving the main problem, they verify that \(125874\) and \(251748\) really do have the same sorted digits. There is also an optional command-line setting that replaces the default upper multiplier \(6\) by a user-specified value at least \(2\), so the same routine can search for analogous questions such as matching digits for \(2x\) through \(4x\).

Complexity Analysis

Let \(M\) be the largest multiplier being checked and let \(A\) be the first solution for that choice. The implementations test every candidate from \(1\) through \(A\). If \(D\) is the number of decimal digits of \(A\), then each signature computation sorts at most \(D\) characters, so one comparison costs \(O(D \log D)\). In the worst case, a candidate performs \(M\) such signature computations, giving total time

$O(A\,M\,D\log D).$

For the default problem, \(M=6\), \(A=142857\), and \(D=6\), so the workload is tiny in practice. The extra space is \(O(D)\) for the temporary digit strings, or constant with respect to the number of candidates.

Footnotes and References

1. Problem page: Project Euler 52 - Permuted Multiples
2. Permutation: Wikipedia - Permutation
3. Decimal representation: Wikipedia - Decimal
4. Congruence modulo \(9\): Wikipedia - Congruence relation
5. Cyclic number: Wikipedia - Cyclic number