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

nyy · 发表于 2024-1-10 14:05:14

本帖最后由 nyy 于 2024-1-10 14:29 编辑

nyy 发表于 2024-1-9 12:10
我来全面地阐述一下你的思想，完全按照你的思路来。

w^2-w-1=0

根据递推数列来求解问题。
f(n)表示斐波那契数列的第n项,

这个是下标翻倍所使用的递推公式
f(2n-1)=f(n-1)^2+f(n)^2
f(2n)=(2*f(n-1)+f(n))*f(n)

下标增加1所使用的递推公式太简单了
f(n+1)=f(n-1)+f(n)

参考资料
https://handwiki.org/wiki/Fibonacci%20number

下面来编程来解决这个问题：

Clear["Global`*"];(*Clear all variables*)
(*子函数,二次域w的模m的乘法.xx={x1,y1},表示x1+y1*w(w^2-w-1=0),yy同,m为整数*)
dmult[xx_,yy_,m_]:=Module[{x1,y1,x2,y2},{x1,y1}=xx;{x2,y2}=yy;Mod[{x1*x2+y1*y2,x2*y1+x1*y2+y1*y2},m]]
n=10^14;(*n次方幂*)
m=1234567891011;(*模*)
n2=IntegerDigits[n,2];(*n次方,写成二进制表的形式*)
output={{"下标k-1","下标k(控制变量)","fibonacci(k-1)(mod m)","fibonacci(k)(mod m)"}};(*输出结果,先添加第一行结果*)
kk=1;(*下标变量*)
result=base={0,1};(*初始赋值,这个表示0+1*w=w,w^2-w-1=0*)
output=Append[output,{kk-1,kk,result[[1]],result[[2]]}];(*添加中间结果*)
Do[result=dmult[result,result,m];(*平方一下,下标翻倍后的结果*)
kk=2*kk;(*下标翻倍*)
output=Append[output,{kk-1,kk,result[[1]],result[[2]]}];(*添加中间结果*)
If[n2[[k]]==1,(*如果是1,那么下标增加1*)
result=dmult[result,base,m];(*下标增加1后的结果*)
kk=kk+1;(*下标增加1*)
output=Append[output,{kk-1,kk,result[[1]],result[[2]]}];(*添加中间结果*)
]
,{k,2,Length[n2]}];(*k就是从2开始的,没错!*)
result (*w^n模m后的求解结果*)
Grid[output,Alignment->Right](*列表显示*)

复制代码

