2021.08.25 MATH 3600 loops

98 days ago by calkin

2 types of loops 

for loops

while loops

Let's use a while loop to compute $F_{10}$. 

F0=0 F1=1 a=F1 b=F0 counter=2 while counter<11: c=a+b print(counter,c,a,b) b=a a=c counter+=1 #counter=counter+1 
       
(2, 1, 1, 0)
(3, 2, 1, 1)
(4, 3, 2, 1)
(5, 5, 3, 2)
(6, 8, 5, 3)
(7, 13, 8, 5)
(8, 21, 13, 8)
(9, 34, 21, 13)
(10, 55, 34, 21)
(2, 1, 1, 0)
(3, 2, 1, 1)
(4, 3, 2, 1)
(5, 5, 3, 2)
(6, 8, 5, 3)
(7, 13, 8, 5)
(8, 21, 13, 8)
(9, 34, 21, 13)
(10, 55, 34, 21)

We have successfully computed $F_{10}=55$!

F0=0 F1=1 n=10^3 # We want to compute F(n) a=F1 b=F0 counter=2 while counter<= n: c=a+b # print(counter,c,a,b) #This print statement was a check that we don't need. b=a a=c counter+=1 print(counter-1, c) 
       
(1000,
434665576869374564356885276750406258025646605173717804024817290895365554\
179490518904038798400792551692959225930803226347752096896232398733224711\
61642996440906533187938298969649928516003704476137795166849228875)
(1000, 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875)
mod(c,10^20) 
       
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
d=mod(c,10^20) print(type(d)) d=Integer(d) print(type(d)) 
       
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
<type 'sage.rings.integer.Integer'>
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
<type 'sage.rings.integer.Integer'>
       
76137795166849228875
76137795166849228875

We have code that works nicely to compute $F_n$.  Let us do the calculations modulo $10^{20}$.

F0=mod(0,10^20) F1=1 n=10^7 # We want to compute F(n) a=F1 b=F0 counter=2 while counter<= n: c=a+b # print(counter,c,a,b) #This print statement was a check that we don't need. b=a a=c counter+=1 print(counter-1, c) 
       
(10000000, 86998673686380546875)
(10000000, 86998673686380546875)
type(c) 
       
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
fibonacci(10) 
       
55
55
mod( fibonacci(10^8), 10^20) 
       
6082642167760546875
6082642167760546875

Challenge: compute $F_n $ mod $10^{20}$ quickly for $n$ much bigger than $10^8$.

Can you compute $F_n$ where $n=7^{CUID}$

7^99999999