Project Euler 4: Searching Products from the Top for the Largest Palindrome

This is the fourth problem in the Project Euler series. Trying every case finishes quickly at this size, so the interesting question is not a faster formula but when a search is allowed to stop. We look at the largest products first and cut off the parts that cannot matter, and we prove properly that the answer is never hiding in what was cut off. The same reasoning keeps coming back in later problems.

Spoiler warning: this post contains a full solution and the answer. If you want to try it yourself first, start with the original problem. Posts in this series never carry ads, because the problem text is licensed under CC BY-NC-SA 4.0, which is non-commercial.

Problem

A palindromic number reads the same forwards and backwards. The problem’s example is that the largest palindrome you can make as the product of two 2-digit numbers is 9009 = 91 × 99. The task is to find the largest palindrome that is the product of two 3-digit numbers.

Each factor is an integer from 100 to 999, and the output is a single number: the largest of those products that is a palindrome.

Background

Testing for a palindrome. Write rev(n) for the number whose decimal digits are those of n in reverse order. Then n is a palindrome exactly when rev(n) = n. rev(n) can be built with integer arithmetic alone, no strings: take the last digit with n % 10, append it to the result (result × 10 + digit), replace n by n divided by 10, and repeat until n is 0. For example 9009 goes 9 → 90 → 900 → 9009, so it is a palindrome, while 9019 goes 9 → 91 → 910 → 9109, so it is not. A number ending in 0 (such as 10) loses that 0 as a leading zero when reversed, so it never equals its reverse and is not a palindrome. Since no number starts with 0, that is the right answer.

Products are monotone. For a fixed positive integer a, a × b increases with b. If b steps down from the top by 1, the product drops by a each time. So when we walk b downwards and some product falls to or below a threshold, every later product is at or below it too. For the same reason, if b is at most hi, the largest value of a × b is a × hi, and that value shrinks as a shrinks.

Even-length palindromes are multiples of 11. Expanding a 4-digit palindrome abba and a 6-digit one abccba by place value:

abba   = 1000a + 100b + 10b + a          = 1001a + 110b          = 11 × (91a + 10b)
abccba = 100001a + 10010b + 1100c                                = 11 × (9091a + 910b + 100c)

(1001 = 11 × 91, 100001 = 11 × 9091, 10010 = 11 × 910, 1100 = 11 × 100.) Since 11 is prime, if an even-length palindrome is written as x × y, at least one of x and y is a multiple of 11. The final algorithm does not use this fact; we use it to check the small example by hand and again in “Going further”.

Brute force

Pair every a and b from 100 to 999, form the product, and keep the largest one that is a palindrome.

best = 0
for a in range(100, 1000):
    for b in range(100, 1000):
        if str(a * b) == str(a * b)[::-1]:
            best = max(best, a * b)

There are 900 three-digit numbers, so this forms 900 × 900 = 810000 products and runs a palindrome test proportional to the digit count on each. A modern computer gets through that quickly, so the method is not wrong. Generalized to d digits, though, the number of products is (9 × 10^(d−1))², a factor of 100 more for each extra digit. It also keeps going through every remaining product after the answer has turned up. We are looking for the largest palindrome, yet the method ignores what we already know about where the large products are.

Derivation

Let the factor range be lo = 10^(d−1) to hi = 10^d − 1 (100 and 999 for three digits). We look for work in the brute force that can safely be dropped, one piece at a time.

Step 1: count each unordered pair once. a × b = b × a, so only pairs with a ≤ b are needed. That nearly halves the number of products.

Step 2: look at large products first. Walk a from hi down to lo, and for each a walk b from hi down to a. By monotonicity, the products within one a (call it “row a”) keep decreasing. So the first palindrome met in row a is the largest palindrome in that row, and the rest of the row does not need to be looked at.

Step 3: compare with the best so far. Call the largest palindrome found so far best. If, walking down row a, a product falls to best or below, every remaining product in the row is at most best, so the row can stop.

