Project Euler problem 4

Source code available on GitHub.

This problem reads as follows:

  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.

The last bit says ‘made from the product of two 3-digit numbers’. There aren’t that many 3-digit numbers around, so it’s perfectly fine for us to just have two `for` loops inside each other:

for i in range(100,1000):
    for j in range(i,1000):
        prod = i*j

Now in order to determine whether `prod` is a palindrome or not, we’re going to have to separate it out into its digits. There is a very simple way of doing this: convert `prod` to a string, and convert that string to a list (or a tuple, as it’s not going to change). You just do `tuple(str(prod))` and you’re done, you have a tuple containing all of its digits. If you want to convert each of those digits back from a string into an integer, you instead do `tuple(int(i) for i in str(prod))`. You can see how that gets the job done.

Anyway, I didn’t think of that when I did this problem, so I’ll give my long-winded mathematical way here that I actually used.

The product of two 3-digit numbers is going to be either 6 digits long or 5 digits long. So, we initialise a list as `digits = [0,0,0,0,0,0]`. Now, the last digit of some integer n with digits a_0,a_1,a_2,a_3,a_4,a_5 is going to be a_5 \equiv n \mod 10. If you don’t know modular arithmetic, that just meant it’s the remainder when we divide n by 10. If our number is 54, for example, then dividing by 10 gives you a remainder of 4, which is indeed the last digit.

It’s not hard to see that the last two digits together are n \mod 100 in a similar way – for instance, divide 154 by 100 and you get a remainder of 54. To get rid of the 4 at the end, we subtract the last digit (which we already know) and divide by 10: (54 - 4)/10 = 5.

The pattern continues all the way down. Our code implementation of this is something like follows:

prod = i*j
digits = [0,0,0,0,0,0] # Separating the product out into its digits
digits[5] = int(prod % 10)
digits[4] = int((prod % 100 - digits[5])/10)
digits[3] = int((prod % 1000 - 10*digits[4])/100)
digits[2] = int((prod % 10000 - 100*digits[3])/1000)
digits[1] = int((prod % 100000 - 1000*digits[2])/10000)
digits[0] = int((prod % 1000000 - 10000*digits[1])/100000)

I hope it makes sense how that works! Once you see how the first two happen, you can just keep adding zeroes every line.

Anyway, now we know the digits. There are still two cases: if the first of those 6 digits is a zero (so `digits[0] == 0`) then `prod` is really a five-digit number; otherwise it’s clearly six digits long.

Fine. Given either of these cases, it’s not hard to check whether the number is a palindrome:

if digits[0] == 0:
            if digits[1] == digits[5] and digits[2] == digits[4]:
                # PALINDROME TRUE
        else:
            if digits[0] == digits[5] and digits[1] == digits[4] and digits[2] == digits[3]:
                # PALINDROME TRUE

Then, using a new variable – let’s call it `largest_pallen` – if the new palendrome is the largest yet, we need to do `largest_pallen = prod`. At the end of the whole thing we’ll be left with `largest_pallen` as our answer!

Full code below:

largest_pallen = 0
for i in range(100,1000):
    for j in range(i,1000):
        prod = i*j
        digits = [0,0,0,0,0,0] # Separating the product out into its digits
        digits[5] = int(prod % 10)
        digits[4] = int((prod % 100 - digits[5])/10)
        digits[3] = int((prod % 1000 - 10*digits[4])/100)
        digits[2] = int((prod % 10000 - 100*digits[3])/1000)
        digits[1] = int((prod % 100000 - 1000*digits[2])/10000)
        digits[0] = int((prod % 1000000 - 10000*digits[1])/100000)
        if digits[0] == 0:
            if digits[1] == digits[5] and digits[2] == digits[4]:
                if prod > largest_pallen:
                    largest_pallen = prod
        else:
            if digits[0] == digits[5] and digits[1] == digits[4] and digits[2] == digits[3]:
                if prod > largest_pallen:
                    largest_pallen = prod
print(largest_pallen)

Leave a Reply

Your email address will not be published. Required fields are marked *