2020-09-04 MATH 3600

459 days ago by calkin

b=10 # This is the default number of digits def list_to_number(L,bb): # This function will take the digits of n in low to high order and compute the temp = 0 # number corresponding to the reversal of those digits for num in L: temp=temp*bb+num return(temp) #### Let's rename the function to rev(n) taking as input a number n, compute the digits, and return the reverse number. def rev(n): bb=10 temp=0 L=n.digits(bb) for num in L: temp=temp*bb+num return(temp) 
       
n=157 rev(n) 
       
751
751
list_to_number(n.digits(b),b) 
       
751
751
list_to_number(n.digits(3),3).digits(3) 
       
[1, 2, 2, 1, 1]
[1, 2, 2, 1, 1]
n.digits(3) 
       
[1, 1, 2, 2, 1]
[1, 1, 2, 2, 1]
 
       
for i in srange(10): print(i) 
       
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
j=2 while j<10^10: print(j) j=j^2 
       
2
4
16
256
65536
4294967296
2
4
16
256
65536
4294967296
 
       

Conditional statements.  We will often need to test whether a statement is true, and whether two quantities are equal, greater than, or less that.

We do this in "while" and "if - then - else" constructs.  We will also need "and" and "or".  To test equality, use ==.


a=2 b=2 print(a==b) 
       
True
True
print(x==b) 
       
x == 2
x == 2
a=3 print(a==b) 
       
False
False
print((a==b) or (a==3)) 
       
True
True
print((a==b) and (a==3)) 
       
False
False
print(a!=b) 
       
True
True
n=157 m=rev(n) counter = 0 while counter<20 and n<10^20: if m==n: break else: n=m+n m=rev(n) counter+=1 print n,m, counter 
       
8888 8888 3
8888 8888 3

Project revision: write a function which will take as input an integer $n$, and do the same as the above.

def add_until_pal(n): m=rev(n) counter=0 while counter<20 and n<10^100: if m==n: break else: n=m+n m=rev(n) counter+=1 print n,m,counter 
       
add_until_pal(157) 
       
8888 8888 3
8888 8888 3
x= add_until_pal(157) 
       
8888 8888 3
8888 8888 3
print(x) 
       
None
None

Rewrite the function, and instead of printing, use return() so that the function actually returns the values.

def add_until_pal(n): m=rev(n) counter=0 while counter<400: if m==n: break else: n=m+n m=rev(n) counter+=1 return( [n,m,counter]) 
       
x=add_until_pal(157) 
       
print(x) 
       
[8888, 8888, 3]
[8888, 8888, 3]
print(x[2]) 
       
3
3
num_steps=[] for i in srange(1,201): k=add_until_pal(i) num_steps.append([i,k[2] ]) 
       
print(num_steps) 
       
