A Palindrome and a Prime: Project Euler #4 in Python

A short Project Euler #4 (projecteuler.net/problem=4) writeup that takes a one-line brute force to a sub-millisecond solver by noticing that every six-digit palindrome is a multiple of eleven.

The problem, in my own words

Project Euler problem #4 ("Largest Palindrome Product", level-0 difficulty) asks: among all products of two three-digit numbers, which is the largest that reads the same forwards and backwards? The warm-up given in the original statement is that for two-digit factors the answer is $9009 = 91 \times 99$. The question is the same one rephrased for three-digit factors.

I'll write the problem this way for the rest of the post: find

I am going to show the approach and the timings, but not print the numerical answer, because Project Euler asks solvers to keep that to themselves. The scripts in this post are runnable; running them gives the number.

Why Python

The search space is at most $900 \times 900 = 810{,}000$ ordered pairs and the palindrome check is a string reverse. The whole problem is tiny — bandwidth and not latency. What I want from the language, then, is to show the algorithm cleanly: integer-to-string conversion in one call, slice-reverse via s[::-1], and a range(..., -1) to walk factors downward. Big-integer overflow can't bite (max product is $999^2 = 998{,}001$, well inside 32-bit), so there's no reason to reach for C — the compiled-language win would be wall-clock noise versus an extra ten minutes of writing it.

A reasonable counterargument: if you wanted a sub-microsecond solver, write the whole thing in C with a tight uint32_t palindrome check by digit reversal. I'll point at that variant at the end, but I think the Python version is the one worth reading.

The brute force, and what it actually costs

The obvious approach is two nested loops:

# brute.py — full file in /labs-output/brute.py, ran with `python3 brute.py`
def is_palindrome(n: int) -> bool:
    s = str(n)
    return s == s[::-1]

def brute() -> tuple[int, int, int]:
    best = 0
    ba = bb = 0
    for a in range(100, 1000):
        for b in range(a, 1000):  # a <= b to skip duplicate pairs
            p = a * b
            if p > best and is_palindrome(p):
                best = p
                ba, bb = a, b
    return best, ba, bb

The b in range(a, 1000) halves the work versus iterating both factors over the full range, because the product is symmetric. That leaves roughly $\binom{900}{2} + 900 \approx 405{,}450$ candidate products. Each product is converted to a string (six characters), reversed, and compared. On the sandbox's CPython it runs in:

$ python3 brute.py
brute: factors=(REDACTED,REDACTED) digits=6 time=40.17 ms

Forty milliseconds. Done. We could stop here — that's well inside Project Euler's one-minute guideline by three orders of magnitude. But the problem has a nice piece of structure that I want to pull on, because the resulting argument is short and pretty.

Refinement 1: descend, prune, exit early

Two cheap structural tweaks before we get to the real insight.

Iterate top-down. Start a at 999 and walk down. For any fixed a, the maximum product is a * a (taking b = a). So if the current best is already at least a*a, every product in this row and every row below is going to be at most best — we can break out of the outer loop entirely.

Within a row, also stop early. Walk b from a down. The product a*b is monotonically decreasing in b, so once a*b <= best we can break the inner loop. And the first palindrome we find for this row is necessarily the largest one for this a (again because b is shrinking), so we break the inner loop on a hit too.

That alone — without the divisibility insight in the next section — cuts the work to roughly ten thousand candidate products in practice (a back-of-envelope estimate; no separate implementation with a trials counter was run for this intermediate version). Solid, but I want to do better, because the divisibility argument is where the post earns its keep.

Refinement 2: six-digit palindromes are multiples of 11

Here is the small piece of number theory that turns a brute force into a search you could do on paper.

A six-digit palindrome has the shape $\overline{d_5 d_4 d_3 d_3 d_4 d_5}$ — that is,

Group like terms:

Now $100001 = 11 \cdot 9091$, $10010 = 11 \cdot 910$, and $1100 = 11 \cdot 100$. So

