Idea of Algorithm

Question

How do I find out if a number is sum of 2 palindromes?

Example:

123 = 101 + 22.

See 101 and 22 are palindromes;

Answer 1

The first, naive way of thinkin is to simply say "check all palindromes to see if they sum to your number"

You can then improve this in two ways:

• First, you don't have to check pairs of palindromes. You can simply check each palindrome, subtract it from your number and se if it results in a palindrome.
• Second, see how you can generate palindromes. For example, you can generate all palindroms of length $2n$ by going throuh all numbers of length $n$ and reversin them, and a similar procedure holds for length $2n+1$.

Answer 2

This is what I told my friend Ruby:

def is_sum_of_two_palindromes?(n)
  i_max = n / 2
  (1..i_max).each do |i|
    j = n - i
    if (is_palindrome?(i) and is_palindrome?(j))
      puts "n = #{i} + #{j}"
      return true
    end
  end
  return false
end

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

When I asked her

is_sum_of_two_palindromes?(123)

she responded with

n = 2 + 121

That was kind of boring, so I told her

def is_sum_of_two_non_trivial_palindromes?(n)
  i_max = n / 2
  (1..i_max).each do |i|
    j = n - i
    if (is_non_trivial_palindrome?(i) and is_non_trivial_palindrome?(j))
      puts "n = #{i} + #{j}"
      return true
    end
  end
  return false
end

def is_non_trivial_palindrome?(n)
  s = n.to_s
  s.length > 1 and s == s.reverse
end

and asked

is_sum_of_two_non_trivial_palindromes?(123)

where Ruby replied

n = 22 + 101