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