# Project Euler problem 4

Source code available on GitHub.

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 with digits is going to be . If you don’t know modular arithmetic, that just meant it’s the remainder when we divide 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 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: .

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)