Detailed mathematical approach

Problem Summary

For a given digit count \(d\), define

$L=10^{d-1},\qquad H=10^d-1.$

Write \(\operatorname{Pal}(x)\) for the statement that \(x\) is a decimal palindrome. The target quantity is then

$M_d=\max\{ab \mid L \le a,b \le H,\ \operatorname{Pal}(ab)\}.$

In the original Project Euler instance \(d=3\), so both factors are three-digit numbers, but the implementations are structured for a general input \(d \ge 1\). The difficulty is not describing the candidate set; it is searching that set without wasting time on products that cannot possibly beat the current record.

Mathematical Approach

The solution uses three ideas that are completely specific to this problem: the search space can be reduced to an upper triangle because multiplication is commutative, palindromicity is a digit-symmetry predicate, and descending order gives monotone bounds that justify early termination. There is no recurrence here; the central invariant is a best-so-far lower bound on the true optimum.

The Search Space Is a Triangle, Not a Square

If \((a,b)\) is admissible, then so is \((b,a)\), and both yield the same product. It is therefore enough to search

$T_d=\{(a,b)\mid L \le b \le a \le H\}.$

Every valid factorization appears exactly once in \(T_d\): if a pair satisfies \(a \lt b\), we simply swap the factors. Hence

$M_d=\max\{ab \mid (a,b)\in T_d,\ \operatorname{Pal}(ab)\}.$

This halves the search space up to lower-order terms, reducing the candidate count from \(N^2\) ordered pairs to \(N(N+1)/2\), where \(N=H-L+1=9\cdot 10^{d-1}\).

The Palindrome Test Is Decimal Symmetry

If a non-negative integer has decimal expansion

$x=\sum_{i=0}^{m} c_i 10^i,$

then \(x\) is palindromic exactly when

$c_i=c_{m-i}\qquad(0 \le i \le m).$

So the mathematical predicate is simply mirror symmetry of digits around the center. Because a product of two \(d\)-digit numbers has at most \(2d\) digits, checking \(\operatorname{Pal}(x)\) costs only \(O(d)\) time. The implementations realize this with decimal strings: Python compares the string with its reversal, while C++ and Java compare mirrored characters from the two ends.

Descending Order Produces Two Valid Pruning Inequalities

For a fixed first factor \(a\), the products \(ab\) decrease as \(b\) decreases. Across rows, the largest value attainable with first factor \(a\) is \(aH\), and these row maxima also decrease as \(a\) decreases.

Let \(B\) denote the largest palindromic product found so far. Then the first key bound is

$aH \lt B.$

If this happens, then every remaining pair with first factor \(a' \le a\) satisfies \(a'b \le aH \lt B\), so no later row can improve the record. The outer loop may stop.

The second key bound is

$ab \le B.$

At that moment, every later candidate in the same row has the form \(ab'\) with \(b' \le b\), hence \(ab' \le ab \le B\). So the rest of the current row can be skipped. These two monotonicity facts are the mathematical reason the search is fast in practice.

Worked Example: Why the Two-Digit Case Stops Early

For \(d=2\) we have \(L=10\) and \(H=99\). The scan starts at the top row \(a=99\), examining

$99\cdot 99,\ 99\cdot 98,\ 99\cdot 97,\ \dots$

Eventually it reaches

$99\cdot 91=9009,$

which is palindromic, so the running record becomes \(B=9009\). Now inspect what happens when the outer loop would move down to \(a=90\): the largest product still available in that entire row is

$90\cdot 99=8910 \lt 9009.$

Therefore every row with first factor \(90\) or smaller is already hopeless, and the outer loop can terminate. The famous two-digit answer is not just a checkpoint; it is also a clean demonstration of how the pruning logic works.

Even-Length Palindromes Are Multiples of 11

A classical fact about decimal palindromes is that every palindrome with an even number of digits is divisible by 11. Suppose

$x=\sum_{i=0}^{2k-1} c_i 10^i,\qquad c_i=c_{2k-1-i}.$

Since \(10\equiv -1 \pmod{11}\), we obtain

$x\equiv \sum_{i=0}^{2k-1} c_i(-1)^i \pmod{11}.$

Now pair the terms with indices \(i\) and \(2k-1-i\). Their contribution is

$c_i(-1)^i+c_{2k-1-i}(-1)^{2k-1-i}=c_i\bigl((-1)^i+(-1)^{2k-1-i}\bigr)=0,$

because the digits are equal and the signs are opposite. Summing over all pairs gives \(x\equiv 0 \pmod{11}\).

In the three-digit problem this means every six-digit palindromic candidate is a multiple of 11, so a specialized solver may insist that one factor be divisible by 11. The present implementations deliberately keep the simpler general scan, but this theorem explains a well-known optimization for the same task.

How the Code Works

Build the Interval of \(d\)-Digit Factors

The implementations first compute the lower and upper endpoints \(L\) and \(H\). Python uses powers of ten directly. C++ and Java arrive at the same interval by repeated multiplication to form \(10^{d-1}\), then subtract one from the next power of ten to obtain the upper endpoint.

Traverse the Triangle in Descending Order

After the interval is known, the implementation loops downward over the first factor and, inside each row, loops downward over the second factor starting from the diagonal \(b=a\). This realizes the triangular search region \(T_d\) exactly once.

Before spending time on the palindrome predicate, the code first asks whether the current product can still beat the running record. If the answer is no, one of the two pruning inequalities triggers and the relevant loop ends immediately. Only products that still have a mathematical chance to improve the answer are tested for decimal symmetry.

All three implementations also verify the known two-digit case by checking that the computed value is \(9009\). That small checkpoint is useful because any off-by-one error in the interval bounds or loop directions would break it immediately.

Complexity Analysis

Let \(N=H-L+1=9\cdot 10^{d-1}\). Because only the triangle \(b \le a\) is scanned, the worst-case number of candidate products is

$\frac{N(N+1)}{2}=\Theta(N^2)=\Theta(10^{2d}).$

Each palindrome test inspects at most \(2d\) decimal digits, so a precise worst-case time bound is

$O(d\,10^{2d}).$

If \(d\) is treated as fixed, as in the original three-digit problem, this is simply quadratic in the size of the factor range. In practice the runtime is much smaller than the worst-case bound because the running record rises quickly and then excludes entire rows and long suffixes of rows. Memory use is \(O(d)\) for the temporary decimal representation, which is effectively \(O(1)\) when \(d\) is fixed.

Footnotes and References

1. Project Euler, Problem 4: Largest palindrome product
2. Palindromic number: Wikipedia
3. Divisibility by 11: Wikipedia
4. Decimal palindromes, OEIS A002113: OEIS
5. Positional notation: Wikipedia