Brute force check for largest palindromic product of three number integers

Updated TrustyTony 0 583 Views

Here is slow brute force way to find the largest palindromic product of three digit integers. You could do loop and break out of it if you go under the smaller number (the second one) of best solution found so far to be more efficient etc.

def pali(a):
    return str(a) == str(a)[::-1]

print('Biggest palindromic product of two three digit integers is %i, which is %i * %i.' % 
       max((a*b, a, b) for a in range(999, 100, -1) for b in range(a, 100000//a, -1) if pali(a*b)))
""" Output:
Biggest palindromic product of two three digit integers is 906609, which is 993 * 913.
"""

Dani AI

Generated

A compact, often faster alternative to the pure brute force posted by is to generate palindromes in descending order and test them for 3‑digit factors. That way the algorithm inspects far fewer candidates (at most a few hundred palindromes) instead of checking every product. It also complements the early‑break idea shown above: once you find a palindrome with two 3‑digit factors you can stop, and you can prune divisor ranges so you never test values that cannot possibly produce a larger product.

Example (palindrome‑construction + tight divisor bounds):

def find_largest_palindrome():
    for left in range(999, 99, -1):
        p = int(str(left) + str(left)[::-1])          # 6-digit palindrome abc|cba
        lower = max(100, (p + 998) // 999)           # ceil(p/999) -> smallest divisor that could produce a 3-digit partner
        for d in range(999, lower-1, -1):
            if p % d == 0:
                q = p // d
                if 100 <= q <= 999:
                    return p, d, q
    return None

Why this helps: there are only 900 possible 6‑digit palindromes made from a 3‑digit left half, and for each palindrome the divisor loop is tightly bounded by math (no wasted checks below ceil(p/999)). That typically finds the same maximal palindrome much faster than checking every a*b pair. The approach also avoids repeated string reverse checks inside a huge nested loop.

Notes and gotchas:

  • The outer early‑break used by is valid because the inner loop only tests b <= a; if the stored smaller factor exceeds the current a, then a*a cannot beat the best product. Keep the stored factors ordered so that check remains correct.
  • Readability wins in most cases; wrapping the palindrome test in a small function is fine unless you need microbenchmarks. String reversal is simple and fast in Python, but integer reversal is an option if you want to avoid conversion costs.
  • For completeness, if no 6‑digit palindrome yields 3‑digit factors you would fall back to generating 5‑digit palindromes (same idea, smaller left half). The 6‑digit search usually succeeds first.

Further reading: Project Euler problem 4 (largest palindromic product) — https://projecteuler.net/problem=4

Member Avatar for hughesadam_87
hughesadam_87 54 Junior Poster

Well that just blew my mind.

Is it actually quicker to define the pali() function than it would be to just put that expression into the generator expression? EG

       max((a*b, a, b) for a in range(999, 100, -1) for b in range(a, 100000//a, -1) if str(a*b))==str(a*b)[::-1])

I ask because sometimes my list comprehensions get really crowded and I never think to do this.

Edited by hughesadam_87
Member Avatar for TrustyTony
TrustyTony 888 ex-Moderator

It is faster by one function call penalty per iteration to not to use function, but function compensate it by making the code more readable. Your generator version is incorrect, you misplaced a ')':

max((a*b, a, b) for a in range(999, 100, -1) for b in range(a, 100000//a, -1) if str(a*b)==str(a*b)[::-1])

The optimized version with loop, even this above one liner is for me fast enough

def pali(a):
    return str(a) == str(a)[::-1]

m = (0,0,0)
for a in range(999, 100, -1):
    if m[-1] > a:
        #print('Breaking with a = %i' % a)
        break
    for b in range(a, 100000//a, -1):
        if pali(a*b):
            if a * b > m[0]:
                m = a*b, a, b
                #print m
            break


print('Biggest palindromic product of two three digit integers is %i, which is %i * %i.' % m)

""" Debug output:
(580085, 995, 583)
(906609, 993, 913)
Breaking with a = 912
Biggest palindromic product of two three digit integers is 906609, which is 993 * 913.
"""
Edited by TrustyTony
Member Avatar for hughesadam_87
hughesadam_87 54 Junior Poster

Ya I would agree that the tradeoff for readability is worth it.

Thanks for sharing the snippet.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview