Reverse and add until a palindrome

Given a positive integer, reverse the digits and add the resulting number to the original number. How many times does one have to repeat the process until one gets a palindrome? A palindrome is a number whose digits are the same when read left to right and right to left. LINK – have a program

For example, for 5280, we get a palindrome after 3 steps (each step reverses the string and add both)

Step 1: 5280 + 0825 = 6105

Step 2: 6105 + 5016 = 11121

Step 3: 11121 + 12111 = 23232

If we start executing the described step over and over again and we generate a palindrome, we the algorithm terminates.  However, if we don’t get a palindrome after 100 steps, after a 1000 steps, after 10,000 steps, what can we conclude?

We can stop and say “we have not generated a palindrome after 10000 iterations” but we cannot make any claim that a palindrome cannot be found later.  Indeed, there exists no algorithm that generates the answer “no palindrome can be generated.

Below is the code for the “reverse and add until a palindrome” problem. The code includes the while-loop

while (not is_palindrome(number) and step < our_limit):

which terminates when a palindrome is found or our patience is over! Run the code with 196 as input. No one has yet found a palindrome. Running the program with our_limit = 10000 will not find one.  If one runs the program without a set limit, an infinite loop happens.

If we were to remove the step < our_limit  condition, we have an algorithm that may not terminate. For many integers, it actually terminates. However for 196, we do not know whether this simple algorithm terminates. No one has been able to prove that it does not terminate either.


#get the reversed number
def reverse_num(n):
    num = str(n)
    rev_num = ""                      #start reversed num as blank
    x = len(num) - 1                  #find the length of the input num

    for i in range(x,-1,-1):      #start at end of num & move backwards
        digit = num[i]                         #get the digit
        rev_num = rev_num + digit              #add it to end of rev_num

    return rev_num

#check if the number is a palindrome
def is_palindrome(n):
    num = str(n)
    rev_num = reverse_num(n)
    return num==rev_num

number = 196
step = 0
our_limit = 1000

while(not is_palindrome(number) and step < our_limit):
#terminate the loop when a palindrome is found
#or the number of iterations done reached our_limit
    step = step + 1
    rev_num = reverse_num(number)
    print 'Step',step,':',number,'+',rev_num,'=',
    number = number + int(rev_num) #reverses the number and add both
    print number