R10下的广义斐波那契序列

无心人

n = 2的 [0, 0] [0, 1]的60个数字的循环 [(0,[0,1]),(1,[1,1]),(2,[1,2]),(3,[2,3]),(4,[3,5]),(5,[5,8]),(6,[8,3]),(7,[3,1]) ,(8,[1,4]),(9,[4,5]),(10,[5,9]),(11,[9,4]),(12,[4,3]),(13,[3,7]),(14,[7,0]),(15, [0,7]),(16,[7,7]),(17,[7,4]),(18,[4,1]),(19,[1,5]),(20,[5,6]),(21,[6,1]),(22,[1, 7]),(23,[7,8]),(24,[8,5]),(25,[5,3]),(26,[3,8]),(27,[8,1]),(28,[1,9]),(29,[9,0]) ,(30,[0,9]),(31,[9,9]),(32,[9,8]),(33,[8,7]),(34,[7,5]),(35,[5,2]),(36,[2,7]),(3 7,[7,9]),(38,[9,6]),(39,[6,5]),(40,[5,1]),(41,[1,6]),(42,[6,7]),(43,[7,3]),(44,[ 3,0]),(45,[0,3]),(46,[3,3]),(47,[3,6]),(48,[6,9]),(49,[9,5]),(50,[5,4]),(51,[4,9 ]),(52,[9,3]),(53,[3,2]),(54,[2,5]),(55,[5,7]),(56,[7,2]),(57,[2,9]),(58,[9,1]), (59,[1,0])] [2,2]的20个数字的循环 [(0,[2,2]),(1,[2,4]),(2,[4,6]),(3,[6,0]),(4,[0,6]),(5,[6,6]),(6,[6,2]),(7,[2,8]) ,(8,[8,0]),(9,[0,8]),(10,[8,8]),(11,[8,6]),(12,[6,4]),(13,[4,0]),(14,[0,4]),(15, [4,4]),(16,[4,8]),(17,[8,2]),(18,[2,0]),(19,[0,2])] [0, 5]的3个 [0, 5], [5, 5], [5, 0] [1, 3]的12个 [1, 3], [3, 4], [4, 7], [7, 1], [1, 8], [8, 9], [9, 7], [7, 6], [6, 3], [3, 9], [9, 2], [2, 1] [2, 6]的4个 [2, 6], [6, 8], [8, 4], [4, 2] n = 2的齐了 正好100个

无心人

以后只罗列最小值及其循环个数 n = 3 [0, 0, 0] 1 [5, 5, 5] 1 [0, 0, 1] 124 [0, 0, 2] 31 [0, 0, 3] 124 [0, 0, 4] 31 [0, 0, 5] 4 [0, 0, 6] 31 [0, 0, 7] 124 [0, 0, 8] 31 [0, 0, 9] 124 [0, 1, 0] 62 [0, 1, 4] 62 [0, 1, 6] 62 [0, 3, 2] 62 [0, 5, 0] 2 [1, 1, 3] 31 [1, 1, 5] 31 [1, 1, 7] 31 [1, 3, 1] 31 共20个序列

无心人

使用了三个haskell函数 let ff l = iterate (\(i, l) -> (i + 1, (tail l) ++ [(sum l) \`mod\` 10]) (0, l) 计算指定起始序列的后续序列， 无限长度 let cc l = take 2 \$ filter (\(_, x) -> x == l) ff l 得到由起始序列生成的序列的周期， 第二个(i, l)的i就是 let check l n = sort \$ map (\(_, x) -> foldl (\a, b -> 10 * a + b) 0, x) \$ take n \$ ff l 得到起始序列l生成的序列的每项的转成10进制数字，按大小排列， 共n个， n由cc l得到，以便检查某个起始序列是否包含在已知循环

无心人

还可以让程序自己产生所有的不重合起始序列及其循环周期 但程序一行长度就可能太长了 在交互里有点不方便

shshsh_0510

这个总结貌似不错 http://mathmu.cn/doc/PolyFacZp.html

shshsh_0510

$ x^6-x^5-x^4-x^3-x^2-x-1 mod 5= (x^4+3*x^3+3*x^2+2*x+3)*(x+2)*(x+4) $

mathe

根据shshsh_0510上面的结论，而且如果$x^4+3x^3+3x^2+2x+3$在$F_5$中不可约，那么设这个方程在$F_{5^4}$中的解为$x_1,x_2,x_3,x_4$,在加上解$3,1$,我们有n=6时候的通项公式为 $a_1x_1^n+a_2x_2^n+a_3x_3^n+a_4x_4^n+a_5*3^n+a_6$ 其中$5^4-1=624$是$x_1,x_2,x_3,x_4$的周期，也就是n=6时，数列的周期必然是624的因子。

mathe

上面只考虑了模5的情况，还要考虑模2的情况，也就是对${x^7+1}/{x+1}$在$F_2$上进行因子分解。

shshsh_0510

呵呵，刚想问你怎么不管F2了？ 上面的分解是用maple，x^4+3x^3+3x^2+2x+3 应该是不可约的了。 对于x^n+x^n-1+...+1 的分解 在f2上 当n为素数幂-1时，可以分解为分园多项式，然后有个复杂的定理可以运用默比乌斯函数容易的对分园多项式进行分解。 但这个x^n-x^n-1-...-1，而且是F5上，而且是任意n，应该是没简单推导方法了。 现在好像还没有多项式算法吧。

shshsh_0510

Factor(x^7+1) mod 2=(x+1)*(x^3+x+1)*(x^3+x^2+1) 于是，方程在扩域 F(2^3)上完全分解，其根r的周期为7的约数，周期为lcd(624,7)=4368的约数