[[1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0], [8, 0], [9, 0],
[10, 1], [11, 0], [12, 1], [13, 1], [14, 1], [15, 1], [16, 1], [17, 1],
[18, 1], [19, 2], [20, 1], [21, 1], [22, 0], [23, 1], [24, 1], [25, 1],
[26, 1], [27, 1], [28, 2], [29, 1], [30, 1], [31, 1], [32, 1], [33, 0],
[34, 1], [35, 1], [36, 1], [37, 2], [38, 1], [39, 2], [40, 1], [41, 1],
[42, 1], [43, 1], [44, 0], [45, 1], [46, 2], [47, 1], [48, 2], [49, 2],
[50, 1], [51, 1], [52, 1], [53, 1], [54, 1], [55, 0], [56, 1], [57, 2],
[58, 2], [59, 3], [60, 1], [61, 1], [62, 1], [63, 1], [64, 2], [65, 1],
[66, 0], [67, 2], [68, 3], [69, 4], [70, 1], [71, 1], [72, 1], [73, 2],
[74, 1], [75, 2], [76, 2], [77, 0], [78, 4], [79, 6], [80, 1], [81, 1],
[82, 2], [83, 1], [84, 2], [85, 2], [86, 3], [87, 4], [88, 0], [89, 24],
[90, 1], [91, 2], [92, 1], [93, 2], [94, 2], [95, 3], [96, 4], [97, 6],
[98, 24], [99, 0], [100, 1], [101, 0], [102, 1], [103, 1], [104, 1],
[105, 1], [106, 1], [107, 1], [108, 1], [109, 2], [110, 1], [111, 0],
[112, 1], [113, 1], [114, 1], [115, 1], [116, 1], [117, 1], [118, 1],
[119, 2], [120, 1], [121, 0], [122, 1], [123, 1], [124, 1], [125, 1],
[126, 1], [127, 1], [128, 1], [129, 2], [130, 1], [131, 0], [132, 1],
[133, 1], [134, 1], [135, 1], [136, 1], [137, 1], [138, 1], [139, 2],
[140, 1], [141, 0], [142, 1], [143, 1], [144, 1], [145, 1], [146, 1],
[147, 1], [148, 1], [149, 2], [150, 2], [151, 0], [152, 2], [153, 2],
[154, 2], [155, 3], [156, 3], [157, 3], [158, 3], [159, 2], [160, 2],
[161, 0], [162, 2], [163, 2], [164, 3], [165, 3], [166, 5], [167, 11],
[168, 3], [169, 2], [170, 2], [171, 0], [172, 2], [173, 2], [174, 4],
[175, 4], [176, 5], [177, 15], [178, 3], [179, 2], [180, 3], [181, 0],
[182, 6], [183, 4], [184, 3], [185, 3], [186, 3], [187, 23], [188, 7],
[189, 2], [190, 7], [191, 0], [192, 4], [193, 8], [194, 3], [195, 4],
[196, 2393], [197, 7], [198, 5], [199, 3], [200, 1]]
[[1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0], [8, 0], [9, 0], [10, 1], [11, 0], [12, 1], [13, 1], [14, 1], [15, 1], [16, 1], [17, 1], [18, 1], [19, 2], [20, 1], [21, 1], [22, 0], [23, 1], [24, 1], [25, 1], [26, 1], [27, 1], [28, 2], [29, 1], [30, 1], [31, 1], [32, 1], [33, 0], [34, 1], [35, 1], [36, 1], [37, 2], [38, 1], [39, 2], [40, 1], [41, 1], [42, 1], [43, 1], [44, 0], [45, 1], [46, 2], [47, 1], [48, 2], [49, 2], [50, 1], [51, 1], [52, 1], [53, 1], [54, 1], [55, 0], [56, 1], [57, 2], [58, 2], [59, 3], [60, 1], [61, 1], [62, 1], [63, 1], [64, 2], [65, 1], [66, 0], [67, 2], [68, 3], [69, 4], [70, 1], [71, 1], [72, 1], [73, 2], [74, 1], [75, 2], [76, 2], [77, 0], [78, 4], [79, 6], [80, 1], [81, 1], [82, 2], [83, 1], [84, 2], [85, 2], [86, 3], [87, 4], [88, 0], [89, 24], [90, 1], [91, 2], [92, 1], [93, 2], [94, 2], [95, 3], [96, 4], [97, 6], [98, 24], [99, 0], [100, 1], [101, 0], [102, 1], [103, 1], [104, 1], [105, 1], [106, 1], [107, 1], [108, 1], [109, 2], [110, 1], [111, 0], [112, 1], [113, 1], [114, 1], [115, 1], [116, 1], [117, 1], [118, 1], [119, 2], [120, 1], [121, 0], [122, 1], [123, 1], [124, 1], [125, 1], [126, 1], [127, 1], [128, 1], [129, 2], [130, 1], [131, 0], [132, 1], [133, 1], [134, 1], [135, 1], [136, 1], [137, 1], [138, 1], [139, 2], [140, 1], [141, 0], [142, 1], [143, 1], [144, 1], [145, 1], [146, 1], [147, 1], [148, 1], [149, 2], [150, 2], [151, 0], [152, 2], [153, 2], [154, 2], [155, 3], [156, 3], [157, 3], [158, 3], [159, 2], [160, 2], [161, 0], [162, 2], [163, 2], [164, 3], [165, 3], [166, 5], [167, 11], [168, 3], [169, 2], [170, 2], [171, 0], [172, 2], [173, 2], [174, 4], [175, 4], [176, 5], [177, 15], [178, 3], [179, 2], [180, 3], [181, 0], [182, 6], [183, 4], [184, 3], [185, 3], [186, 3], [187, 23], [188, 7], [189, 2], [190, 7], [191, 0], [192, 4], [193, 8], [194, 3], [195, 4], [196, 2393], [197, 7], [198, 5], [199, 3], [200, 1]]
list_plot(num_steps) 
       
add_until_pal(196) 
       
