2022.10.12 MATH 3600-001 Pisano

301 days ago by calkin

def pisano(m): a=1 # second Fib number b=1 # first Fib number counter = 1 while [b,a] != [0,1]: a,b=a+b,a a=a%m b=b%m counter+=1 return(counter) 
       
pisano(3) 
        
8
8
pisano(10) 
        
60
60
pisano(10^2) 
        
300
300
pisano(10^3) 
        
1500
1500
pisano(10^4) 
        
15000
15000
pisano(10^5) 
        
150000
150000
pisano(10^6) 
        
1500000
1500000
pisano(10^7) 
        
15000000
15000000
pisano(10^8) 
        
150000000
150000000
t=cputime() print(pisano(10^7)) print(cputime()-t) 
        
15000000
10.746151
15000000
10.746151
n=4 
       
n.next_prime() 
        
5
5
prime_pisano_periods=[] N=2000 p=2 while p<N: pip=pisano(p) prime_pisano_periods.append([p,pisano(p)]) p=p.next_prime() list_plot(prime_pisano_periods) 
       
print(prime_pisano_periods) 
        
[[3, 8], [5, 20], [7, 16], [13, 28], [17, 36], [23, 48], [37, 76], [43,
88], [53, 108], [67, 136], [73, 148], [83, 168], [97, 196], [103, 208],
[127, 256], [137, 276], [157, 316], [163, 328], [167, 336], [173, 348],
[193, 388], [197, 396]]
[[3, 8], [5, 20], [7, 16], [13, 28], [17, 36], [23, 48], [37, 76], [43, 88], [53, 108], [67, 136], [73, 148], [83, 168], [97, 196], [103, 208], [127, 256], [137, 276], [157, 316], [163, 328], [167, 336], [173, 348], [193, 388], [197, 396]]
prime_pisano_periods=[] N=200 p=2 while p<N: pip=pisano(p) if pip>3*p/2: prime_pisano_periods.append([p,pisano(p)]) p=p.next_prime() list_plot(prime_pisano_periods) 
       
prime_pisano_periods=[] N=200 p=2 while p<N: pip=pisano(p) if pip<3*p/2 and pip>3*p/4: prime_pisano_periods.append([p,pisano(p)]) p=p.next_prime() list_plot(prime_pisano_periods) 
       
print(prime_pisano_periods) 
        
[[11, 10], [19, 18], [31, 30], [41, 40], [59, 58], [61, 60], [71, 70],
[79, 78], [109, 108], [131, 130], [149, 148], [179, 178], [191, 190]]
[[11, 10], [19, 18], [31, 30], [41, 40], [59, 58], [61, 60], [71, 70], [79, 78], [109, 108], [131, 130], [149, 148], [179, 178], [191, 190]]
prime_pisano_periods=[] N=2000 p=2 while p<N: pip=pisano(p) if pip<2*p/3+3 and pip>2*p/3-3: prime_pisano_periods.append([p,pisano(p)]) p=p.next_prime() show(list_plot(prime_pisano_periods)) print(prime_pisano_periods) 
        
[[2, 3], [11, 10], [47, 32], [107, 72], [113, 76], [263, 176], [347,
232], [353, 236], [563, 376], [677, 452], [743, 496], [977, 652], [1097,
732], [1217, 812], [1223, 816], [1277, 852], [1307, 872], [1523, 1016],
[1553, 1036], [1733, 1156], [1823, 1216], [1877, 1252], [1913, 1276],
[1973, 1316]]
[[2, 3], [11, 10], [47, 32], [107, 72], [113, 76], [263, 176], [347, 232], [353, 236], [563, 376], [677, 452], [743, 496], [977, 652], [1097, 732], [1217, 812], [1223, 816], [1277, 852], [1307, 872], [1523, 1016], [1553, 1036], [1733, 1156], [1823, 1216], [1877, 1252], [1913, 1276], [1973, 1316]]
prime_pisano_periods=[] N=2000 p=2 while p<N: pip=pisano(p) #if pip<2*p/3+3 and pip>2*p/3-3: if pip==(p-1)/3: prime_pisano_periods.append([p,pisano(p)]) p=p.next_prime() show(list_plot(prime_pisano_periods)) print(prime_pisano_periods) 
        