输出结果
\[\begin{array}{rrrr}
\text{"下标k-1"} & \text{"下标k(控制变量)"} & \text{"fibonacci(k-1)(mod m)"} & \text{"fibonacci(k)(mod m)"} \\
0 & 1 & 0 & 1 \\
1 & 2 & 1 & 1 \\
3 & 4 & 2 & 3 \\
4 & 5 & 3 & 5 \\
9 & 10 & 34 & 55 \\
10 & 11 & 55 & 89 \\
21 & 22 & 10946 & 17711 \\
43 & 44 & 433494437 & 701408733 \\
44 & 45 & 701408733 & 1134903170 \\
89 & 90 & 418399201576 & 551554240726 \\
179 & 180 & 35334909920 & 262763311695 \\
180 & 181 & 262763311695 & 298098221615 \\
361 & 362 & 715815121972 & 930032138944 \\
362 & 363 & 930032138944 & 411279369905 \\
725 & 726 & 1026988262627 & 828715802615 \\
726 & 727 & 828715802615 & 621136174231 \\
1453 & 1454 & 821860435034 & 417571290317 \\
1454 & 1455 & 417571290317 & 4863834340 \\
2909 & 2910 & 934557690341 & 557570412125 \\
5819 & 5820 & 640405874750 & 464477778489 \\
11639 & 11640 & 1013559227533 & 904296183042 \\
11640 & 11641 & 904296183042 & 683287519564 \\
23281 & 23282 & 591955495468 & 998223761158 \\
23282 & 23283 & 998223761158 & 355611365615 \\
46565 & 46566 & 81721725944 & 130805084138 \\
93131 & 93132 & 1152681928634 & 232625857545 \\
186263 & 186264 & 808353439816 & 899496241938 \\
372527 & 372528 & 943727228053 & 683419929087 \\
372528 & 372529 & 683419929087 & 392579266129 \\
745057 & 745058 & 611330023543 & 191599921612 \\
1490115 & 1490116 & 1213637629787 & 285547575834 \\
2980231 & 2980232 & 647529389044 & 637495749849 \\
5960463 & 5960464 & 1631614720 & 1196381075232 \\
11920927 & 11920928 & 253829897098 & 1011991423821 \\
23841855 & 23841856 & 740141742670 & 947158241988 \\
23841856 & 23841857 & 947158241988 & 452732093647 \\
47683713 & 47683714 & 301233544144 & 792749392219 \\
47683714 & 47683715 & 792749392219 & 1093982936363 \\
95367429 & 95367430 & 1203241060565 & 121233975080 \\
95367430 & 95367431 & 121233975080 & 89907144634 \\
190734861 & 190734862 & 563640401774 & 1179902729333 \\
190734862 & 190734863 & 1179902729333 & 508975240096 \\
381469725 & 381469726 & 838744405928 & 770821019051 \\
762939451 & 762939452 & 253313627033 & 954110205801 \\
762939452 & 762939453 & 954110205801 & 1207423832834 \\
1525878905 & 1525878906 & 686545378966 & 716243478166 \\
3051757811 & 3051757812 & 703886646500 & 380897852856 \\
6103515623 & 6103515624 & 1125087808291 & 983575078080 \\
6103515624 & 6103515625 & 983575078080 & 874094995360 \\
12207031249 & 12207031250 & 264311759608 & 734529240229 \\
24414062499 & 24414062500 & 717505801973 & 78537520554 \\
48828124999 & 48828125000 & 412428169831 & 24647128548 \\
97656249999 & 97656250000 & 1033896072196 & 776128952802 \\
195312499999 & 195312500000 & 421094787541 & 64290543849 \\
390624999999 & 390625000000 & 546459273466 & 937001535603 \\
781249999999 & 781250000000 & 591003879817 & 576397611993 \\
1562499999999 & 1562500000000 & 126500401000 & 1107739986885 \\
3124999999999 & 3125000000000 & 1159474177240 & 1015775014842 \\
6249999999999 & 6250000000000 & 253889169430 & 508737534690 \\
12499999999999 & 12500000000000 & 38578495201 & 127771626150 \\
24999999999999 & 25000000000000 & 853039993912 & 820562429274 \\
49999999999999 & 50000000000000 & 622584505348 & 201033954324 \\
99999999999999 & 100000000000000 & 512884989226 & 921144120792 \\
\end{array}\]

表中的f(n)都是模m后的结果

不习惯上面代码的人，可以用下面的代码，上面的代码，把下标翻倍与下标增1写成了一个函数，下面的函数分开写了。更清晰易懂！

Clear["Global`*"];(*Clear all variables*)
(*子函数,下标翻倍后的结果,xx表示{fibonacci(n-1),fibonacci(n)},m表示模,输出{fibonacci(2n-1),fibonacci(2n)}mod m*)
doublekk[xx_,m_]:=Module[{a,b},{a,b}=xx;Mod[{a^2+b^2,(2*a+b)*b},m]]
(*子函数,下标增加1后的结果,xx表示{fibonacci(n-1),fibonacci(n)},m表示模,输出xx表示{fibonacci(n),fibonacci(n+1)}mod m*)
addonekk[xx_,m_]:=Module[{a,b},{a,b}=xx;Mod[{b,a+b},m]]
n=10^14;(*n次方幂*)
m=1234567891011;(*模*)
n2=IntegerDigits[n,2];(*n次方,写成二进制表的形式*)
output={{1,2,3,4}};(*输出结果,先添加第一行结果*)
kk=1;(*下标变量*)
result=base={0,1};(*初始赋值,这个表示0+1*w=w,w^2-w-1=0*)
output=Append[output,{kk-1,kk,result[[1]],result[[2]]}];(*添加中间结果*)
Do[result=doublekk[result,m];(*平方一下,下标翻倍后的结果*)
kk=2*kk;(*下标翻倍*)
output=Append[output,{kk-1,kk,result[[1]],result[[2]]}];(*添加中间结果*)
If[n2[[k]]==1,(*如果是1,那么下标增加1*)
result=addonekk[result,m];(*下标增加1后的结果*)
kk=kk+1;(*下标增加1*)
output=Append[output,{kk-1,kk,result[[1]],result[[2]]}];(*添加中间结果*)
]
,{k,2,Length[n2]}];(*k就是从2开始的,没错!*)
Grid[output,Alignment->Right](*列表显示*)