Step 4: stop the outer loop too. The largest product in row a is a × hi. If a × hi ≤ best, row a holds nothing above best, and every row below a has even smaller products, so they hold nothing either. The whole search ends here.

Checking the small example by hand. Follow it with two digits (lo = 10, hi = 99). Row 99 is just 99 × 99 = 9801, not a palindrome. In rows 98 down to 92, a product can only be a palindrome if one factor is a multiple of 11, by the background fact, and the only multiple of 11 between 92 and 99 is 99. So the only products to check are those with b = 99:

92 × 99 = 9108    93 × 99 = 9207    94 × 99 = 9306    95 × 99 = 9405
96 × 99 = 9504    97 × 99 = 9603    98 × 99 = 9702    99 × 99 = 9801

None is a palindrome, so best stays 0 through rows 99 to 92 (the algorithm walks each of these rows all the way down). The first product in row 91, 91 × 99 = 9009, is a palindrome, so best becomes 9009 and the row stops. In row 90, 90 × 99 = 8910 ≤ 9009, so by step 4 the search ends. The result is 9009 = 91 × 99, matching the problem’s example.

Final algorithm

1. Start with lo = 10^(d−1), hi = 10^d − 1 and best = 0.
2. For a = hi, hi − 1, …, lo:
   1. If a × hi ≤ best, stop everything.
   2. For b = hi, hi − 1, …, a, form p = a × b. If p ≤ best, stop this row. If p is a palindrome, set best = p and stop this row.
3. Return best. It would be 0 if there were no palindrome at all, but that does not happen for the d = 1, 2, 3 used here.
4. Before printing the answer, check small inputs: the palindrome test must give 9009 → true, 9019 → false, 7 → true, 10 → false, and the results for one and two digits must be 9 and 9009. If any check fails, exit with a nonzero status.

Correctness proof

Just before row a is processed, the following holds (the invariant).

best is the largest palindrome among the products of all pairs (x, y) with a < x ≤ y ≤ hi, or 0 if there is none.

At the start (a = hi) there are no such pairs and best = 0, so it holds. A row can stop in two ways. If it stops because a product fell to best or below, monotonicity says every skipped product is at most best, so none of them can change the maximum. If it stops at a palindrome, that product is the largest palindrome in the row and every skipped product is smaller. Within a row, best changes only when a palindrome larger than best turns up. Either way, once the row is done best is the maximum over all pairs with x ≥ a, which is the invariant for the next row, a − 1.

If the outer loop stops at step 4, every remaining pair (x, y) has x ≤ a and y ≤ hi, so x × y ≤ a × hi ≤ best: no remaining product can beat best. If the loop runs all the way down to lo, every pair has been seen. In both cases best is the maximum over all pairs with lo ≤ x ≤ y ≤ hi, and by the symmetry in step 1 that equals the maximum over all pairs regardless of order.

Complexity

Worst case. With N = hi − lo + 1 = 9 × 10^(d−1), there are N(N + 1) / 2 pairs with a ≤ b, and one palindrome test costs time proportional to the number of digits of the product (at most 2d). If no pruning happened at all, the time would be O(N² · d), about half of the brute force. For three digits N = 900, so even the worst case is 405450 products. Only a handful of values are stored, so the auxiliary space is O(1).

In practice it stops much earlier. Once a large palindrome turns up, steps 3 and 4 end most rows after a few products or skip them entirely. How early depends on the input, and there is no formula that guarantees it in advance, so only the worst-case bound is given as the complexity here. This post does not measure the actual iteration count.

Integer range.

• For three digits the largest product is 999 × 999 = 998001, which even fits in 32 bits. The C++ version uses unsigned long long so that d can be anything from 1 to 9. In that range a product is at most (10^9 − 1)² < 10^18, and the standard guarantees unsigned long long is at least 64 bits wide (maximum at least about 1.8 × 10^19), so nothing overflows. Unsigned overflow would not be undefined behaviour anyway, but in this range it simply never occurs.
• The reversed number built by the palindrome test never has more digits than the original, so it stays below 10^18 as well. The product a × hi in step 4 is within the same bound.
• The loop variables are unsigned too, but they stop at a >= lo (lo ≥ 1) and b >= a (a ≥ 1), so they never step below 0 and wrap around to a huge value.
• Python’s int has unlimited precision, so it cannot overflow. The algorithm is the same as in C++.

