## 863 days ago by calkin

This worksheet is to explore the reverse and add until palindrome problem.

Questions:

Why do we think the process will terminate?

How many steps on average/worst case will it take to terminate?

How many digits will there be in the terminating number compared to starting number?

What happens in other bases, especially binary?

Let's start with a number $b$, and use digits() to get a list of its digits.

To convert a list $L$ of digits back into a number, use ZZ(L,base=10)

This worksheet is to explore the reverse and add until palindrome problem.

Questions:

- Why do we think the process will terminate?

- How many steps on average/worst case will it take to terminate?

- How many digits will there be in the terminating number compared to starting number?

- What happens in other bases, especially binary?

- What happens in base 10 starting with 196?  How fast do the iterates grow?

- What proportion of numbers less than $10^k$ terminate quickly? 246 of first 10000 do not terminate quickly.

- What is the first number to terminate in exactly $k$ steps?

- For which numbers $k$ are there inputs that terminate in exactly $k$ steps? Is $k=24$ the largest value?

- How close to palindromic are the iterates of 196?  That is, how many digits of the iterate are the same in the reverse?

- What is the probability that a random number with $k$ digits doesn't terminate quickly?  Is it increasing as a function of $k$?  Does it tend to a limit?  Does it tend to 1?

which takes a number n, checks if it is a palindrome: if it is, it returns the list [n,0]

otherwise it reverses and adds, until the result is a palindrome, and returns the

palindrome and the number of adds.

def add_til_pal(n,b): S=300 # number of steps before giving up m=n is_palindrome=0 counter = 0 L1=n.digits(base=b) L2=n.digits(base=b) L2.reverse() if L1==L2: return(m,0) else: while is_palindrome==0 and counter<S: counter+=1 m=m+ZZ(L2,base=b) L1= m.digits(base=b) L2= m.digits(base=b) L2.reverse() if L1==L2: is_palindrome=1 if is_palindrome == 1: return([m,counter]) else: return([m,counter])
 [1991, 2] [1991, 2]
 [17507933051084611082966952558975958114804408365576204222897384455555455\ 34946981225126744738044974228585887562506602702253911502307957, 300] [1750793305108461108296695255897595811480440836557620422289738445555545534946981225126744738044974228585887562506602702253911502307957, 300]
for i in srange(1000,2000): c=add_til_pal(i,10) if c>11 and c<299: print i, add_til_pal(i,10)
 1297 [8813200023188, 21] 1387 [8813200023188, 21] 1477 [8813200023188, 21] 1496 [5233333325, 16] 1567 [8813200023188, 21] 1586 [5233333325, 16] 1657 [8813200023188, 21] 1676 [5233333325, 16] 1747 [8813200023188, 21] 1766 [5233333325, 16] 1792 [5233333325, 17] 1797 [8836886388, 13] 1798 [89540004598, 18] 1837 [8813200023188, 21] 1856 [5233333325, 16] 1882 [5233333325, 17] 1887 [8836886388, 13] 1888 [89540004598, 18] 1894 [52788725, 13] 1897 [133697796331, 16] 1927 [8813200023188, 21] 1946 [5233333325, 16] 1972 [5233333325, 17] 1977 [8836886388, 13] 1978 [89540004598, 18] 1984 [52788725, 13] 1987 [133697796331, 16] 1998 [8939779398, 15] 1297 [8813200023188, 21] 1387 [8813200023188, 21] 1477 [8813200023188, 21] 1496 [5233333325, 16] 1567 [8813200023188, 21] 1586 [5233333325, 16] 1657 [8813200023188, 21] 1676 [5233333325, 16] 1747 [8813200023188, 21] 1766 [5233333325, 16] 1792 [5233333325, 17] 1797 [8836886388, 13] 1798 [89540004598, 18] 1837 [8813200023188, 21] 1856 [5233333325, 16] 1882 [5233333325, 17] 1887 [8836886388, 13] 1888 [89540004598, 18] 1894 [52788725, 13] 1897 [133697796331, 16] 1927 [8813200023188, 21] 1946 [5233333325, 16] 1972 [5233333325, 17] 1977 [8836886388, 13] 1978 [89540004598, 18] 1984 [52788725, 13] 1987 [133697796331, 16] 1998 [8939779398, 15]
Frequencies = [ 0 for i in srange(301)]
for i in srange(1,10000): c=add_til_pal(i,10) if c<301: Frequencies[c]+=1
list_plot(Frequencies[:40],ymax=100) print Frequencies[0:30]
 [396, 5578, 5658, 2682, 1792, 830, 798, 488, 114, 126, 24, 98, 220, 134, 6, 164, 116, 26, 54, 0, 52, 128, 4, 14, 4, 0, 0, 0, 0, 0] [396, 5578, 5658, 2682, 1792, 830, 798, 488, 114, 126, 24, 98, 220, 134, 6, 164, 116, 26, 54, 0, 52, 128, 4, 14, 4, 0, 0, 0, 0, 0]
 300 300
 1272747 5963683 8613558 1818976 1409802 6383387 8064601 3530173 2772552 3311203 9912452 8499231 5620925 9802016 2048325 4225327 4784463 8409567 1939734 2077216 7991525 9227870 4861863 4133748 8674637 8157753 9774887 2259981 9094516 5871388 1272747 5963683 8613558 1818976 1409802 6383387 8064601 3530173 2772552 3311203 9912452 8499231 5620925 9802016 2048325 4225327 4784463 8409567 1939734 2077216 7991525 9227870 4861863 4133748 8674637 8157753 9774887 2259981 9094516 5871388