复制代码

王守恩 · 发表于 2024-1-13 15:20:50

虚心请教。谢谢各位大侠！谢谢！
第1个问题。依据31楼的算式, 可以有算式(1),算式(2),算式(3),算式(4)四种变化, 答案都是921144120792。四种变化?还可以更多吗？谢谢各位大侠！谢谢！

算式(1): s=IntegerDigits[10^14-1,2];m={{0,1},{1,0}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{0,1},{1,1}}],1234567891011],{i,Length[s]}];m[[2,2]]
算式(2): s=IntegerDigits[10^14-1,2];m={{0,1},{1,0}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{1,1},{1,0}}],1234567891011],{i,Length[s]}];m[[1,1]]
算式(3): s=IntegerDigits[10^14-1,2];m={{1,0},{0,1}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{0,1},{1,1}}],1234567891011],{i,Length[s]}];m[[2,2]]
算式(4): s=IntegerDigits[10^14-1,2];m={{1,0},{0,1}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{1,1},{1,0}}],1234567891011],{i,Length[s]}];m[[1,1]]

复制代码

第2个问题。主帖是这样一道题目。递推数列: a(1)=a(2)=1, a(n)=a(n-1)+a(n-2), 求a(10^14)除以1234567891011的余数。答:余数=921144120792。
改动一下。递推数列: a(0)=2,a(1)=1, a(n)=a(n-1)+a(n-2), 求a(10^14)除以1234567891011的余数。可以有吗？谢谢各位大侠！谢谢！

王守恩 · 发表于 2024-1-14 12:28:03

虚心请教。谢谢各位大侠！谢谢！
第1个问题。依据31楼的算式, 可以有算式(1),算式(2),算式(3),......12种变化, 答案都是921144120792。12种变化? 还可以更多吗？谢谢各位大侠！谢谢！

算式(01): s=IntegerDigits[10^14-1,2];m={{0,1},{1,0}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{0,1},{1,1}}],1234567891011],{i,Length[s]}];m[[2,2]]
算式(02): s=IntegerDigits[10^14-1,2];m={{0,1},{1,0}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{1,1},{1,0}}],1234567891011],{i,Length[s]}];m[[1,1]]
算式(03): s=IntegerDigits[10^14-1,2];m={{1,0},{0,1}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{0,1},{1,1}}],1234567891011],{i,Length[s]}];m[[2,2]]
算式(04): s=IntegerDigits[10^14-1,2];m={{1,0},{0,1}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{1,1},{1,0}}],1234567891011],{i,Length[s]}];m[[1,1]]
算式(05): s=IntegerDigits[10^14-0,2];m={{0,1},{1,0}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{0,1},{1,1}}],1234567891011],{i,Length[s]}];m[[2,1]]
算式(06): s=IntegerDigits[10^14-0,2];m={{0,1},{1,0}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{1,1},{1,0}}],1234567891011],{i,Length[s]}];m[[2,1]]
算式(07): s=IntegerDigits[10^14-0,2];m={{1,0},{0,1}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{0,1},{1,1}}],1234567891011],{i,Length[s]}];m[[2,1]]
算式(08): s=IntegerDigits[10^14-0,2];m={{1,0},{0,1}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{1,1},{1,0}}],1234567891011],{i,Length[s]}];m[[2,1]]
算式(09): s=IntegerDigits[10^14+1,2];m={{0,1},{1,0}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{0,1},{1,1}}],1234567891011],{i,Length[s]}];m[[1,1]]
算式(10): s=IntegerDigits[10^14+1,2];m={{0,1},{1,0}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{1,1},{1,0}}],1234567891011],{i,Length[s]}];m[[2,2]]
算式(11): s=IntegerDigits[10^14+1,2];m={{1,0},{0,1}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{0,1},{1,1}}],1234567891011],{i,Length[s]}];m[[1,1]]
算式(12): s=IntegerDigits[10^14+1,2];m={{1,0},{0,1}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{1,1},{1,0}}],1234567891011],{i,Length[s]}];m[[2,2]]

