Euler #004 - Largest palindrome product
12345678910111213141516171819202122232425262728293031323334353637
"""
The palindrome can be written as: abccba
Which then simpifies to:
100000a + 10000b + 1000c + 100c + 10b + a
And then:
100001a + 10010b + 1100c
Factoring out 11, you get:
11(9091a + 910b + 100c)
So the palindrome must be divisible by 11.
Seeing as 11 is prime, at least one of the numbers must be divisible by 11.
So brute force in Python, only with less numbers to be checked
"""
def is_palindrome(n):
nstr = str(n)
for idx in range(len(nstr) + 1 // 2):
if nstr[idx] != nstr[-(idx + 1)]:
return False
return True
ans = n1 = n2 = comp = 0
# for num1 in range(100, 1000):
# for num2 in range(num1, 1000):
for num1 in range(999, 99, -1): # num1 range 999 to 100
for num2 in range(num1 - num1 % 11, 99, -11): # num2 range from (nearest 11 factor of num1) to (all 11 factors > 99)
product = num1 * num2
comp += 1
if product > ans and is_palindrome(product):
ans, n1, n2 = product, num1, num2
print(ans, n1, n2, comp)
Python
INFO