[[139, 46], [151, 50], [331, 110], [619, 206], [661, 220], [811, 270],
[829, 276], [1069, 356], [1231, 410], [1279, 426], [1291, 430], [1381,
460], [1471, 490], [1579, 526], [1699, 566], [1999, 666]]
[[139, 46], [151, 50], [331, 110], [619, 206], [661, 220], [811, 270], [829, 276], [1069, 356], [1231, 410], [1279, 426], [1291, 430], [1381, 460], [1471, 490], [1579, 526], [1699, 566], [1999, 666]]
prime_pisano_periods_ratio=[] N=2000 p=2 while p<N: pip=pisano(p) if p%5==2 or p%5==3: prime_pisano_periods_ratio.append([p,2*(p+1)/pip]) else: prime_pisano_periods_ratio.append([p,(p-1)/pip]) p=p.next_prime() show(list_plot(prime_pisano_periods_ratio)) print(prime_pisano_periods_ratio) 
        
[[2, 2], [3, 1], [5, 1/5], [7, 1], [11, 1], [13, 1], [17, 1], [19, 1],
[23, 1], [29, 2], [31, 1], [37, 1], [41, 1], [43, 1], [47, 3], [53, 1],
[59, 1], [61, 1], [67, 1], [71, 1], [73, 1], [79, 1], [83, 1], [89, 2],
[97, 1], [101, 2], [103, 1], [107, 3], [109, 1], [113, 3], [127, 1],
[131, 1], [137, 1], [139, 3], [149, 1], [151, 3], [157, 1], [163, 1],
[167, 1], [173, 1], [179, 1], [181, 2], [191, 1], [193, 1], [197, 1],
[199, 9], [211, 5], [223, 1], [227, 1], [229, 2], [233, 9], [239, 1],
[241, 1], [251, 1], [257, 1], [263, 3], [269, 1], [271, 1], [277, 1],
[281, 5], [283, 1], [293, 1], [307, 7], [311, 1], [313, 1], [317, 1],
[331, 3], [337, 1], [347, 3], [349, 2], [353, 3], [359, 1], [367, 1],
[373, 1], [379, 1], [383, 1], [389, 1], [397, 1], [401, 2], [409, 1],
[419, 1], [421, 5], [431, 1], [433, 1], [439, 1], [443, 1], [449, 1],
[457, 1], [461, 10], [463, 1], [467, 1], [479, 1], [487, 1], [491, 1],
[499, 1], [503, 1], [509, 2], [521, 20], [523, 1], [541, 6], [547, 1],
[557, 9], [563, 3], [569, 1], [571, 1], [577, 1], [587, 1], [593, 1],
[599, 1], [601, 1], [607, 1], [613, 1], [617, 1], [619, 3], [631, 1],
[641, 1], [643, 1], [647, 1], [653, 1], [659, 1], [661, 3], [673, 1],
[677, 3], [683, 1], [691, 5], [701, 1], [709, 6], [719, 1], [727, 1],
[733, 1], [739, 1], [743, 3], [751, 1], [757, 1], [761, 2], [769, 4],
[773, 1], [787, 1], [797, 7], [809, 4], [811, 3], [821, 1], [823, 1],
[827, 1], [829, 3], [839, 1], [853, 1], [857, 1], [859, 11], [863, 1],
[877, 1], [881, 5], [883, 1], [887, 1], [907, 1], [911, 13], [919, 9],
[929, 1], [937, 1], [941, 2], [947, 1], [953, 9], [967, 11], [971, 1],
[977, 3], [983, 1], [991, 5], [997, 1], [1009, 8], [1013, 1], [1019, 1],
[1021, 2], [1031, 5], [1033, 1], [1039, 1], [1049, 4], [1051, 1], [1061,
2], [1063, 1], [1069, 3], [1087, 17], [1091, 1], [1093, 1], [1097, 3],
[1103, 23], [1109, 2], [1117, 1], [1123, 1], [1129, 1], [1151, 5],
[1153, 1], [1163, 1], [1171, 1], [1181, 1], [1187, 1], [1193, 1], [1201,
1], [1213, 1], [1217, 3], [1223, 3], [1229, 2], [1231, 3], [1237, 1],
[1249, 2], [1259, 1], [1277, 3], [1279, 3], [1283, 1], [1289, 4], [1291,
3], [1297, 1], [1301, 1], [1303, 1], [1307, 3], [1319, 1], [1321, 1],
[1327, 1], [1361, 2], [1367, 1], [1373, 1], [1381, 3], [1399, 1], [1409,
2], [1423, 1], [1427, 17], [1429, 1], [1433, 1], [1439, 1], [1447, 1],
[1451, 1], [1453, 1], [1459, 1], [1471, 3], [1481, 1], [1483, 7], [1487,
1], [1489, 1], [1493, 1], [1499, 1], [1511, 5], [1523, 3], [1531, 1],
[1543, 1], [1549, 2], [1553, 3], [1559, 1], [1567, 1], [1571, 1], [1579,
3], [1583, 1], [1597, 47], [1601, 10], [1607, 1], [1609, 1], [1613, 1],
[1619, 1], [1621, 2], [1627, 1], [1637, 1], [1657, 1], [1663, 1], [1667,
1], [1669, 2], [1693, 1], [1697, 1], [1699, 3], [1709, 2], [1721, 4],
[1723, 1], [1733, 3], [1741, 2], [1747, 1], [1753, 1], [1759, 1], [1777,
1], [1783, 1], [1787, 1], [1789, 2], [1801, 1], [1811, 1], [1823, 3],
[1831, 1], [1847, 1], [1861, 2], [1867, 1], [1871, 5], [1873, 1], [1877,
3], [1879, 1], [1889, 1], [1901, 1], [1907, 1], [1913, 3], [1931, 1],
[1933, 1], [1949, 1], [1951, 5], [1973, 3], [1979, 1], [1987, 1], [1993,
1], [1997, 1], [1999, 3]]
[[2, 2], [3, 1], [5, 1/5], [7, 1], [11, 1], [13, 1], [17, 1], [19, 1], [23, 1], [29, 2], [31, 1], [37, 1], [41, 1], [43, 1], [47, 3], [53, 1], [59, 1], [61, 1], [67, 1], [71, 1], [73, 1], [79, 1], [83, 1], [89, 2], [97, 1], [101, 2], [103, 1], [107, 3], [109, 1], [113, 3], [127, 1], [131, 1], [137, 1], [139, 3], [149, 1], [151, 3], [157, 1], [163, 1], [167, 1], [173, 1], [179, 1], [181, 2], [191, 1], [193, 1], [197, 1], [199, 9], [211, 5], [223, 1], [227, 1], [229, 2], [233, 9], [239, 1], [241, 1], [251, 1], [257, 1], [263, 3], [269, 1], [271, 1], [277, 1], [281, 5], [283, 1], [293, 1], [307, 7], [311, 1], [313, 1], [317, 1], [331, 3], [337, 1], [347, 3], [349, 2], [353, 3], [359, 1], [367, 1], [373, 1], [379, 1], [383, 1], [389, 1], [397, 1], [401, 2], [409, 1], [419, 1], [421, 5], [431, 1], [433, 1], [439, 1], [443, 1], [449, 1], [457, 1], [461, 10], [463, 1], [467, 1], [479, 1], [487, 1], [491, 1], [499, 1], [503, 1], [509, 2], [521, 20], [523, 1], [541, 6], [547, 1], [557, 9], [563, 3], [569, 1], [571, 1], [577, 1], [587, 1], [593, 1], [599, 1], [601, 1], [607, 1], [613, 1], [617, 1], [619, 3], [631, 1], [641, 1], [643, 1], [647, 1], [653, 1], [659, 1], [661, 3], [673, 1], [677, 3], [683, 1], [691, 5], [701, 1], [709, 6], [719, 1], [727, 1], [733, 1], [739, 1], [743, 3], [751, 1], [757, 1], [761, 2], [769, 4], [773, 1], [787, 1], [797, 7], [809, 4], [811, 3], [821, 1], [823, 1], [827, 1], [829, 3], [839, 1], [853, 1], [857, 1], [859, 11], [863, 1], [877, 1], [881, 5], [883, 1], [887, 1], [907, 1], [911, 13], [919, 9], [929, 1], [937, 1], [941, 2], [947, 1], [953, 9], [967, 11], [971, 1], [977, 3], [983, 1], [991, 5], [997, 1], [1009, 8], [1013, 1], [1019, 1], [1021, 2], [1031, 5], [1033, 1], [1039, 1], [1049, 4], [1051, 1], [1061, 2], [1063, 1], [1069, 3], [1087, 17], [1091, 1], [1093, 1], [1097, 3], [1103, 23], [1109, 2], [1117, 1], [1123, 1], [1129, 1], [1151, 5], [1153, 1], [1163, 1], [1171, 1], [1181, 1], [1187, 1], [1193, 1], [1201, 1], [1213, 1], [1217, 3], [1223, 3], [1229, 2], [1231, 3], [1237, 1], [1249, 2], [1259, 1], [1277, 3], [1279, 3], [1283, 1], [1289, 4], [1291, 3], [1297, 1], [1301, 1], [1303, 1], [1307, 3], [1319, 1], [1321, 1], [1327, 1], [1361, 2], [1367, 1], [1373, 1], [1381, 3], [1399, 1], [1409, 2], [1423, 1], [1427, 17], [1429, 1], [1433, 1], [1439, 1], [1447, 1], [1451, 1], [1453, 1], [1459, 1], [1471, 3], [1481, 1], [1483, 7], [1487, 1], [1489, 1], [1493, 1], [1499, 1], [1511, 5], [1523, 3], [1531, 1], [1543, 1], [1549, 2], [1553, 3], [1559, 1], [1567, 1], [1571, 1], [1579, 3], [1583, 1], [1597, 47], [1601, 10], [1607, 1], [1609, 1], [1613, 1], [1619, 1], [1621, 2], [1627, 1], [1637, 1], [1657, 1], [1663, 1], [1667, 1], [1669, 2], [1693, 1], [1697, 1], [1699, 3], [1709, 2], [1721, 4], [1723, 1], [1733, 3], [1741, 2], [1747, 1], [1753, 1], [1759, 1], [1777, 1], [1783, 1], [1787, 1], [1789, 2], [1801, 1], [1811, 1], [1823, 3], [1831, 1], [1847, 1], [1861, 2], [1867, 1], [1871, 5], [1873, 1], [1877, 3], [1879, 1], [1889, 1], [1901, 1], [1907, 1], [1913, 3], [1931, 1], [1933, 1], [1949, 1], [1951, 5], [1973, 3], [1979, 1], [1987, 1], [1993, 1], [1997, 1], [1999, 3]]

