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种情况的