C++17

#include <iostream>

// True when the decimal digits of n read the same in both directions.
bool is_palindrome(unsigned long long n) {
    unsigned long long reversed = 0;
    for (unsigned long long rest = n; rest > 0; rest /= 10) {
        reversed = reversed * 10 + rest % 10;
    }
    return reversed == n;
}

// Largest palindrome that is a product of two numbers with exactly `digits` digits.
// Only pairs a <= b are tried. For a fixed a, b goes down from the top, so the
// products go down too: stop at the first palindrome or once a product is no
// larger than the best so far. Stop the outer loop once even a * hi cannot beat it.
// Meant for 1 <= digits <= 9, where every value fits in 64 bits.
unsigned long long largest_palindrome_product(int digits) {
    unsigned long long lo = 1;
    for (int i = 1; i < digits; ++i) {
        lo *= 10;
    }
    const unsigned long long hi = lo * 10 - 1;
    unsigned long long best = 0;
    for (unsigned long long a = hi; a >= lo; --a) {
        if (a * hi <= best) {
            break;
        }
        for (unsigned long long b = hi; b >= a; --b) {
            const unsigned long long product = a * b;
            if (product <= best) {
                break;
            }
            if (is_palindrome(product)) {
                best = product;
                break;
            }
        }
    }
    return best;
}

int main() {
    if (!is_palindrome(9009) || is_palindrome(9019) || !is_palindrome(7) ||
        is_palindrome(10) || largest_palindrome_product(1) != 9 ||
        largest_palindrome_product(2) != 9009) {
        return 1;
    }
    std::cout << largest_palindrome_product(3) << '\n';
    return 0;
}

The small examples are checked with if, not assert, because assert disappears in builds where NDEBUG is defined. If any check fails, return 1 gives a nonzero exit status.

Python 3

def is_palindrome(n: int) -> bool:
    """True when the decimal digits of n read the same in both directions."""
    reversed_n = 0
    rest = n
    while rest > 0:
        reversed_n = reversed_n * 10 + rest % 10
        rest //= 10
    return reversed_n == n


def largest_palindrome_product(digits: int) -> int:
    """Largest palindrome that is a product of two numbers with exactly `digits` digits.

    Only pairs a <= b are tried. For a fixed a, b goes down from the top, so the
    products go down too: stop at the first palindrome or once a product is no
    larger than the best so far. Stop the outer loop once even a * hi cannot beat it.
    """
    lo = 10 ** (digits - 1)
    hi = lo * 10 - 1
    best = 0
    for a in range(hi, lo - 1, -1):
        if a * hi <= best:
            break
        for b in range(hi, a - 1, -1):
            product = a * b
            if product <= best:
                break
            if is_palindrome(product):
                best = product
                break
    return best


def main() -> None:
    if (
        not is_palindrome(9009)
        or is_palindrome(9019)
        or not is_palindrome(7)
        or is_palindrome(10)
        or largest_palindrome_product(1) != 9
        or largest_palindrome_product(2) != 9009
    ):
        raise SystemExit(1)
    print(largest_palindrome_product(3))


if __name__ == "__main__":
    main()

Same algorithm, same small examples as the C++ version. To match C++, the palindrome test uses integer arithmetic instead of str(n)[::-1], and digits are stripped with integer division //=. Because range excludes its end value, the loops end one step lower, as in range(hi, lo - 1, -1). If a small example fails, raise SystemExit(1) gives exit status 1. assert is not used because running with python -O removes it.

Answer and checks

The largest palindrome made from the product of two 3-digit numbers is 906609 = 913 × 993. From here on we just call it the result.

