Idea of Algorithm How do I find out if a number is sum of 2 palindromes?
Example:
123 = 101 + 22.
See 101 and 22 are palindromes;
 A: 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$.

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

