Palindrome Root

Computer Science Level 5

Most of the positive integers can form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers. For example, for the number 19,

$\begin{aligned} 19 + 91 &= 110 \\ 110+011 &= 121\end{aligned}$

can form the palindrome 121 after 2 iterations. In this case, we call 19 the root of palindrome 121. A number $n$ is the root of palindrome $p$ if it is the smallest number such that after going through some number of iterations the first palindrome it forms is $p$ .

What is the root of the following number?

4668731596684224866951378664

Clarification :

Although 7 can form 121 after some number of iterations, it is not the root of 121 because the first palindrome formed by it is 55.

The answer is 10677.

2 solutions

Christopher Boo
Jul 8, 2016

I'm not sure why there is a very low success rate. Here is the code. Start from every number and let it go through the iterative process.

def is_pal(n):
    s = str(n)
    return s == s[::-1]

def transform(n):
    return n + int(str(n)[::-1])

target = 4668731596684224866951378664

n = 1
found = False
while not found:
    t = n
    while t < target:
        t = transform(t)
        if t == target:
            found = True
            print n
        elif is_pal(t):
            break
    n += 1

I suspect the bug most of the people make is line 19 and 20. If you doesn't break the process after it founds its first palindrome, you are going to get the answer 10137, but the answer is really 10677.

The success rate was low because, everyone was trying to find the root starting with the input, instead of starting with a guess root and working towards the target string.

Siva Bathula - 4 years, 11 months ago

In your question, you said that "we call 19 the root of the palindrome 121", but you didn't establish that the 19 is indeed the smallest number. Can you clean up the phrasing?

Calvin Lin Staff - 4 years, 11 months ago

"A number $n$ is the root of palindrome $p$ if it is the smallest number such that after going through some number of iterations the first palindrome it forms is $p$ ."

Is this better now?

Christopher Boo - 4 years, 11 months ago

Rushikesh Jogdand
Jul 10, 2016

def is_palin(n):
    return str(n)==str(n)[::-1]
def first_palin_less_than(n,upper_bound):
    tmp=n+0
    while tmp<upper_bound:
        if is_palin(tmp):break
        tmp+=int(str(tmp)[::-1])
    return tmp
def root(n):
    candidate=1
    while True:
        if first_palin_less_than(candidate,n)==n:return candidate
        candidate+=1
print(root(4668731596684224866951378664))

I am disappointed. I was hoping for an algorithm other than brute force.

Terry Smith - 4 years, 10 months ago

Palindrome Root

The answer is 10677.

2 solutions

0 pending reports