# 2021.08.25 MATH 3600 loops

## 275 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)
  
d=mod(c,10^20) print(type(d)) d=Integer(d) print(type(d))
    
 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)
  
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