When is 5 a square modulo p?
def is_5_square(p): for i in srange(p): if (i^2 %p)==5: return(i) return(False) 
       
for i in srange(100): if is_prime(i): print(i, is_5_square(i)) 
        
(2, False)
(3, False)
(5, False)
(7, False)
(11, 4)
(13, False)
(17, False)
(19, 9)
(23, False)
(29, 11)
(31, 6)
(37, False)
(41, 13)
(43, False)
(47, False)
(53, False)
(59, 8)
(61, 26)
(67, False)
(71, 17)
(73, False)
(79, 20)
(83, False)
(89, 19)
(97, False)
(2, False)
(3, False)
(5, False)
(7, False)
(11, 4)
(13, False)
(17, False)
(19, 9)
(23, False)
(29, 11)
(31, 6)
(37, False)
(41, 13)
(43, False)
(47, False)
(53, False)
(59, 8)
(61, 26)
(67, False)
(71, 17)
(73, False)
(79, 20)
(83, False)
(89, 19)
(97, False)
p=23 for i in srange(1,p): print(i,(i^(p-1))%p) 
        
(1, 1)
(2, 1)
(3, 1)
(4, 1)
(5, 1)
(6, 1)
(7, 1)
(8, 1)
(9, 1)
(10, 1)
(11, 1)
(12, 1)
(13, 1)
(14, 1)
(15, 1)
(16, 1)
(17, 1)
(18, 1)
(19, 1)
(20, 1)
(21, 1)
(22, 1)
(1, 1)
(2, 1)
(3, 1)
(4, 1)
(5, 1)
(6, 1)
(7, 1)
(8, 1)
(9, 1)
(10, 1)
(11, 1)
(12, 1)
(13, 1)
(14, 1)
(15, 1)
(16, 1)
(17, 1)
(18, 1)
(19, 1)
(20, 1)
(21, 1)
(22, 1)
x=7^99999999 len(x.digits()) 
        
84509804
84509804
log(99999999.)/log(2.) 
        
26.5754247446719
26.5754247446719
a=mod(7,15*10^19) 
       
a^99999999 
        
17707875437142857143
17707875437142857143