复制代码

第2个问题。主帖是这样一道题目。递推数列: a(1)=a(2)=1, a(n)=a(n-1)+a(n-2), 求a(10^14)除以1234567891011的余数。答:余数=921144120792。
改动一下。递推数列: a(0)=2,a(1)=1, a(n)=a(n-1)+a(n-2), 求a(10^14)除以1234567891011的余数。可以有吗？谢谢各位大侠！谢谢！

王守恩 · 发表于 2024-1-14 15:57:37

晒一晒我的 "通项公式"。也就是说, 依据31楼的算式, 可以有无穷个算式, 答案都是921144120792。谢谢zgg___大侠！谢谢！谢谢各位大侠！谢谢！

重复主帖题目。递推数列: a(1)=a(2)=1, a(n)=a(n-1)+a(n-2), 求a(10^14)除以1234567891011的余数。答:余数=921144120792。

Table[s=IntegerDigits[809322544+900788112n,2];m={{0,1},{1,0}};Do[m=Mod[If[s[[i]]==0,m.m,m.m.{{0,1},{1,1}}],1234567891011],{i,Length[s]}];m[[2,1]],{n,0,9}]

复制代码

{921144120792, 921144120792, 921144120792, 921144120792, 921144120792, 921144120792, 921144120792, 921144120792, 921144120792, 921144120792}

在这里：a + bn = 809322544 + 900788112 n, n=0,1,2,3,4,.....。特别地, n= 111013 时, 809322544 + 900788112 n=10^14

谢谢各位大侠！这 a, b 还可以缩小吗？谢谢！

nyy · 发表于 2024-1-15 08:49:44

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

第2个问题。主帖是这样一道题目。递推数列: a(1)=a(2)=1, a(n)=a(n-1)+a(n-2), 求a(10^14)除以1234567891011的余数。答:余数=921144120792。
改动一下。递推数列: a(0)=2,a(1)=1, a(n)=a(n-1)+a(n-2), 求a(10^14)除以1234567891011的余数。可以有吗？谢谢各位大侠！谢谢！

这个问题的回答见

GP/PARI CALCULATOR Version 2.15.4 (released)
amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version
compiled: Jun 28 2023, gcc version 10-posix 20210110 (GCC)
threading engine: single
(readline v8.0 enabled, extended help enabled)
Copyright (C) 2000-2022 The PARI Group
PARI/GP is free software, covered by the GNU General Public License, and comes
WITHOUT ANY WARRANTY WHATSOEVER.
Type ? for help, \q to quit.
Type ?18 for how to get moral (and possibly technical) support.
parisizemax = 400000000, primelimit = 500000
(08:41) gp > n=10^14;
(08:41) gp > m=1234567891011;
(08:41) gp > mat=[1,1;1,0]
%3 =
[1 1]
[1 0]
(08:41) gp > aa=(Mod(mat,m)^(n-1))*[1;2]
%4 =
[Mod(712346208233, 1234567891011)]
[ Mod(94835361347, 1234567891011)]
(08:41) gp > bb=aa[1,1]
%5 = Mod(712346208233, 1234567891011)

复制代码

从上面的计算结果可以知道答案是712346208233

王守恩 · 发表于 2024-1-15 09:07:29

第1题(基本解决), 我们有12个算式(我对这些按钮不熟)的变化,我就想找出某种规律来，解决第2题(或者更多的题)。

nyy · 发表于 2024-1-15 11:47:51

