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.
This problem has been reviewed numerous times on this site, and many extraordinary clever solutions has been suggested. I have taken my own stab at the problem, and done it a tad differently. I was mainly wondering if my code is readable and if it has any advantages over the quote on quote standard approach i see many others using.
The standard approach is shown below.
- for i from 999 to 1 - for j from 999 to 1 if is_palindrome( i*j ) best = max(old, best)
The basic idea is to iterate over the 3-digit numbers i and j. If the product is a palindrome then check whether it is bigger than the previously found palindrome. There are many speed improvements one could make to the psudo code above (like breaking early or only iterating over numbers divisible by 11). I have implemented these in the code below labeled standard approach.
My thought was even with these improvements it took 160 seconds finding the biggest palindromic product formed by two 8 digit numbers.
for palindromes < limit num1, num2 = check(palindrome) if num1*num2 > 0 return num1*num2
Here i iterate over the palindromes starting from biggest to smallest. If the palindromes can be factored into two numbers with n digits we have found the solution. Since we start at the biggest palindrome we can stop once a solution has been found.
I am mainly interested in feedback regarding my method, not the standard one.Is it readable, can one understand what the different help functions do? Also any general feedback on my algorithm / approach would be appreaciated. I think I atleast have followed PEP8.
def is_palindrome(n): """Return True if n is a palindrome, False otherwise.""" s = str(n) return s == s[::-1] def product_lst(n): palindrome = max_palindrome = 0 pair = (0, 0) for i in xrange(n - 1, 0, -1): "Since all palindromes are divisible by 11, either j or i has to be as well" if i % 11 == 0: j_max = i j_range = xrange(i + 1, 0, -1) else: j_max = 11 * int(i / 11) j_range = xrange(j_max, 0, -11) if i * j_max < palindrome: break for j in j_range: product = i * j if product < palindrome: break if is_palindrome(product): if product > palindrome: palindrome = product pair = (i, j) return (pair, palindrome)
from primefac import isprime def palindrome_product(n): "Maximises num1 * num2 = palindrome. Where num1 and num2 has length n." palindrome_generator = generate_palindromes(n) for palindrome in palindrome_generator: num1, num2 = is_product_of_two(palindrome, n) if num1 != 0: return ((num1, num2), palindrome) def generate_palindromes(n): " Generates palindromes of decreasing order" first_half = 10**n - 1 while first_half > 10**(n - 1) - 1: second_half = str(first_half)[::-1] palindrome = int(str(first_half) + str(second_half)) yield palindrome first_half -= 1 def is_product_of_two(palindrome, n): " Checks wheter the palindrome can be written as a product" " of two numbers of length num" palindrome //= 11 "All palindromes are divisible by 11" num_1 = num_2 = 0 if not isprime(palindrome): " Generate numbers such that 11*i has length n" for i in xrange(10**(n) / 11, 10**(n - 1) / 11, -1): " If num2 > 10**n then num2 is no longer a n-digit number" if palindrome > i * 10**n: break if palindrome % i == 0: num_1 = i * 11 num_2 = palindrome / i break return num_1, num_2