# Euler Problem 4

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.

Testing for a palendrome is easy: Convert number to string and compare pairs of digits working your way in from the outside to the center. If all the pairs match, you have a palendrome

def is_palindrome(v) s = v.to_s for i in 0..((s.length-1)/2) do return false if s[i] != s[-(i+1)] end return true end

A naive approach might be to list all multiples of three digit numbers, sort the list from largest to smallest and work your way down the list until you find a palindrome.

But, there’s actually no need to generate all the multiples of three digit numbers in order to search through them from largest to smallest. Consider:

– if a+b > x+y then a*b > x*y

– if a+b = x+y and abs(a-b) < abs(x-y) then a*b > x*y

Hence, counting down from n = 999*2, generate multiples from the pairs of three digit numbers that add to n, starting with the pair i*(n-i) where i = n/2 and incrementing i.

def largest_palindrome_product( max ) n = max*2 while n > 0 do for i in (((n+1)/2)..max) p max, n, i, n-i return i*(n-i) if is_palendrome( i*(n-i) ) end n -= 1 end end

## About this entry

You’re currently reading “Euler Problem 4,” an entry on blog

- Published:
- February 20, 2012 / 14:04

- Category:
- euler

- Tags:

## 1 Comment

Jump to comment form | comment rss [?] | trackback uri [?]