[17598541086689945285167338888136924288805444688910008977928788773762536\
519077974571756366911993393434782401552465528056338524602204376595030972\
735063663114734068362130271430753931211084819379031297892773439906399816\
913425753535209739440454403032766827597511014891217864537722157550462857\
424163137981007446711462668213200410655819551530490964273407554647454691\
945764170495146024903893727181079426005426162977372204718710325222501730\
855479191146026372088458825244451771560830080840286599901910827475568669\
754648271281090065720590799389562771534415299537901836305322809854491370\
953126130177184913827793516244007240791916183883104106425851713585401865\
647365546044814790830361569075669040132028772631167537091897313615247581\
540657601377344687122093002257957177772292054451449368036243586144087180\
045990432773097920210829185800022384669341819321648593483023564695471701\
294957734912074257347498355543540152765334042891197735581753697709255461\
584777788208798000187964445989724197407899337516824400856910457967,
 76975401965800442861573399870479142798954446978100089780288777748516455\
290779635718553779119824043356725104534555389474375247021943775949210717\
459646532038439584612391814396648322000858192801202979037723409954008178\
044168534263086394415445029227777175975220039022178644377310675604518574\
251631379819073576113627782023104096657096516303809741844064556374656810\
458531715852460140138838161919704270044261539772831948177103162135907319\
445890822350363810973599251443517726598399709502756009018217284645796686\
557472801910999568204808003806517715444252885488027362064119197455803710\
522252301781740227377926162450062497018172739830942064159407146754919645\
474645570437246909403515591855601400231286626411764470018973136142475826\
405575122773546871219841011579572866723030445404493790253535752431961899\
360993437729879213097391848011213935703417203126386043741136636053727903\
059567340220642583365082556425510428743439339911966365717547977091563526\
737788782977980001988644450888242963188883376158254998668014589571,
 2393]
[17598541086689945285167338888136924288805444688910008977928788773762536519077974571756366911993393434782401552465528056338524602204376595030972735063663114734068362130271430753931211084819379031297892773439906399816913425753535209739440454403032766827597511014891217864537722157550462857424163137981007446711462668213200410655819551530490964273407554647454691945764170495146024903893727181079426005426162977372204718710325222501730855479191146026372088458825244451771560830080840286599901910827475568669754648271281090065720590799389562771534415299537901836305322809854491370953126130177184913827793516244007240791916183883104106425851713585401865647365546044814790830361569075669040132028772631167537091897313615247581540657601377344687122093002257957177772292054451449368036243586144087180045990432773097920210829185800022384669341819321648593483023564695471701294957734912074257347498355543540152765334042891197735581753697709255461584777788208798000187964445989724197407899337516824400856910457967,
 76975401965800442861573399870479142798954446978100089780288777748516455290779635718553779119824043356725104534555389474375247021943775949210717459646532038439584612391814396648322000858192801202979037723409954008178044168534263086394415445029227777175975220039022178644377310675604518574251631379819073576113627782023104096657096516303809741844064556374656810458531715852460140138838161919704270044261539772831948177103162135907319445890822350363810973599251443517726598399709502756009018217284645796686557472801910999568204808003806517715444252885488027362064119197455803710522252301781740227377926162450062497018172739830942064159407146754919645474645570437246909403515591855601400231286626411764470018973136142475826405575122773546871219841011579572866723030445404493790253535752431961899360993437729879213097391848011213935703417203126386043741136636053727903059567340220642583365082556425510428743439339911966365717547977091563526737788782977980001988644450888242963188883376158254998668014589571,
 2393]

Questions to investigate.

1. Does every number end up as a palindrome?

2. If so, after how many steps?  (Average, maximum, distribution, etc)

3. If not, what proportion of numbers up to $N$ do end up with a palindrome?  How many steps needed for those that terminate (Average, maximum, distribution, etc).

For large $N$ won't be able to compute everything: will need to sample random numbers in the range.

How do we generate a random integer?  That is, given an integer $N$, generate a uniformly chosen element  $n$ in $\mathbb Z$ in the range $0\leq n< N$.

We use ZZ.random_element(0,N).

print(ZZ.random_element(0,10^20)) 
       
55667190204002510731
55667190204002510731
add_until_pal(55667190204002510731) 
       
[71100854945863081576402140792285354115900996686455214828363530208578202\
628758483331394059123552229494041333738579352028767910363648185026535877\
8811951046357239704120368518025953955700216,
 61200755935952081586302140793275364015911887785356205818463630197678202\
539758373331404949222553219504931333848578262028758020353638284125546866\
9900951145358229704120467518036854945800117,
 400]
[711008549458630815764021407922853541159009966864552148283635302085782026287584833313940591235522294940413337385793520287679103636481850265358778811951046357239704120368518025953955700216,
 612007559359520815863021407932753640159118877853562058184636301976782025397583733314049492225532195049313338485782620287580203536382841255468669900951145358229704120467518036854945800117,
 400]
n=ZZ.random_element(0,10^20) add_until_pal(n) 
       