王守恩发表于 2024-1-15 09:07
第1题(基本解决), 我们有12个算式(我对这些按钮不熟)的变化,我就想找出某种规律来，解决第2题(或者更多的题 ...

你的第二题，我来给你答案
首先是求系数

Clear["Global`*"];(*Clear all variables*)
f[n_]:=c1*((1+Sqrt[5])/2)^n+c2*((1-Sqrt[5])/2)^n
ans=Solve[{f[0]==2,f[1]==1},{c1,c2}]//Simplify

复制代码

求得系数
\[\{\{\text{c1}\to 1,\text{c2}\to 1\}\}\]
因此通项系数表达式为：
\[\left(\frac{1}{2} \left(1+\sqrt{5}\right)\right)^n+\left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^n\]

GP/PARI CALCULATOR Version 2.15.4 (released)
amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version
compiled: Jun 28 2023, gcc version 10-posix 20210110 (GCC)
threading engine: single
(readline v8.0 enabled, extended help enabled)
Copyright (C) 2000-2022 The PARI Group
PARI/GP is free software, covered by the GNU General Public License, and comes
WITHOUT ANY WARRANTY WHATSOEVER.
Type ? for help, \q to quit.
Type ?18 for how to get moral (and possibly technical) support.
parisizemax = 400000000, primelimit = 500000
(11:42) gp > n=10^14;
(11:42) gp > m=1234567891011;
(11:42) gp > aa=Mod(Mod((1+x)/2,m),x^2-5)^n
%3 = Mod(Mod(460572060396, 1234567891011)*x + Mod(973457049622, 1234567891011), x^2 - 5)
(11:42) gp > bb=Mod(Mod((1-x)/2,m),x^2-5)^n
%4 = Mod(Mod(773995830615, 1234567891011)*x + Mod(973457049622, 1234567891011), x^2 - 5)
(11:42) gp > cc=aa+bb
%5 = Mod(Mod(712346208233, 1234567891011), x^2 - 5)
(11:42) gp > dd=lift(lift(cc))
%6 = 712346208233

复制代码

王守恩 · 发表于 2024-1-15 18:15:45

第1道题。递推数列: a(1)=a(2)=1, a(n)=a(n-1)+a(n-2), 求a(10^14)除以1234567891011的余数。答:余数=921144120792。

Mod[Fibonacci[809322544], 1234567891011]

复制代码

第2道题。递推数列: a(0)=2,a(1)=1, a(n)=a(n-1)+a(n-2), 求a(10^14)除以1234567891011的余数。答:余数=712346208233。

Mod[LucasL[809322544], 1234567891011]

复制代码

基本思路(9#10#)。我们不能改变1234567891011,但我们可以改变10^14。
1234567891011=3*7*13*67*107*630803
LCM[8,16,28,136,72,1261608]=900788112
其中: 3对应8,7对应16,13对应28,67对应136,107对应72,630803对应1261608。
每道题可以有无穷个解。809322544=809322544+900788112n, n=0,1,2,3,4,.....。
特别地, n=111013 时, 809322544+900788112n=10^14。
这809322544,900788112已经是最小的了你还怀疑吗？！谢谢各位大侠！谢谢！
留个遗憾: 看63#12个算式(我对这些按钮不熟), 我就想找出某种类似31#规律来, 解决更多的题。
谢谢zgg___大侠！谢谢 wayne！谢谢mathe！

王守恩 · 发表于 2024-1-15 20:23:04

谢谢47楼！9楼：http://oeis.org/A001175 Let the prime factorization of n be p1^e1...pk^ek. Then a(n) = lcm(a(p1^e1), ..., a(pk^ek))

n=2; Table[p= i; a=Join[Table[-1, {n - 1}], {n}]; a=Mod[a, p]; a0=a; k=0; While[k++; s=Mod[Plus@@a, p]; a=RotateLeft[a]; a[[n]]=s; a !=a0];k,{i,630803,630803}]

复制代码

{1261608}

王守恩 · 发表于 2024-1-16 08:02:28

谢谢47楼！瞄一眼通项公式(47楼论文的通项公式)就出来了(不同69#)。谢谢 nyy! 谢谢 northwolves！

n=2;Table[p=i;a=Join[Table[-1,{n-1}],{n}];a=Mod[a,p];b=a;k=0;While[k++;a[[n]]=Mod[Plus@@a,p];a=RotateLeft[a];b !=a];k,{i,630803,630803}]

复制代码

我赖在这里不走！就是这里有众多大侠(当然包括你)！谢谢zgg___大侠！谢谢 wayne！谢谢mathe！

账号		自动登录	找回密码
密码			欢迎注册

[求助] fibonacci(10^14) % 1234567891011是多少?

点评

点评

点评

点评

点评

点评

点评

点评