The parts that can be checked by hand:

• The product. 913 × 993 = 913 × 1000 − 913 × 7 = 913000 − 6391, which is exactly the result. Both 913 and 993 have three digits.
• The palindrome. The result has six digits, and its first three digits read backwards are its last three.
• The link to 11. The result is 11 × 82419, and 913 = 11 × 83, so one factor is a multiple of 11, as the background fact requires. Splitting further, the result is 3 × 11 × 83 × 331, with 993 = 3 × 331.

That the result is the largest is not a hand calculation; it rests on the correctness proof above and on running the programs. The checks come in three layers.

1. Small examples. Before printing the answer, both programs check four palindrome tests (9009, 9019, 7, 10), the one-digit result 9 and the two-digit result 9009, and exit with a nonzero status if any differ. The two-digit result 9009 was also traced by hand in the derivation.
2. Agreement between the two implementations. In this series’ repository a check script compiles the C++ code with g++ -std=c++17 -O2 -Wall -Wextra -Werror and runs it (warnings count as failures), and runs the Python code with python3 -I -B. Both outputs must match the stored answer.txt byte for byte, and a nonzero exit status or a timeout (1 second for C++, 10 seconds for Python) is a failure. By the series rules only code that passes this check is published.
3. The proof. The correctness proof showed that no product skipped by the pruning can exceed best. If you are still doubtful, run the brute-force code above as it is and compare the results.

Boundary cases

• One digit (d = 1): every product of 1 to 9 that has one digit is a palindrome, and the two-digit palindromes 11, 22, …, 99 are all multiples of 11, so none is a product of two single digits. The answer is therefore 9 (= 9 × 1 = 3 × 3). The algorithm finds no palindrome in rows 9 down to 4 and finds 9 at the last product of row 3, 3 × 3. Row 2 opens because 2 × 9 = 18 is above 9, but stops once a product drops to 9 or below, and row 1 has 1 × 9 = 9 ≤ 9, so step 4 ends the search.
• Products ending in 0: numbers like 10 or 9010 that end in 0 are not palindromes. Reversing with integers drops the leading zero, so the test returns false naturally. The small examples include 10 → false.
• Single-digit numbers: a single digit such as 7 is a palindrome by itself. The loop runs once and gives 7 = 7.
• A product equal to best: the step 3 condition uses <=. An equal value would not change best, so skipping it is fine.

Going further

• Try only multiples of 11. A product of two 3-digit numbers is at least 10000, so a palindrome among them has five or six digits, and if the answer is a six-digit palindrome then a or b must be a multiple of 11. When a is not a multiple of 11, change the inner loop to step b down through multiples of 11 only. Which part of the correctness proof needs to change? You will also have to deal with the fact that five-digit palindromes are not necessarily multiples of 11.
• Build the palindromes first. The other way round is to generate six-digit palindromes from the top, 999999, 998899, 997799, …, and check whether each has a divisor x from 100 to 999 whose cofactor also has three digits. The first three digits determine the palindrome. Which approach tests fewer numbers?
• More digits. How does the effect of pruning change for d = 4, 5, …? The C++ code above stays within 64 bits for d ≤ 9, but even there the worst-case bound is O(N² · d).
• Other bases. is_palindrome only looks at decimal digits. How would you change it to take the base as a parameter, and does the argument that numbers ending in 0 are never palindromes still hold?

Sources and license

• Project Euler, Problem 4 — the original problem. The “Problem” section of this post is my own summary of it and is shared under the same CC BY-NC-SA 4.0 license as the original. Attribution for the problem goes to Project Euler.
• Project Euler, Copyright — the license of the problem text and how to link to problems. Because of the non-commercial condition, this post carries no ads (ads: false).
• The solution, proofs and code are my own. I did not consult Project Euler’s overviews, forum, member-only material or other solution sites. Motitory is not affiliated with or sponsored by Project Euler, and Project Euler has not reviewed this post.