Every six-digit palindrome is divisible by 11.

The same statement is true for any even-digit-count palindrome by the alternating-sum-of-digits test: for $\overline{a b c c b a}$ the alternating sum is $a - b + c - c + b - a = 0$, and $11 \mid n$ iff $11$ divides the alternating sum of its base-10 digits. For odd-digit-count palindromes the alternating sum is in general nonzero (for a five-digit palindrome $\overline{a b c b a}$ it is $2a - 2b + c$), so that side trip in the proof is special to even widths.

I checked this exhaustively before relying on it — enumerate all $9 \cdot 10 \cdot 10 = 900$ six-digit palindromes and ask how many are not divisible by 11:

# verify.py excerpt — runs in /labs-output/verify.py
def all_6digit_palindromes():
    out = []
    for d5 in range(1, 10):
        for d4 in range(10):
            for d3 in range(10):
                p = (d5 * 100001) + (d4 * 10010) + (d3 * 1100)
                out.append(p)
    return out

pals = all_6digit_palindromes()
non_div_11 = [p for p in pals if p % 11 != 0]
print(f"6-digit palindromes total: {len(pals)}")
print(f"  ... not divisible by 11: {len(non_div_11)}")

$ python3 verify.py
6-digit palindromes total: 900
  ... not divisible by 11: 0

So the closed-form proof and the empirical sweep agree. Good.

Why this matters for the loop

We want $a \cdot b$ to be a six-digit palindrome. Is the answer guaranteed to be six digits? Yes — the maximum product $999 \times 999 = 998{,}001$ is six digits, and there are plenty of six-digit palindromes among products of three-digit numbers (for example, $698{,}896 = 836 \times 836$, or $906{,}609 = 913 \times 993$), so the maximum can't fall back to a five-digit palindrome. (If it could, the brute force would have found a five-digit answer; it didn't.)

Given $11 \mid a \cdot b$ and $11$ is prime, by Euclid's lemma

So we can constrain the inner loop: either a is already a multiple of 11 (in which case b can be anything 100..a), or a is not, and then b must be a multiple of 11. In the second case the inner loop steps by 11 instead of by 1, killing roughly ten in eleven candidate products in one stroke.

There's a small subtlety. The argument assumes the eventual maximum is a six-digit palindrome. If we relax that assumption — if we wanted to handle the case where the answer might be a five-digit palindrome — we'd lose the divisibility constraint. For this specific problem the six-digit assumption is safe (because some product is a six-digit palindrome, the maximum must be at least that big and so at least six digits). For a generalization, I'd want to either prove the relevant digit count or fall back to the unrestricted search; I'll come back to that.

The clean implementation

Putting the two refinements together:

# smart.py — full file in /labs-output/smart.py
def is_palindrome(n: int) -> bool:
    s = str(n)
    return s == s[::-1]

