R10下的广义斐波那契序列

shshsh_0510

嗯，而且用不着穷举n维向量，只算一维的10个应该就行了

shshsh_0510

上边的讲法不太妥当，求分布还是要算一些，
如果算出n-step fibonacci 数，则可得到其乘1-9再mod 10的10个序列，我们只需根据mathe的方法算到一定长度
然后，就可以根据初始向量，求出n位分别的周期，再取公倍数

mathe

原帖由 mathe 于 2009-1-22 17:19 发表
重新安装了Pari/GP来计算因子分解
n=6时:
$x^6-x^5-x^4-x^3-x^2-x-1-=(x^3+x+1)(x^3+x^2+1)(mod 2)$
$x^6-x^5-x^4-x^3-x^2-x-1-=(x+2)(x+4)(x^4+3x^3+3x^2+2x+3)(mod 5)$

通过Pari/GP验证,关于模5，$x^4+3x^3+3x^2+2x+3$的最小周期为208.也就是验证了无心人n=6的最小周期为208*7=1456。
而对于特征函数为$H(x)/C(x)$,
模5情况分成三种情况
i)$H(x)=0(modC(x),5)$,关于模5的最小周期为1
ii)$H(x)=0(mod x^4+3x^3+3x^2+2x+3,5)$,但是不是i),关于模5的最小周期为4
iii)除去i)和ii)的情况，关于模5的最小周期为208
而模2的情况分成两种
i)$H(x)=0(mod C(x),2)$，关于模2的最小周期为1
ii)除了i)的情况，关于模2的最小周期为7
所以它们组合的情况对应的周期分别有1,4,7,28,208,1456
模5情况i)的计数只有1个，而再同时考虑到模2的情况，那么分子的6个系数每个都可以有加5的选项，总共$2^6=64$种
其中模2也为0的只有一个，也就是周期为1的一个，周期为7的63个；也就是9个不相交的周期为7的序列。
模5情况ii)包含i)有$5^2=25$个，扣除i)还有24个，同样再考虑模2的情况每个可以对应64个，这64个有且只有一个模2为0
所以周期为4总共24个，而周期为28总共24*63=1512个，也就是是有6个不相交的周期为4的序列，54个不相交的周期为28的序列。
模5情况iii)总共有$5^6-5^2=15600$个，同样考虑模2后每个可以对应64个，其中每64个只有一个模2为0
所以周期为208的总共有15600个，构成75个不相交的序列；而周期为208*7=1456的数有15600*63个，构成675个不相交的序列。

mathe

而对于一个具体的初始值，如果要计算对应的周期，可以根据我38#中的方法计算出H(x),然后计算(H(x),C(x)),然后就可以计算出这个数列的周期了。
不过这个方法还不能判断两个给定的不同初始值是否会出现在对方的序列中。
当然如果两个不同的初始值假设对应的H(x)分别为$H_1(x),H_2(x)$,如果它们同C(x)的最大公约数不同，必然不在一个序列中出现。
如果相同，那么比较麻烦，这个时候，它们会相互出现的充分必要条件是存在正整数k,使得
$C(x)|x^{kn}*H_1(x)-H_2(x)$
其中n为C(x)的次数。不过这个条件不知道有没有简单的判断方法

mathe

原帖由 medie2005 于 2009-1-23 09:38 发表
看样子无心人在死算.
要不无心人你算一下99阶的.
用mathe的方法,很好确定99阶的周期的.

呵呵，的确，好像因子分解很容易:
(10:17) gp > factormod(x^100-2*x^99+1,5)
%1 =
[Mod(1, 5)*x + Mod(4, 5) 1]

[Mod(1, 5)*x^5 + Mod(3, 5)*x^4 + Mod(4, 5)*x^3 + Mod(1, 5)*x^2 + Mod(1, 5)*x + M
od(1, 5) 1]

[Mod(1, 5)*x^7 + Mod(4, 5)*x^6 + Mod(2, 5)*x^5 + Mod(4, 5)*x^3 + Mod(3, 5)*x^2 +
Mod(4, 5) 1]

[Mod(1, 5)*x^10 + Mod(2, 5)*x^9 + Mod(2, 5)*x^8 + Mod(1, 5)*x^7 + Mod(3, 5)*x^6
+ Mod(4, 5)*x^5 + Mod(1, 5)*x^3 + Mod(2, 5)*x^2 + Mod(3, 5)*x + Mod(2, 5) 1]

