Largest palindrome product From the Project Euler challenge series:


  A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
  Find the largest palindrome made from the product of two 3-digit numbers.


The brute force method runs in 1.8s per loop on my machine:

def getGen(n):
    return range(n,-1,-1)

def bruteForce():
    gen = getGen(999)
    sc = maxpalin = 0
    for i in gen:
        for j in gen:
            sc += 1
            prod = i * j
            s = str(prod)
            if s==s[::-1] and prod &gt; maxpalin:
                maxpalin = prod
    print(sc)
    return maxpalin

%timeit bruteForce()


When I initially approached the problem, I tried to use the properties of multiplying 2 different 3-digit numbers to find the solution. This approach, however, takes approximately 16.7s per loop, even though the sc for the bruteForce is 1 million and the sc for Palindrome.main() (see below) is considerably lower at 4536. Why does the Palindrome class run so much slower?

$$(a.b.c) * (x.y.z) = (l.m.n.n.m.l)$$
$$(100a + 10b + c) * (100x + 10y + z) = (100001l + 10010m + 110n)$$
$$(10000ax + 1000ay + 100az) + (1000bx + 100by + 10bz) + (100cx + 10cy + cz) = (100001l + 10010m + 110n)$$
$$10000ax + 1000(ay + bx) + 100(az + by + cx) + 10(bz + cy) + cz = (100001l + 10010m + 1100n)$$
$$10(1000ax + 100(ay + bx) + 10(az + by + cx) + (bz + cy)) + cz = 100001l + 10(1001m + 110n)$$

firstPass
$$10(1000ax + 100(ay + bx) + 10(az + by + cx) + (bz + cy) - 1001m - 110n) = 100001l - cz = 10p \implies 10 \mid 10p$$

secondPass
$$p = 10(100ax + 10(ay + bx) + (az + by + cx - 11n)) + (bz + cy) - 1001m \implies 10 \mid p + 1001m - (bz + cy) = 10q$$

thirdPass
$$q = 10(10ax + (ay + bx)) + (az + by + cx - 11n) \implies 10 \mid q + 11n - (az + by + cx) = 10r$$

main
$$r = 10ax + (ay + bx) \implies 10 \mid r - (ay + bx) = 10s$$

class Palindrome(object):
    def __init__(self):
        self.a = 0
        self.b = 0
        self.c = 0
        self.l = 0
        self.m = 0
        self.n = 0
        self.x = 0
        self.y = 0
        self.z = 0

    def firstPass(self):
        gen = getGen(9)
        for l in gen:
            for c in gen:
                for z in gen:
                    p = 100001 * l - (c * z)
                    if (p % 10):
                        continue
                    self.l = l
                    self.c = c
                    self.z = z
                    yield p / 10

    def secondPass(self, p):
        gen = getGen(9)
        for m in gen:
            for b in gen:
                for y in gen:
                    q = p + (1001 * m) - ((b * self.z) + (self.c * y))
                    if (q % 10):
                        continue
                    self.m = m
                    self.b = b
                    self.y = y
                    yield q / 10

    def thirdPass(self, q):
        gen = getGen(9)
        by = self.b * self.y
        for a in gen:
            for x in gen:
                for n in gen:
                    r = q + (11 * n) - (a * self.z + by + self.c * x)
                    if (r % 10):
                        continue
                    self.a = a
                    self.x = x
                    self.n = n
                    yield r / 10

    def main(self):
        sc = 0
        for p in self.firstPass():
            for q in self.secondPass(p):
                for r in self.thirdPass(q):
                    a = self.a
                    b = self.b
                    x = self.x
                    y = self.y

                    s = r - (a * y + b * x)
                    if s == 10 * a * x:
                        sc += 1
                        m = 100 * a + 10 * b + self.c
                        n = 100 * x + 10 * y + self.z

                        yield m * n
        print(sc)

i = Palindrome()
%timeit (max(i.main()))
A quick look at bruteForce.


The built-in max computes the maximum value of a collection.
Nested loops can often be combined into a single loop using product, combinations, or combinations_with_replacement, depending on how you need to handle repetitions.
The loops go downwards from 999, but no use is made of this (no early exit) so you might as well let the loops go upwards, which is simpler.


Revised code:

from itertools import combinations_with_replacement

def palindrome(n):
    """Return True if n is a palindrome in base 10."""
    s = str(n)
    return s == s[::-1]

def problem4():
    """Return the largest palindrome made from the product of two 3-digit
    numbers.

    """
    return max(i * j
               for i, j in combinations_with_replacement(range(1000), 2)
               if palindrome(i * j))