Shanghai Bob

I’ve been doing the Project Euler puzzles in Python.  Here’s one:

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.

My solution turned out to be unique.  Instead of multiplying three-digit numbers, filtering for palindromes, and then picking the largest, it generates palindromes directly by counting down from 999 and “mirroring” the digits to the right:

999999

998899

997799

…

Since the result will be six digits (nnn * nnn = nnnnnn), the first number in this series that has a three-digit factor must be the answer.  Here’s the code, which returns in under a second:

#!/usr/bin/python
from sys import exit
def mirror(n):
  s = str(n)
  return int(s + s[::-1])
r = range(999, 100, -1)
for i in r:
  pal = mirror(i)
  for j in r:
    if (pal % j == 0) and (pal / j < 1000):
      print pal
      exit(0)

This entry was posted on Tuesday, June 9th, 2009 at 6:03 am and is filed under web.