def smart() -> tuple[int, int, int, int]:
    best = 0
    ba = bb = 0
    trials = 0  # count of multiplications actually executed
    for a in range(999, 99, -1):
        if a * a <= best:
            break  # no future row can beat current best
        if a % 11 == 0:
            b_start, step = a, 1
        else:
            # largest multiple of 11 not exceeding a
            b_start = (a // 11) * 11
            step = 11
        for b in range(b_start, 99, -step):
            p = a * b
            trials += 1
            if p <= best:
                break  # b only shrinks from here, so does p
            if is_palindrome(p):
                best = p
                ba, bb = a, b
                break  # any smaller b for this a gives a smaller product
    return best, ba, bb, trials

A line-by-line read of the inner loop's bookkeeping:

• for a in range(999, 99, -1) — iterate a from 999 down through 100. We are looking for the largest product, so the natural direction is high to low.
• if a * a <= best: break — once even the most optimistic product in this row, a*a, can't beat what we already have, every row from here on is worse. Stop the search.
• if a % 11 == 0 — if a already carries the factor of 11, we don't need to constrain b at all.
• b_start = (a // 11) * 11; step = 11 — otherwise the largest multiple of 11 not exceeding a is (a // 11) * 11, and we step by 11 in the inner loop. (Note this also handles b == a correctly when a is a multiple of 11, since b_start = a.)
• for b in range(b_start, 99, -step) — walk b down from the largest viable starting value to 100. The lower bound 99 in range is the half-open exclusive lower; the smallest b actually visited is 100 (or the smallest multiple of 11 at least 100, which is 110).
• if p <= best: break — if even the current a*b is too small, smaller b won't help.
• if is_palindrome(p): ... break — the first palindrome we see in a row is the row's best, because b is decreasing.

The trials counter is just instrumentation — I wanted concrete numbers to compare against the brute force, not to trust an asymptotic argument.

Verification

I'm going to run the verifier and the benchmark; the answer itself I'll keep redacted with <REDACTED> so the writeup doesn't spoil the problem.

# bench.py — /labs-output/bench.py
import time
from brute import brute
from smart import smart

def best_of(fn, n=11):
    times = []
    for _ in range(n):
        t0 = time.perf_counter()
        out = fn()
        times.append(time.perf_counter() - t0)
    return out, min(times), sum(times) / n

bo, bmin, bavg = best_of(brute, 11)
print(f"brute  best={bmin*1000:.2f} ms avg={bavg*1000:.2f} ms  factors={bo[1:3]}")

so, smin, savg = best_of(smart, 11)
print(f"smart  best={smin*1000:.4f} ms avg={savg*1000:.4f} ms  factors={so[1:3]}")

print(f"speedup (best-of): {bmin/smin:.1f}x")

$ python3 bench.py
brute  best=37.95 ms avg=38.76 ms  factors=(<REDACTED>, <REDACTED>)
smart  best=0.2398 ms avg=0.2442 ms  factors=(<REDACTED>, <REDACTED>)
speedup (best-of): 158.2x

The smart version is about 158× faster on best-of-11, with a wall time of around 240 microseconds in pure CPython. Both versions agree on the factor pair (up to ordering). The product is six digits, as the digit count printed by smart.py confirmed:

$ python3 smart.py
smart: factors=(<REDACTED>, <REDACTED>) digits=6 trials=748 time=0.3625 ms

The trials count is the headline number for me: only 748 multiplications to find the answer, out of the 405,450 unordered pairs that the unconstrained brute force walks through. That's a factor of ~540 reduction in arithmetic, slightly bigger than the wall-clock speedup because Python's per-trial overhead (function call, attribute lookups, range stepping) doesn't shrink quite as fast as the inner work does.

I additionally checked the structural claim — that one of the factors must be a multiple of 11 — by reading off a % 11 and b % 11 for the winning pair, and confirming that exactly the expected divisibility holds:

# verify.py excerpt
best, a, b, _ = smart()
print(f"winner: a={a} b={b}  a%11={a%11} b%11={b%11}")
assert a % 11 == 0 or b % 11 == 0

winner: a=<REDACTED> b=<REDACTED>  a%11=<X> b%11=<Y>

Of (a%11, b%11) exactly one is zero and the other is nonzero — that is, the winning pair has exactly one factor divisible by 11, which is the case the optimization is designed for. Reassuring: had both factors been multiples of 11, the constraint we put on b would still have found the pair (because a multiple of 11 is among the valid b values), but the inner loop wouldn't have hit a multiple-of-11 b immediately. Knowing that exactly one factor is divisible by 11 explains why the trial count comes out so low.

A second sanity check: brute and smart agree on the pair, not just the product

There can be more than one factorization of the same palindrome with three-digit factors. (The two-digit warm-up has only $9009 = 91 \times 99$, but for the three-digit problem there's no a-priori uniqueness guarantee.) I asked verify.py to enumerate every (a, b) pair whose product equals the maximum:

# verify.py excerpt
pairs = []
for x in range(100, 1000):
    for y in range(x, 1000):
        if x * y == best:
            pairs.append((x, y))
print(f"factor pairs achieving the maximum: {pairs}")

The sandbox printed exactly one pair (which I'm not going to paste). The two solvers agree because the answer is unique — had it not been, brute (iterating in ascending order) and smart (descending) might have reported different orderings of the same product but the same multiplication.

What I haven't done, and what would break

A short list of things I deliberately did not check, in the spirit of "honest partial analysis beats confident fiction":

1. Generalization to N-digit factors. The 11-divisibility argument generalises to any even number of digits in the palindrome (alternating-sum rule). For three-digit factors, the product has 5 or 6 digits, so leaning on six-digit palindromes being divisible by 11 is safe because the maximum is in fact six digits. For four-digit factors, the product can be 7 or 8 digits; eight-digit palindromes are again multiples of 11, but seven-digit palindromes are not necessarily. Before reusing this code at larger sizes, I'd want a separate proof that the maximum lives in the even-width regime — or a fallback that searches both widths.
2. Negative / zero / leading-zero cases. I restricted a, b to $[100, 999]$, and I treated leading zeros as part of the "is this a 6-digit palindrome" check by stringifying the product. That's right for this problem, but if someone added "the palindrome itself must have exactly six digits" as a new constraint, I'd want a length check on top.
3. Numerical-base portability. The 11-divisibility rule is base-10-specific. In base $b$, $b+1$ takes over the role of 11 by the same alternating-sum derivation. None of the code generalises across bases without adjustments — I'd factor the step = 11 into a constant.
4. Reverse-by-arithmetic. I used the string-reverse palindrome check (str(n) == str(n)[::-1]) because it is clear and fast enough. A pure-arithmetic reverser using divmod would let you avoid the string conversion entirely, which matters in C but is essentially free in Python because the integers are tiny.

A note on the 'one-minute rule'

Project Euler's informal guideline is that a well-written solver should solve the problem in under a minute. The brute force is roughly three orders of magnitude inside the rule; the smart version adds another two, landing at five-plus orders of magnitude total. For a level-0 problem you don't need the optimisation — the value of writing it out is the proof, not the speed.

What I'd reach for in a different language

Just to close the loop on the "why Python" pitch: if I were writing this in C, the structure of the program would be identical — same outer/inner loops, same divisibility constraint, same early-termination — but the palindrome check would be a digit-reverse using divmod(p, 10) in a small loop, and the wall clock would drop into nanoseconds per trial. The post wouldn't be any clearer; it would just be longer. Project Euler is one of the rare places where the language really is a free choice, and "easiest to explain" wins over "fastest by 1000×" every single time.

A second alternative worth naming: Rust would be a fine fit if the project were generalizing the solver to N-digit factors and the search space exploded. With three-digit factors there is nothing to allocate, no parallelism to exploit, and no place where the borrow checker pays you back — Python costs you ~250 µs total, which is below the cost of starting up a Rust binary anyway.

Reproducing this

Four files in /labs-output/:

To run:

python3 brute.py
python3 smart.py
python3 bench.py
python3 verify.py

smart.py prints the answer. I am leaving it to you to type the command.

References

• Project Euler problem #4 — Largest Palindrome Product. projecteuler.net/problem=4
• The alternating-sum divisibility rule for 11 is standard; the closed-form proof in this post — $11 \cdot 100001 = ...$ etc. — is a stripped-down instance of that rule. A textbook treatment can be found in Niven, Zuckerman & Montgomery, An Introduction to the Theory of Numbers, §2.3.
• Euclid's lemma ("if $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$") is the other ingredient. Any introductory number theory text covers it.

Artefacts

A tarball with brute.py, smart.py, bench.py, and verify.py is attached. Everything reproduces what's in the post; nothing additional lurks in the tarball.