patternrubyMinor

Project Euler problem 4 in Ruby

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

problemprojecteulerruby

Problem

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 << 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.

Solution

Algorithm

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

-
Given m and n,

m 

- 
If a palindrome

kl has been found, where k kl, where i kl/i (regardless of whether ij is a palindrome). In other words, there is no need to check to see if i*j is a palindrome for j

if kl/i > n, we are finished, as no product ef, e




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 > 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=>             9,009, :v1=>       91, :v2=>      99,
  # :smaller_at_term=>         90, :nbr_palins=>1, :soln_time=>"0.00004"}
largest_palindrome(999)
  # {:product=>           906,609, :v1=>      913, :v2=>      993,
  #  :smaller_at_term=>       907, :nbr_palins=>2, :soln_time=>"0.00101"}
largest_palindrome(9,999)
  # {:product=>        99,000,099, :v1=>     9901, :v2=>     9999,
  #  :smaller_at_term=>    9,900,  :nbr_palins=>1, :soln_time=>"0.00178"}
largest_palindrome(99,999)
  # {:product=>     9,966,006,699, :v1=>    99681, :v2=>    99979,
  #  :smaller_at_term=>     99661, :nbr_palins=>1, :soln_time=>"0.02040"}
largest_palindrome(999,999)
  # {:product =>  999,000,000,999, :v1=>  999,001, :v2=>  999,999,
  #  :smaller_at_term=>   999,000, :nbr_palins=>1, :soln_time=>"0.20434"}
largest_palindrome(9,999,999)
  # {:product=>99,956,644,665,999, :v1=>9,997,647, :v2=>9,998,017,
  #  :smaller_at_term=> 9,995,665, :nbr_palins=>1, :soln_time=>"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 #=> 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) => 9998 => 9,702 pairs were examined, which is 0.0097% of all 9999*9998 => 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.

Code Snippets

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 > 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

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

(99000099/9999.0).ceil - 1 #=> 9900

Context

StackExchange Code Review Q#74881, answer score: 5

Revisions (0)

No revisions yet.