Reverse-add-palindrome

686 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?

 

Let's construct a function add_til_pal(n,b)

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]) 
       
add_til_pal(248,10) 
       
[1991, 2]
[1991, 2]
add_til_pal(196,10) 
       
[17507933051084611082966952558975958114804408365576204222897384455555455\
34946981225126744738044974228585887562506602702253911502307957,
 300]
[1750793305108461108296695255897595811480440836557620422289738445555545534946981225126744738044974228585887562506602702253911502307957,
 300]
for i in srange(1000,2000): c=add_til_pal(i,10) if c[1]>11 and c[1]<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)[1] 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]
add_til_pal(196,10)[1] 
       
300
300
for i in srange(30): print ZZ.random_element(10^6,10^7) 
       
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