R10下的广义斐波那契序列

mathe

n=8,模5不可约，模2为$(x^2+x+1)(x^6+x^3+1)$ n=9,模5不可约,模2为$(x+1)(x^4+x^3+x^2+x+1)^2$ n=10,模2不可约，模5为$(x+2)(x^2+4x+2)(x^3+4x^2+4x+2)(x^4+4x^3+x^2+2x+3)$

mathe

所以n=6是，模5的周期为$5^4-1=624$,模2的周期为$2(2^3-1)=14$,所以整个周期必然是LCM(624,14)=4368的因子

mathe

原帖由 mathe 于 2009-1-22 17:21 发表 n=5 $x^5-x^4-x^3-x^2-x-1-=x^5-x^4-x^3-x^2-x-1(mod 5)$ $x^5-x^4-x^3-x^2-x-1-=(x+1)(x^2+x+1)^2(mod 2)$

而对于n=5,周期必然是$"LCM"(5^5-1,2*(2^2-1))=9372$的因子。

mathe

原帖由 mathe 于 2009-1-22 17:22 发表 n=4,2不可约 n=3模5不可约，模2为$(x+1)^3$

n=4,周期为$"LCM"(5^4-1,2^4-1)=9360$的因子 n=2,周期为$"LCM"(5^2-1,2^2-1)=24$的因子 n=3,周期为$"LCM"(5^3-1,2)=124$的因子

mathe

原帖由 mathe 于 2009-1-22 17:24 发表 n=7,模2为$(x+1)^7$,模5为$(x^2+3x+4)(x^5+x^4+2x^3+4x^2+4x+1)$

n=7是周期为$"LCM"(5^2-1,5^5-1,2)=18744$的因子

mathe

原帖由 mathe 于 2009-1-22 17:30 发表 n=8,模5不可约，模2为$(x^2+x+1)(x^6+x^3+1)$ n=9,模5不可约,模2为$(x+1)(x^4+x^3+x^2+x+1)^2$ n=10,模2不可约，模5为$(x+2)(x^2+4x+2)(x^3+4x^2+4x+2)(x^4+4x^3+x^2+2x+3)$

n=8,周期为$"LCM"(5^8-1,2^2-1,2^6-1)=8203104$的因子 n=9,周期为$"LCM"(5^9-1,2,2(2^4-1))=29296860$的因子 n=10,周期为$"LCM"(5,5^2-1,5^3-1,5^4-1,2^10-1)=1063920$的因子

mathe

原帖由 mathe 于 2009-1-22 17:40 发表 n=4,周期为$"LCM"(5^4-1,2^4-1)=9360$的因子 n=2,周期为$"LCM"(5^2-1,2^2-1)=24$的因子 n=3,周期为$"LCM"(5^3-1,2)=124$的因子

n=2弄错了，$(x^2-x-1)-=(x+2)^2(mod 5)$,所以周期为$"LCM"(2^2-1,5*4)=60$的因子

mathe

现在还有另外一个问题，就是不同周期的序列的数目分别是多少个。 对于递推序列 $a_{n+k}=c_1a_{n+k-1}+c_2a_{n+k-2}+...+c_ka_n(mod p)$,p为素数 我们记形式计数 $F(x)=sum_{n=0}^{infty}a_nx^n$ 那么可以得到 $F(x)=sum_{n=0}^{k-1}a_nx^n+c_1x(F(x)-u_1(x))+c_2x^2(F(x)-u_2(x))+...+c_kx^k(F(x)-u_k(x))$ 可以得到$F(x)=\frac{H(x)}{1-c_1x-c_2x^2-...-c_kx^k}=\frac{H(x)}{C(x)}$,其中H(x)的次数小于k,而且H(x)和初始值的选择一一对应。($p^k$种不同的选择) 同样，如果假设a(n)的周期为M,那么我们有 $F(x)=(a_0+a_1x+...+a_{M-1}x^{M-1})(1+x^M+x^{2M}+...)={G(x)}/{1-x^M}$ 由此我们可以得到 ${G(x)}/{1-x^M}={H(x)}/{C(x)}$ 由此可见，如果C(x)的次数为n,那么当$(H(x),C(x))=1$的时候，$M=n$,但是如果$(H(x),C(x))!=1$的时候,M可以取更小的值，也就是 ${C(x)}/{(C(x),H(x))}$的次数（必然为n的因子）。

mathe

原帖由 mathe 于 2009-1-22 17:54 发表 n=2弄错了，$(x^2-x-1)-=(x+2)^2(mod 5)$,所以周期为$"LCM"(2^2-1,5*4)=60$的因子

再以n=2为例子，$C(x)=1-x-x^2-=-(x+3)^2(mod 5)$而模2不可约 所以当H(x)是x+3的倍数的时候，可以有 i)H(x)=0,这个时候周期为1，推广的模10情况可以H(x)=0和H(x)=5x,H(x)=5,H(x)=5+5x,前面一种周期为1，后面3种周期为$2^2-1=3$. ii)H(x)=k(x+3),k=1,2,3,4,共4种情况，而扩展到$R_10$，k的选择可以多一倍，x+3可以分别为x+8，所以共16个不同的情况。 其中在$H(x)-=0(mod 2)$时周期为4，k为奇数的时候周期为$"LCM"(2^2-1,4)=12$，容易看出两种情况个一个正好构成16个情况。 而当H(x)不是x+3的倍数，余下的应该还有100-16-4=80种情况 同样我们需要考虑是否有$H(x)-=0(mod 2)$,如果模2为0，那么周期为5*4=20;不然周期为60;这个也是两者各一个。

无心人

我已经求出来n = 4的数据 n = 5的接近完成 但一整天不能抢到电脑 所以无法发过来 写了一个很复杂的Haskell函数 已经不用任何手工干预 能分析出指定n的各序列的起始数字和长度 但电脑被霸占来玩游戏 只能在一个老旧的笔记本上运行 在n = 5时卡在最后几项慢的很 就放弃了 n = 4是12种情况的