王守恩对数字有一种特殊的直觉，往往会在别人不注意的地方得到答案。
nyy 发表于 2024-1-10 14:05
根据递推数列来求解问题。
f(n)表示斐波那契数列的第n项,
既然能翻倍，直接翻五倍，岂不更快。
def double(a, b, m):
return (a * a + b * b) % m, b * (2 * a + b) % m
def fivefold(a, b, m):
x = pow(a, 5, m) + 10 * pow(a, 3, m) * pow(b, 2, m) + 10 * pow(a, 2, m) * pow(b, 3, m)\
+ 10 * a * pow(b, 4, m) + 3 * pow(b, 5, m)
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)\
+ 15 * a * pow(b, 4, m) + 5 * pow(b, 5, m)
return x % m, y % m
if __name__ == '__main__':
import datetime, time
print(datetime.datetime.now().strftime('%F %T'))
start = time.time()
m = 1234567891011
a, b = 0, 1
for k in range(14):
a, b = double(a, b, m)
a, b = fivefold(a, b, m)
print(a, b, f'(10^{k+1})')
print(f'fibonacci(10^14) % 1234567891011 = {b}')
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 秒
xbtianlang 发表于 2024-4-14 17:17
既然能翻倍，直接翻五倍，岂不更快。
2024-04-14 17:12:13
二进制，五进制，又能有多大的本质区别？
nyy 发表于 2024-4-15 14:46
二进制，五进制，又能有多大的本质区别？
二进制、五进制、十进制本质上没区别，而且它们有一个共同点就是：
2=1^2+1
5=2^2+1
10=3^2+1
人们习惯于十进制，比如10^14等等。
王守恩 发表于 2024-1-13 15:20
虚心请教。谢谢各位大侠！谢谢！
第1个问题。依据31楼的算式, 可以有算式(1),算式(2),算式(3),算式(4)四种 ...
第2题，设标准fibonacci数列为f(n),此题数列为F(n)，两数列做差分，可得F(n)=f(n)+2f(n-1)，问题解决。
if __name__ == '__main__':
import datetime, time
print(datetime.datetime.now().strftime('%F %T'))
start = time.time()
m = 1234567891011
a, b, p = 0, 1, 14
for k in range(p):
a, b = double(a, b, m)
a, b = fivefold(a, b, m)
print(f'F(10^{k + 1}) % {m} = {(2*a+b)%m}')
# print(f'fibonacci(10^{p}) % 1234567891011 = {b}')
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通项公式。可以更好吗？谢谢！
Table] = Mod; a = RotateLeft;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,......