Project Euler problem 4 in Ruby 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.


I started out with this solution. It's iterative, and not very efficient. It multiplies all number combinations, adds the products to an array, finds the palindromes, then chooses the max.

def palindrome?(number)
  number.to_s == number.to_s.reverse
end

def largest_palindrome(range = 1..999)
  array = []
  range.each do |x|
    range.each do |y|
      array.push(x * y)
    end
  end
  array.select { |n| palindrome?(n) }.max
end
puts largest_palindrome


I improved with my second iteration, but it still relies on iteration. I narrowed the range down reasoning that the largest palindrome is likely to be the product of two numbers within 901 and 999. This time I multiplied all the numbers, but only saved the palindromes in the array, then selected max, which saved a step. It's noticeably faster, but still not optimal.

def largest_palindrome(range = 1..99)
  palindromes = []
  range.end.downto(range.begin).each do |x|
    range.end.downto(range.begin).each do |y|
      palindromes &lt;&lt; x * y if palindrome?(x * y)
    end
  end
  palindromes.max
end

puts largest_palindrome 901..999


My reasoning about narrowing the range feels like cheating. It's intuitive, and arbitrary.
Algorithm

You can increase the efficiency of the algorithm by making use of two facts (particularly the second one):


Given m and n, m &lt; n, the largest palindrome m*j, m &lt; j &lt;= n, if there are any, is the one for which j is largest.  In other words, with m fixed, we can look for palindromes m*j, beginning with j = n and then successively reduce j until either a palindrome is found or we conclude there are no palindromes m*j for m &lt; j &lt;= n. If a palindrome mk is found, then (for fixed m) there is no need to consider values of j for which m &lt; j &lt; k, as we have found the largest palindrome whose smaller factor equals m and whose larger factor is between m+1 and n.
If a palindrome k*l has been found, where k &lt; l &lt;= n, then in order for i*j &gt; k*l, where i &lt; k, i &lt; j &lt;= n, we see that j &gt; k*l/i (regardless of whether i*j is a palindrome).  In other words, there is no need to check to see if i*j is a palindrome for j &lt;= k*l/i, as it cannot be larger than the currently largest known palindrome.  Moreover:


if i*j, is found to a palindrome, where k*l/i &lt; j &lt;= n, it becomes the currently largest known palindrome; and
if k*l/i &gt; n, we are finished, as no product e*f, e &lt;= i, e &lt; f &lt;= n, can be larger than the currently largest known palindrome.



These two observations are implemented in a straightforward way by the code that follows.

Code

def largest_palindrome(low=1,n)
  best = { product: false }
  (n-1).downto(low) do |start1|
    start2 = best[:product] ? (best[:product]/start1.to_f).ceil : start1+1
    break if start2 &gt; n
    found2 = n.downto(start2).find { |j| palindrome?(start1*j) }
    best = { product: start1*found2, v1: start1, v2: found2 } if found2
  end
  best
end  

def palindrome?(n)
  (s = n.to_s) == s.reverse
end


Examples

largest_palindrome(99)
  # {:product=&gt;             9,009, :v1=&gt;       91, :v2=&gt;      99,
  # :smaller_at_term=&gt;         90, :nbr_palins=&gt;1, :soln_time=&gt;"0.00004"}
largest_palindrome(999)
  # {:product=&gt;           906,609, :v1=&gt;      913, :v2=&gt;      993,
  #  :smaller_at_term=&gt;       907, :nbr_palins=&gt;2, :soln_time=&gt;"0.00101"}
largest_palindrome(9,999)
  # {:product=&gt;        99,000,099, :v1=&gt;     9901, :v2=&gt;     9999,
  #  :smaller_at_term=&gt;    9,900,  :nbr_palins=&gt;1, :soln_time=&gt;"0.00178"}
largest_palindrome(99,999)
  # {:product=&gt;     9,966,006,699, :v1=&gt;    99681, :v2=&gt;    99979,
  #  :smaller_at_term=&gt;     99661, :nbr_palins=&gt;1, :soln_time=&gt;"0.02040"}
largest_palindrome(999,999)
  # {:product =&gt;  999,000,000,999, :v1=&gt;  999,001, :v2=&gt;  999,999,
  #  :smaller_at_term=&gt;   999,000, :nbr_palins=&gt;1, :soln_time=&gt;"0.20434"}
largest_palindrome(9,999,999)
  # {:product=&gt;99,956,644,665,999, :v1=&gt;9,997,647, :v2=&gt;9,998,017,
  #  :smaller_at_term=&gt; 9,995,665, :nbr_palins=&gt;1, :soln_time=&gt;"2.05677"}


I have formatted the numbers to make them easier to read and also added three statistics I thought might be of interest:


the value of the smaller of the two factors when the search was terminated;
the number of palindromes found before the search terminated; and
the solution time in seconds (on a newish Mac).


To see where each search terminated, divide best[:product] by n, round up and subtract 1. For example, for n = 9999, this would be:

(99000099/9999.0).ceil - 1 #=&gt; 9900


This shows that when determining the largest palindrome for numbers up to 9,999, it was only necessary to consider pairs with values greater than 9,900. Hence, at most (9999-9900)*(9999-9901) =&gt; 99*98 =&gt; 9,702 pairs were examined, which is 0.0097% of all 9999*9998 =&gt; 99,970,002 pairs of numbers up to 9,999.

For n = 999, two palindromes were found before the search terminated. In each of the other four examples, only one palindrome (i.e., the largest) was found before the search terminated.