Fibonacci

2250 days ago by calkin

t=cputime() fibonacci(100) print cputime(t) 
        
0.000833
0.000833
t=cputime() fibonacci(1000) print cputime(t) 
        
0.000124
0.000124
t=cputime() fibonacci(10000) print cputime(t) 
        
0.00011
0.00011
t=cputime() fibonacci(10000000) print cputime(t) 
        
0.314409
0.314409
def my_fib(n): i=0 a=0 b=1 while i<n: (a,b)=((a+b)% 10^100,a ) i+=1 return(a) 
       
my_fib(200000) 
        
486192612635235963032921420195770467711978919314265479877731245093503108\
9429802652246259408175853125
4861926126352359630329214201957704677119789193142654798777312450935031089429802652246259408175853125
fibonacci(200000)%10^100 
        
486192612635235963032921420195770467711978919314265479877731245093503108\
9429802652246259408175853125
4861926126352359630329214201957704677119789193142654798777312450935031089429802652246259408175853125
t=cputime() my_fib(1000) print cputime(t) 
        
0.001056
0.001056
t=cputime() my_fib(10000) print cputime(t) 
        
0.010389
0.010389
t=cputime() my_fib(100000) print cputime(t) 
        
0.088563
0.088563
t=cputime() my_fib(1000000) print cputime(t) 
        
0.703061
0.703061
t=cputime() my_fib(10000000) print cputime(t) 
        
6.452606
6.452606
2^9 
        
512
512
99999999*log(2.)/log(10.) 
        
3.01029992653681e7
3.01029992653681e7
fibonacci(85) 
        
259695496911122585
259695496911122585
fibonacci(84) 
        
160500643816367088
160500643816367088
exp(1.) 
        
2.71828182845905
2.71828182845905
def check_period(k): i=1 a=1 b=1 while (a==0 and b==1)==False: (a,b)=(b,a+b) a=Integer(a%k) b=Integer(b%k) i+=1 return(i) 
       
check_period(2) 
        
3
3
check_period(3) 
        
8
8
check_period(4) 
        
6
6
for k in srange(2,100): print k, check_period(k),k^2-1 
        
2 3 3
3 8 8
4 6 15
5 20 24
6 24 35
7 16 48
8 12 63
9 24 80
10 60 99
11 10 120
12 24 143
13 28 168
14 48 195
15 40 224
16 24 255
17 36 288
18 24 323
19 18 360
20 60 399
21 16 440
22 30 483
23 48 528
24 24 575
25 100 624
26 84 675
27 72 728
28 48 783
29 14 840
30 120 899
31 30 960
32 48 1023
33 40 1088
34 36 1155
35 80 1224
36 24 1295
37 76 1368
38 18 1443
39 56 1520
40 60 1599
41 40 1680
42 48 1763
43 88 1848
44 30 1935
45 120 2024
46 48 2115
47 32 2208
48 24 2303
49 112 2400
50 300 2499
51 72 2600
52 84 2703
53 108 2808
54 72 2915
55 20 3024
56 48 3135
57 72 3248
58 42 3363
59 58 3480
60 120 3599
61 60 3720
62 30 3843
63 48 3968
64 96 4095
65 140 4224
66 120 4355
67 136 4488
68 36 4623
69 48 4760
70 240 4899
71 70 5040
72 24 5183
73 148 5328
74 228 5475
75 200 5624
76 18 5775
77 80 5928
78 168 6083
79 78 6240
80 120 6399
81 216 6560
82 120 6723
83 168 6888
84 48 7055
85 180 7224
86 264 7395
87 56 7568
88 60 7743
89 44 7920
90 120 8099
91 112 8280
92 48 8463
93 120 8648
94 96 8835
95 180 9024
96 48 9215
97 196 9408
98 336 9603
99 120 9800
2 3 3
3 8 8
4 6 15
5 20 24
6 24 35
7 16 48
8 12 63
9 24 80
10 60 99
11 10 120
12 24 143
13 28 168
14 48 195
15 40 224
16 24 255
17 36 288
18 24 323
19 18 360
20 60 399
21 16 440
22 30 483
23 48 528
24 24 575
25 100 624
26 84 675
27 72 728
28 48 783
29 14 840
30 120 899
31 30 960
32 48 1023
33 40 1088
34 36 1155
35 80 1224
36 24 1295
37 76 1368
38 18 1443
39 56 1520
40 60 1599
41 40 1680
42 48 1763
43 88 1848
44 30 1935
45 120 2024
46 48 2115
47 32 2208
48 24 2303
49 112 2400
50 300 2499
51 72 2600
52 84 2703
53 108 2808
54 72 2915
55 20 3024
56 48 3135
57 72 3248
58 42 3363
59 58 3480
60 120 3599
61 60 3720
62 30 3843
63 48 3968
64 96 4095
65 140 4224
66 120 4355
67 136 4488
68 36 4623
69 48 4760
70 240 4899
71 70 5040
72 24 5183
73 148 5328
74 228 5475
75 200 5624
76 18 5775
77 80 5928
78 168 6083
79 78 6240
80 120 6399
81 216 6560
82 120 6723
83 168 6888
84 48 7055
85 180 7224
86 264 7395
87 56 7568
88 60 7743
89 44 7920
90 120 8099
91 112 8280
92 48 8463
93 120 8648
94 96 8835
95 180 9024
96 48 9215
97 196 9408
98 336 9603
99 120 9800
for j in srange(1,9): print j,check_period(10^j) 
        
