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