fibonacci(10^14) % 1234567891011是多少?

只是呼吸

王守恩对数字有一种特殊的直觉，往往会在别人不注意的地方得到答案。

xbtianlang

nyy 发表于 2024-1-10 14:05
根据递推数列来求解问题。
f(n)表示斐波那契数列的第n项,

既然能翻倍，直接翻五倍，岂不更快。

1. def double(a, b, m):
   
2.     return (a * a + b * b) % m, b * (2 * a + b) % m
   
3. 
   
4. 
   
5. def fivefold(a, b, m):
   
6.     x = pow(a, 5, m) + 10 * pow(a, 3, m) * pow(b, 2, m) + 10 * pow(a, 2, m) * pow(b, 3, m)\
   
7.         + 10 * a * pow(b, 4, m) + 3 * pow(b, 5, m)
   
8.     y = 5 * pow(a, 4, m) * b + 10 * pow(a, 3, m) * pow(b, 2, m) + 20 * pow(a, 2, m) * pow(b, 3, m)\
   
9.         + 15 * a * pow(b, 4, m) + 5 * pow(b, 5, m)
   
10.     return x % m, y % m
    
11. 
    
12. 
    
13. if __name__ == '__main__':
    
14.     import datetime, time
    
15. 
    
16.     print(datetime.datetime.now().strftime('%F %T'))
    
17.     start = time.time()
    
18.     m = 1234567891011
    
19.     a, b = 0, 1
    
20.     for k in range(14):
    
21.         a, b = double(a, b, m)
    
22.         a, b = fivefold(a, b, m)
    
23.         print(a, b, f'(10^{k+1})')
    
24.     print(f'fibonacci(10^14) % 1234567891011 = {b}')
    
25.     print("用时 %.5f 秒" % (time.time() - start))
    

复制代码

2024-04-14 17:12:13
34 55 (10^1)
116612017118 495345832656 (10^2)
300447695764 723674336364 (10^3)
959708987980 1231249114683 (10^4)
76392597604 1214159484279 (10^5)
1159141250527 519842384901 (10^6)
562995635077 1128339761598 (10^7)
629994371161 229892300169 (10^8)
271915538539 567371328867 (10^9)
1040234075350 1019093565168 (10^10)
754543197094 1127292776442 (10^11)
204030176701 336630174993 (10^12)
478253823013 1178927050077 (10^13)
512884989226 921144120792 (10^14)
fibonacci(10^14) % 1234567891011 = 921144120792
用时 0.00000 秒

nyy

xbtianlang 发表于 2024-4-14 17:17
既然能翻倍，直接翻五倍，岂不更快。

2024-04-14 17:12:13

二进制，五进制，又能有多大的本质区别？

xbtianlang

nyy 发表于 2024-4-15 14:46
二进制，五进制，又能有多大的本质区别？

二进制、五进制、十进制本质上没区别，而且它们有一个共同点就是：
2=1^2+1
5=2^2+1
10=3^2+1
人们习惯于十进制，比如10^14等等。

xbtianlang

王守恩 发表于 2024-1-13 15:20
虚心请教。谢谢各位大侠！谢谢！
第1个问题。依据31楼的算式, 可以有算式(1),算式(2),算式(3),算式(4)四种 ...

第2题，设标准fibonacci数列为f(n),此题数列为F(n)，两数列做差分，可得F(n)=f(n)+2f(n-1)，问题解决。

1. if __name__ == '__main__':
   
2.     import datetime, time
   
3. 
   
4.     print(datetime.datetime.now().strftime('%F %T'))
   
5.     start = time.time()
   
6.     m = 1234567891011
   
7.     a, b, p = 0, 1, 14
   
8.     for k in range(p):
   
9.         a, b = double(a, b, m)
   
10.         a, b = fivefold(a, b, m)
    
11.         print(f'F(10^{k + 1}) % {m} = {(2*a+b)%m}')
    
12.     # print(f'fibonacci(10^{p}) % 1234567891011 = {b}')
    
13.     print("用时 %.5f 秒" % (time.time() - start))

复制代码

2024-04-17 15:15:26
F(10^1) % 1234567891011 = 123
F(10^2) % 1234567891011 = 728569866892
F(10^3) % 1234567891011 = 90001836881
F(10^4) % 1234567891011 = 681531308621
F(10^5) % 1234567891011 = 132376788476
F(10^6) % 1234567891011 = 368989103933
F(10^7) % 1234567891011 = 1019763140741
F(10^8) % 1234567891011 = 255313151480
F(10^9) % 1234567891011 = 1111202405945
F(10^10) % 1234567891011 = 630425933846
F(10^11) % 1234567891011 = 167243388608
F(10^12) % 1234567891011 = 744690528395
F(10^13) % 1234567891011 = 900866805092
F(10^14) % 1234567891011 = 712346208233
用时 0.00000 秒

王守恩

A001175,  主帖绕不过去的坑！ 晒一晒！A001175通项公式。可以更好吗？谢谢！

1. Table[a = {1, 1}; b = a; k = 0; While[k++; a[[2]] = Mod[Plus @@ a, n]; a = RotateLeft[a];  b != a]; k, {n, 2, 13000}]

复制代码

{3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30, 48, 40, 36, 80, 24, 76, 18, 56, 60, 40, 48, 88,
30, 120, 48, 32, 24, 112, 300, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120, 60, 30, 48, 96, 140, 120, 136, 36, 48, 240, 70, 24, 148, 228, 200, 18, 80, 168, 78, 120, 216,
120, 168, 48, 180, 264, 56, 60, 44, 120, 112, 48, 120, 96, 180, 48, 196, 336, 120, 300, 50, 72, 208, 84, 80, 108, 72, 72, 108, 60, 152, 48, 76, 72, 240, 42, 168,  ......