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.
Program:
#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