1 60
2 300
3 1500
4 15000
5 150000
6 1500000
7 15000000
8 150000000
1 60
2 300
3 1500
4 15000
5 150000
6 1500000
7 15000000
8 150000000
check_period(8),check_period(125) 
        
(12, 500)
(12, 500)
for j in srange(1,10): print j,check_period(2^j),check_period(5^j) 
        
1 3 20
2 6 100
3 12 500
4 24 2500
5 48 12500
6 96 62500
7 192 312500
8 384 1562500
9 768 7812500
1 3 20
2 6 100
3 12 500
4 24 2500
5 48 12500
6 96 62500
7 192 312500
8 384 1562500
9 768 7812500
def predict_period(p): if is_prime(p): if (Integer(p%5)==1) or (Integer(p%5)==4): return(p-1) if (Integer(p%5)==2) or (Integer(p%5)==3): return(2*(p+1)) 
       
j=13 while j<1000: if (check_period(j)==predict_period(j))==False: print j%5,j,check_period(j), predict_period(j)/check_period( j=next_prime(j) 
        
4 29 14 2
2 47 32 3
4 89 44 2
1 101 50 2
2 107 72 3
3 113 76 3
4 139 46 3
1 151 50 3
1 181 90 2
4 199 22 9
1 211 42 5
4 229 114 2
3 233 52 9
3 263 176 3
1 281 56 5
2 307 88 7
1 331 110 3
2 347 232 3
4 349 174 2
3 353 236 3
1 401 200 2
1 421 84 5
1 461 46 10
4 509 254 2
1 521 26 20
1 541 90 6
2 557 124 9
3 563 376 3
4 619 206 3
1 661 220 3
2 677 452 3
1 691 138 5
4 709 118 6
3 743 496 3
1 761 380 2
4 769 192 4
2 797 228 7
4 809 202 4
1 811 270 3
4 829 276 3
4 859 78 11
1 881 176 5
1 911 70 13
4 919 102 9
1 941 470 2
3 953 212 9
2 967 176 11
2 977 652 3
1 991 198 5
4 29 14 2
2 47 32 3
4 89 44 2
1 101 50 2
2 107 72 3
3 113 76 3
4 139 46 3
1 151 50 3
1 181 90 2
4 199 22 9
1 211 42 5
4 229 114 2
3 233 52 9
3 263 176 3
1 281 56 5
2 307 88 7
1 331 110 3
2 347 232 3
4 349 174 2
3 353 236 3
1 401 200 2
1 421 84 5
1 461 46 10
4 509 254 2
1 521 26 20
1 541 90 6
2 557 124 9
3 563 376 3
4 619 206 3
1 661 220 3
2 677 452 3
1 691 138 5
4 709 118 6
3 743 496 3
1 761 380 2
4 769 192 4
2 797 228 7
4 809 202 4
1 811 270 3
4 829 276 3
4 859 78 11
1 881 176 5
1 911 70 13
4 919 102 9
1 941 470 2
3 953 212 9
2 967 176 11
2 977 652 3
1 991 198 5
for i in srange(30): (fibonacci(i)).binary() 
        
'0'
'1'
'1'
'10'
'11'
'101'
'1000'
'1101'
'10101'
'100010'
'110111'
'1011001'
'10010000'
'11101001'
'101111001'
'1001100010'
'1111011011'
'11000111101'
'101000011000'
'1000001010101'
'1101001101101'
'10101011000010'
'100010100101111'
'110111111110001'
'1011010100100000'
'10010010100010001'
'11101101000110001'
'101111111101000010'
'1001101100101110011'
'1111101100010110101'
'0'
'1'
'1'
'10'
'11'
'101'
'1000'
'1101'
'10101'
'100010'
'110111'
'1011001'
'10010000'
'11101001'
'101111001'
'1001100010'
'1111011011'
'11000111101'
'101000011000'
'1000001010101'
'1101001101101'
'10101011000010'
'100010100101111'
'110111111110001'
'1011010100100000'
'10010010100010001'
'11101101000110001'
'101111111101000010'
'1001101100101110011'
'1111101100010110101'