1
$\begingroup$

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

Example:

123 = 101 + 22.

See 101 and 22 are palindromes;

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

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$.
| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.