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

• Do you accept $121 = 0 + 121$? – mvw Sep 14 '16 at 7:45

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

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


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


is_sum_of_two_non_trivial_palindromes?(123)

n = 22 + 101