Detailed mathematical approach

Problem Summary

For each base \(B\in[9,18]\), the digits \(0,1,\dots,B-1\) must be distributed exactly once across three positive integers \(a\), \(b\), and \(c\), with no leading zero. We seek all triples satisfying

$a^2+ab+b^2=c^2,\qquad c\lt a+b.$

The equation is symmetric in \(a\) and \(b\), and the left-hand side is strictly larger than both \(a^2\) and \(b^2\), so every valid solution may be treated in ordered form \(a\lt b\lt c\). For each base we sum all valid values of \(c\), then add those sums over bases \(9\) through \(18\).

Mathematical Approach

The implementation constructs the numbers from left to right. A search state contains a current prefix for each of the three numbers and the set of digits already used. The key mathematics is what lets the search discard entire subtrees long before all digits are assigned.

Step 1: Organize the search by balanced digit lengths

Write

$B=3k+r,\qquad r\in\{0,1,2\}.$

The solver arranges the final digit lengths as

$ (\ell_a,\ell_b,\ell_c)= \begin{cases} (k,k,k), & r=0,\\ (k,k,k+1), & r=1,\\ (k,k+1,k+1), & r=2. \end{cases} $

This is the balanced way to spend all \(B\) digits, and it matches the magnitude restriction \(b\lt c\lt a+b\): \(c\) must be slightly larger than \(b\), but it cannot be dramatically larger. The search therefore starts with one leading digit in each number when \(r=0\), with one extra leading digit already placed in \(c\) when \(r=1\), and with one extra leading digit already placed in both \(b\) and \(c\) when \(r=2\).

Step 2: Extend prefixes while preserving order and digit uniqueness

If the current prefixes are still called \(a\), \(b\), and \(c\), then appending one new base-\(B\) digit to each gives

$a'=aB+d_a,\qquad b'=bB+d_b,\qquad c'=cB+d_c,$

where \(d_a\), \(d_b\), and \(d_c\) are distinct unused digits. Only the leading digits are forced to be nonzero; later appended digits may be zero.

The ordering established at the start is preserved automatically. Indeed, if \(a\lt b\), then for any digits \(d_a,d_b\in\{0,\dots,B-1\}\),

$aB+d_a\le aB+(B-1) \lt (a+1)B\le bB\le bB+d_b.$

So once a prefix state is generated in sorted order, every deeper state stays sorted as well. This prevents duplicate counting caused by the symmetry between \(a\) and \(b\).

Step 3: Use interval bounds to test whether a prefix can still succeed

Suppose there are \(r\) more digits to append to each number, and set

$p=B^r.$

Then the final completed values must lie in the intervals

$A\in[ap,\ ap+p-1],\qquad B\in[bp,\ bp+p-1],\qquad C\in[cp,\ cp+p-1].$

Because the quadratic form \(x^2+xy+y^2\) is increasing for positive \(x\) and \(y\), the smallest and largest possible left-hand sides over this state are

$L_{\min}=(ap)^2+(bp)^2+(ap)(bp),$

$L_{\max}=(ap+p-1)^2+(bp+p-1)^2+(ap+p-1)(bp+p-1).$

Likewise, the right-hand side must stay inside

$R_{\min}=(cp)^2,\qquad R_{\max}=(cp+p-1)^2.$

A prefix can be extended only if two necessary conditions hold:

$cp \lt (ap+p-1)+(bp+p-1),$

$L_{\max}\ge R_{\min},\qquad L_{\min}\le R_{\max}.$

If either the triangle inequality range or the quadratic-form range fails, then no completion of that prefix can possibly work, so the entire branch is pruned immediately.

Step 4: Finish exactly when only two or three digits per number remain

Once the search has reached the point where only two digits remain for each number, there are exactly six unused digits left. At that point the implementation simply tests all \(6!=720\) ordered assignments of those digits to the three 2-digit tails and checks the full equation exactly.

When three digits remain for each number, the implementation uses a stronger filter. Write the final numbers as

$A=aB^3+a_t,\qquad B=bB^3+b_t,\qquad C=cB^3+c_t,$

where \(a_t\), \(b_t\), and \(c_t\) are 3-digit tails built from the remaining digits. If

$A^2+AB+B^2=C^2,$

then reducing modulo \(B^3\) yields the necessary congruence

$a_t^2+a_tb_t+b_t^2\equiv c_t^2\pmod{B^3}.$

So the solver precomputes all ordered 3-digit tails with distinct digits, groups candidate \(c_t\) values by their square residue modulo \(B^3\), and only combines tails whose digit masks are disjoint and whose residues satisfy the congruence. The full identity and \(c\lt a+b\) are then checked on the completed integers.

Worked Example: pruning a base-9 prefix

Take \(B=9\). Then \(9=3\cdot3\), so the final lengths are \((3,3,3)\). Suppose a search node has one-digit prefixes

$a=1,\qquad b=2,\qquad c=5,$

with two more digits still to append to each number. Then \(p=9^2=81\), so

$A\in[81,161],\qquad B\in[162,242],\qquad C\in[405,485].$

Now

$\max A+\max B=161+242=403,$

but

$\min C=405.$

Therefore every completion of this prefix would satisfy \(C\ge A+B\), which contradicts \(c\lt a+b\). The whole subtree below \((1,2,5)\) is discarded without trying any of the remaining six digits.

How the Code Works

The C++ and Java implementations follow the same search strategy. For each base they precompute powers of the base, generate the allowed initial prefix states for the relevant length pattern, and repeatedly append one digit to each number while keeping only the states that survive the interval test above.

If the search reaches the 2-digit finishing case, the implementation checks all \(720\) tail assignments directly. If it reaches the 3-digit finishing case, it precomputes all distinct 3-digit tails, buckets them by residue modulo \(B^3\), joins only mask-compatible residue matches, and then verifies the complete identity with exact integer arithmetic rather than floating point. The C++ implementation also parallelizes the independent bases \(9\) through \(18\) and includes an independent brute-force verification for base \(9\). The Python implementation is intentionally thin: it builds or reuses the compiled solver, runs it, and returns the parsed numeric result.

Complexity Analysis

A naive search would be essentially factorial in \(B\), because it would have to examine permutations of the \(B\) digits together with ways to split them among three numbers. The implemented method still has exponential worst-case behavior, but its practical cost is driven by the number of prefix states that survive pruning rather than by raw \(B!\).

For the finishing phase, the 2-digit case costs \(O(720)\) exact completions per live state. In the 3-digit case there are

$P(B,3)=B(B-1)(B-2)$

ordered tails to precompute, and the residue-based preprocessing is quadratic in that tail count up to the number of residue-compatible, mask-disjoint pairs and triples that survive. Memory usage is proportional to the live prefix states plus the stored tail tables. In the C++ version, distributing bases across worker threads improves wall-clock time but does not change the underlying search complexity.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=660
2. Pandigital numbers: Wikipedia — Pandigital number
3. Positional notation: Wikipedia — Positional notation
4. Branch and bound: Wikipedia — Branch and bound
5. Eisenstein integers and the related norm form: Wikipedia — Eisenstein integer