A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 \times 99.
Find the largest palindrome made from the product of two 3-digit numbers.
https://projecteuler.net/problem=4
Dog, no poop on God!
That’s my favorite palindromic sentence. I don’t know about a favorite palindromic number, but they’re certainly interesting. The symmetric nature of them is aesthetic. While they don’t seem to have much application beyond recreational mathematics, the techniques developed to deal with them are pretty cool.
The problem is asking for the largest palindrome from the product of two 3-digit numbers. This is actually two problems in one. The first problem is detecting whether a number is a palindrome. The second problem is finding an efficient way to generate and sort products of two 3-digit numbers. Let us tackle the second problem first.
X+Y sorting
This problem is known as X+Y sorting. Here, the operation is multiplication rather than addition. An unsolved problem in computer science is the search for an algorithm that does better than \mathcal{O}(n^2 \log{n}). Let’s see how my attempt fares.
So we’ve got two sequences: A and B which enumerate from 100 to 999. We want to find all pairs and multiply them together. This is called the Cartesian product. One drawback that pops up is that these are ordered pairs. Multiplication is commutative, i.e. it doesn’t care about order. We would be generating twice as many products as we need to check. True, big O doesn’t care about a constant factor of 2, but it’s still good to keep in mind.
For each number a in A, we multiply it with all numbers in B. We store the products in a list P. This part of the algorithm takes place in quadratic time.
In Python, here’s the naive way1Of course, some will argue that using Python for number theory is naive in itself:
numbers = range(100, 1000) # Range is right-exclusive
products = []
for a in numbers:
for b in numbers:
products.append(a*b)
products = sorted(products, reverse = True)
This generates a sorted list of the Cartesian product, but it’s also reinventing the wheel. Python’s standard library follows a “batteries included” philosophy. itertools, a very useful module, offers the combinations_with_replacement function, which returns “r length subsequences of elements from the input iterable allowing individual elements to be repeated more than once.” The above code can be crushed into
import itertools pairs = itertools.combinations_with_replacement(range(100,1000), 2) products = sorted([pair[0] * pair[1] for pair in pairs], reverse = True)
Let’s have a race between the two methods! The first method takes an average of 0.21 seconds. The second method takes an average of 0.089 seconds, more than halving running time! Yay for itertools!
There are some duplicates in both lists. Numbers can be the product of two different pairs of numbers. For example: 90000=100\times900=225\times400. They could be eliminated by converting the list to a set, but I’m not sure if that is worthwhile.
Are you a palindrome?
Now that we’ve got a sorted list of all products of two 3-digit numbers, it’s time to write a method that checks if numbers are palindromic or not. One simple way is to convert the number to a string, then check if both the string and its reverse are the same. However, it feels like a cop-out to resort to strings. Just for the challenge, I want to do a numerical method.
Getting the number of digits in a base-10 number is easy: just round up the logarithm to the next integer!
\text{number of digits in }n=\lceil\log_{10}(n)\rceil \tag{1}We also need a way to access individually the digits of a number. We’re working with base-10 numbers so we can just divide by 10 repeatedly. The decimal part will contain the digit. For example: 12345/10 = 1234.5. Severing the decimal part from the whole part is just a subtraction and multiplication away: 5=(1234.5-\lfloor1234.5\rfloor)\times10.
\text{rightmost digit in }n=10\times\Big(\frac{n}{10}-\Big\lfloor\frac{n}{10}\Big\rfloor\Big) \tag{2}To decompose a number into its constituent digits, we can apply Equation 2 over and over. But there’s a snag: what happens if n is just one digit? We need a stopping condition. This is where Equation 1 comes in. Hmm…sounds like a perfect condition for a while loop!
import math
def is_palindromic(n):
digits = []
while math.ceil(math.log(n, 10)) > 1:
rightmost_digit_of_n = 10 * (n / 10 - math.floor(n / 10))
n = math.floor(n / 10)
digits.append(rightmost_digit_of_n)
digits.append(n)
reversed_digits = digits[::-1]
return digits == reversed_digits
Uh-oh…floating point errors galore! These arise because real numbers cannot be represented in a finite space. Overlooking this can be very costly. One classic example is the Patriot missile failure in 1991. American missile defense systems failed to shoot down an incoming Iraqi Scud missile, resulting in the deaths of 28 soldiers. The error occurred because cumulative floating point errors caused the Patriot defense system’s internal clock to drift by a third of a second. This tiny discrepancy combined with the speed of the incoming Scud resulted in a miss of 600 meters. There are many more unfortunate examples of floating point errors with real ramifications.
Thousands and thousands of journal articles have been written about this subject. For an amateur coder like me, I’d rather save some mental work and just round off the error. Kludgy and terrible for mission-critical applications, but it’ll do for now. The fix is rounding the subtraction in line 5 above to the tenths place.
Putting it together
Now that we’ve solved both sub-problems (generating the Cartesian product and checking if a number is palindromic), let’s put them together, add documentation, and let the program have at the problem.
import itertools, math
def generate_sorted_products_of_two_n_digit_numbers(n):
"""Runs a Cartesian product between all n digit numbers, then sorts them in decreasing order.
Args:
n (int): number of digits in the number
Returns:
list: a sorted list, in descending order, of the Cartesian product between all n-digit numbers
"""
pairs = itertools.combinations_with_replacement(range(10**(n-1),10**n), 2)
return sorted([pair[0] * pair[1] for pair in pairs], reverse = True)
def is_palindromic(n):
"""Non-string method of checking whether a number is palindromic or not
Args:
n (int): number to check for palindromicity
Returns:
bool: true if the number is palindromic, false otherwise
"""
digits = []
while math.ceil(math.log(n, 10)) > 1:
rightmost_digit_of_n = 10 * round(n / 10 - math.floor(n / 10), 1)
n = math.floor(n / 10)
digits.append(int(rightmost_digit_of_n))
digits.append(n)
reversed_digits = digits[::-1]
return digits == reversed_digits
# Putting it together
products = generate_sorted_products_of_two_n_digit_numbers(3)
for product in products:
if is_palindromic(product):
print(product)
break # Since the list is sorted in descending order, the first palindrome we encounter will be the largest.
Running it outputs 906609. Correct! (I checked with this handy list of answers). Now, I’m curious about two things: 1) what about 4-digit numbers? This takes much longer! The largest palindrome for that is 99000099. 2) Is the string method faster?
It’s very easy on the brain to spin up a string-based method to check if a number is palindromic.
def is_palindromic_string(n):
return str(n) == str(n)[::-1]
Putting both is_palindromic functions through time trials reveals that the string-based method executes faster than the numerical-based method. I suspect this is due to my poor coding, rather than any inherent limitation.
>>> compare_execution_times(is_palindromic, (12345678987654321,), is_palindromic_string, (12345678987654321,)) is_palindromic_string wins! Time difference: 2.568e-05 seconds, factor of 24.345
Look at that! The string-based method is 24 times faster! My solution code, if you want it, is here.