[Mod(1, 5)*x^28 + Mod(2, 5)*x^26 + Mod(2, 5)*x^25 + Mod(4, 5)*x^23 + Mod(4, 5)*x
^22 + Mod(4, 5)*x^20 + Mod(2, 5)*x^18 + Mod(4, 5)*x^17 + Mod(4, 5)*x^16 + Mod(1,
5)*x^14 + Mod(1, 5)*x^13 + Mod(1, 5)*x^12 + Mod(1, 5)*x^10 + Mod(4, 5)*x^8 + Mo
d(3, 5)*x^7 + Mod(2, 5)*x^6 + Mod(1, 5)*x^5 + Mod(2, 5)*x^4 + Mod(4, 5)*x^3 + Mo
d(4, 5)*x^2 + Mod(3, 5)*x + Mod(2, 5) 1]

[Mod(1, 5)*x^49 + Mod(3, 5)*x^47 + Mod(3, 5)*x^46 + Mod(4, 5)*x^45 + Mod(3, 5)*x
^44 + Mod(1, 5)*x^43 + Mod(4, 5)*x^42 + Mod(2, 5)*x^41 + Mod(2, 5)*x^40 + Mod(1,
5)*x^39 + Mod(2, 5)*x^38 + Mod(3, 5)*x^37 + Mod(2, 5)*x^36 + Mod(3, 5)*x^35 + M
od(2, 5)*x^34 + Mod(4, 5)*x^33 + Mod(3, 5)*x^32 + Mod(1, 5)*x^31 + Mod(2, 5)*x^3
0 + Mod(3, 5)*x^28 + Mod(3, 5)*x^27 + Mod(4, 5)*x^26 + Mod(1, 5)*x^25 + Mod(3, 5
)*x^24 + Mod(1, 5)*x^23 + Mod(4, 5)*x^22 + Mod(2, 5)*x^21 + Mod(4, 5)*x^20 + Mod
(1, 5)*x^19 + Mod(3, 5)*x^18 + Mod(3, 5)*x^17 + Mod(4, 5)*x^16 + Mod(3, 5)*x^15
+ Mod(4, 5)*x^14 + Mod(2, 5)*x^13 + Mod(4, 5)*x^12 + Mod(4, 5)*x^11 + Mod(2, 5)*
x^10 + Mod(4, 5)*x^8 + Mod(2, 5)*x^7 + Mod(2, 5)*x^6 + Mod(3, 5)*x^5 + Mod(3, 5)
*x^3 + Mod(2, 5)*x^2 + Mod(3, 5)*x + Mod(4, 5) 1]

(10:17) gp > factormod(x^100-2*x^99+1,2)
%2 =
[Mod(1, 2)*x + Mod(1, 2) 4]

[Mod(1, 2)*x^4 + Mod(1, 2)*x^3 + Mod(1, 2)*x^2 + Mod(1, 2)*x + Mod(1, 2) 4]

[Mod(1, 2)*x^20 + Mod(1, 2)*x^15 + Mod(1, 2)*x^10 + Mod(1, 2)*x^5 + Mod(1, 2) 4]

无心人

你能得到具体每个序列的一个值么?
呵呵
算这个是为了学习 Haskell呢

无心人

n = 7的部分结果
[([0,0,0,0,0,0,0],1),([0,0,0,0,0,0,1],18744),([0,0,0,0,0,0,2],9372),([0,0,0,0,0,
0,3],18744),([0,0,0,0,0,0,4],9372),([0,0,0,0,0,0,5],8),([0,0,0,0,0,0,6],9372),([
0,0,0,0,0,0,7],18744),([0,0,0,0,0,0,8],9372),([0,0,0,0,0,0,9],18744),([0,0,0,0,0
,1,0],18744),([0,0,0,0,0,1,2],18744),([0,0,0,0,0,1,3],18744),([0,0,0,0,0,1,4],18
744),([0,0,0,0,0,1,5],18744),([0,0,0,0,0,1,6],18744)]

mathe

原帖由 无心人 于 2009-1-23 11:16 发表
你能得到具体每个序列的一个值么?
呵呵
算这个是为了学习 Haskell呢

可以对于给定的序列，快速计算出周期。而且如果模是素数，对于给定的两个不同的初始值，可以快速判断两个对应的序列是否只是循环移位了一下。但是对于模不是素数的时候，现在还不能确定是否有快速的判断方法。
不过说具体每个序列的一个值，也就是给出递推公式，然后编号，计算这个序列指定编号位置的值，这个也很容易，不需要逐项计算。假设周期为T,计算复杂度应该为log(T)就可以了

无心人

呵呵

那这个问题应该算差不多完成了

无心人

其实这类问题的结果可以作为加密解密的混淆步