[19181517278208464552588985362945058247014013982004004984801826539815355\
346656767704734726419390987458171642367619853200115476764676611596156011\
012233407623570257554367690938242980570307321841428075878556393160727574\
657830673270111811835315029001287295112996965396509339242012894476302836\
506287039624734012518154801930079755093130872446428606555584656701519695\
620603936959606755047978166767853928785328009851162733817424224639855570\
658771805902270503215403619223345595293673285453693011875702025943855996\
573506191076880013863654734763914956423339054036213149623194982777471755\
588274233246183382512580107136968284578677509797415566059606294160254970\
151966663954557158345353671403015469701381085519151005464259317727155391\
936753882102430438946946685993215828810108314045281192110712870377653856\
380503946458894708341381247030750792339390966633558619664257034322012106\
515851167765665755120023480257632460818538990830147263385076675665446524\
189466182073904993112883203017338406592536898742664638019718141928,
 82914181791083646624789863529560483371030238821139940937028166498142564\
456657667058336274103809983581806423675208432002155756656776115851560121\
022343075246691685533666909393329705703074218314380749885464930508365835\
677307821701129118254041380101882851239958664964983403420128835763919355\
172771395246450015191558018310796451030417635354385175545936666915107945\
206149260695066551479790577687548286963170108521528338164233247288555717\
477728949132694131263045093332465941936743745636831008867019160537569955\
834952020757811039635458237639259554332291630451230507220950817785607555\
893642242471833726115890082358782935876766187974055760695963930602659691\
510765648555560682464427803139055797003910845181521043742693078260563820\
367449821024293390569356969921159278210092051353811811107237603875647572\
706139365587857082414812370307508924283909676345575207532670433221011065\
169511667646767451100235891676324617185478909391462743740776765664355351\
893562810848940040028931041074285054926358988525546480287271518191,
 2366]
[19181517278208464552588985362945058247014013982004004984801826539815355346656767704734726419390987458171642367619853200115476764676611596156011012233407623570257554367690938242980570307321841428075878556393160727574657830673270111811835315029001287295112996965396509339242012894476302836506287039624734012518154801930079755093130872446428606555584656701519695620603936959606755047978166767853928785328009851162733817424224639855570658771805902270503215403619223345595293673285453693011875702025943855996573506191076880013863654734763914956423339054036213149623194982777471755588274233246183382512580107136968284578677509797415566059606294160254970151966663954557158345353671403015469701381085519151005464259317727155391936753882102430438946946685993215828810108314045281192110712870377653856380503946458894708341381247030750792339390966633558619664257034322012106515851167765665755120023480257632460818538990830147263385076675665446524189466182073904993112883203017338406592536898742664638019718141928,
 82914181791083646624789863529560483371030238821139940937028166498142564456657667058336274103809983581806423675208432002155756656776115851560121022343075246691685533666909393329705703074218314380749885464930508365835677307821701129118254041380101882851239958664964983403420128835763919355172771395246450015191558018310796451030417635354385175545936666915107945206149260695066551479790577687548286963170108521528338164233247288555717477728949132694131263045093332465941936743745636831008867019160537569955834952020757811039635458237639259554332291630451230507220950817785607555893642242471833726115890082358782935876766187974055760695963930602659691510765648555560682464427803139055797003910845181521043742693078260563820367449821024293390569356969921159278210092051353811811107237603875647572706139365587857082414812370307508924283909676345575207532670433221011065169511667646767451100235891676324617185478909391462743740776765664355351893562810848940040028931041074285054926358988525546480287271518191,
 2366]

To investigate how many integers in the range (0,N) end in a palindrome, select random integers in the range,

and test how long they take, and whether they terminate.  Keep track of how many integers you've tested, and 

how many become palindromes.

num_tested=0 num_pals=0 for i in srange(1000): n=ZZ.random_element(0,10^10) k=add_until_pal(n) if k[0]==k[1]: num_pals+=1 num_tested+=1 print(num_pals,num_tested) 
       
(527, 1000)
(527, 1000)
196+rev(196) 
       
887
887
887+rev(887) 
       
1675
1675
rev(1675) 
       
5761
5761
1675+rev(1675) 
       
7436
7436
7436+rev(7436) 
       
13783
13783
13783+rev(13783) 
       
52514
52514
52514 + rev(52514) 
       
94039
94039
94039+rev(94039) 
       
187088
187088
187088+rev(187088) 
       
1067869
1067869
1067869+rev(1067869) 
       
10755470
10755470
10755470+rev(10755470) 
       
18211171
18211171
18211171+rev(18211171) 
       
35322452
35322452
35322452+rev(35322452) 
       
60744805
60744805
60744805+rev(60744805) 
       
111589511
111589511
111589511+rev(111589511) 
       
227574622
227574622
matrix(111589511.digits())-matrix(rev(111589511).digits()) 
       
[ 0  0  4  4  0 -4 -4  0  0]
[ 0  0  4  4  0 -4 -4  0  0]

For the first $N$ iterates of 196, what proportion of the digits of the iterate and its reverse the same?

Also examing Connor and Spencer's ideas of how to measure the distance between the iterate and its reverse.

Do the same thing for random integers in the range $(0,10^{20})$.


If you pick a random number in the range $10^{20}$, and do exactly one iteration, how many digits would you expect to be the same in its reversal?