R10下的广义斐波那契序列

无心人

下面是代码 let ff l = iterate (\(i, l) -> (i + 1, (tail l) ++ [(sum l) \`mod\` 10])) (0, l) let cc l = fst . last \$ take 2 \$ filter (\(_, x) -> x == l) \$ ff l let check l = sort \$ map (\(_, x) -> foldl (\a b -> 10 * a + b) 0 x) \$ take (cc l) \$ ff l let inv [] = []; inv (x:xs) = inv xs ++ [x] let sp ns n = map snd \$ inv \$ tail \$ take (n+1) \$ iterate (\(x, y) -> (div x 10, mod x 10)) (ns, 0) let fr10 n = iterate (\(_, _, ex) -> if (ex == []) then ([], 0, []) else (sp (head ex) n, cc \$ sp (head ex) n, ex \\ (check \$ sp (head ex) n))) (take n \$ repeat 0, 1, [1..10^n-1])

无心人

n = 4 [([0,0,0,0],1),([0,0,0,1],1560),([0,0,0,2],312),([0,0,0,5],5),([0,0,1,0],1560),( [0,0,1,2],1560),([0,0,1,5],1560),([0,0,2,0],312),([0,0,5,0],5),([0,1,1,1],1560), ([0,1,1,3],1560),([0,5,5,5],5)]

无心人

使用take 12 \$ map (\(a, b, _) -> (a, b)) $ fr10 4 分析n = 4的情况 因为不知道如何用takeWhile所以要手工选择情况数 必须预先估计最大可能情况数

无心人

n = 5的结果 [([0,0,0,0,0],1),([0,0,0,0,1],4686),([0,0,0,0,2],781),([0,0,0,0,3],4686),([0,0,0 ,0,4],781),([0,0,0,0,5],6),([0,0,0,0,6],781),([0,0,0,0,7],4686),([0,0,0,0,8],781 ),([0,0,0,0,9],4686),([0,0,0,1,0],4686),([0,0,0,1,2],4686),([0,0,0,1,6],4686),([ 0,0,0,1,8],4686),([0,0,0,5,0],6),([0,0,1,0,0],2343),([0,0,1,0,4],2343),([0,0,1,1 ,1],4686),([0,0,1,1,3],4686),([0,0,1,1,7],4686),([0,0,1,1,9],4686),([0,0,1,2,0], 2343),([0,0,1,2,2],2343),([0,0,5,0,0],3),([0,0,5,5,5],6),([0,1,0,1,1],4686),([0, 1,0,1,3],4686),([0,1,0,1,9],4686),([0,1,0,3,7],4686),([0,1,1,0,1],2343),([0,1,1, 0,3],2343),([0,1,1,0,7],2343),([0,1,1,2,3],2343),([0,5,0,5,5],6),([0,5,5,0,5],3) ,([1,1,1,1,1],781),([1,1,1,3,1],781),([1,1,1,3,3],781),([1,1,3,3,1],781),([5,5,5,5,5],1)]

shshsh_0510

今天看了一下原题，似乎没必要这么整呀. 考虑前4个a1,a2,a3,a4 第5个a1+a2+a3+a4 .... 只考虑第1个的周期 她在各数中出现的次数为 1，0，0，0，1，1，2，4，8，15 是4-step fabonacci 吧 于是可算单个的位的周期，然后再将4个取最小公倍就是4个的周期了

无心人

n = 6的输出可能要违背mathe的结论了 只有短周期的序列， 最大周期是1456

无心人

n = 6部分结果 [([0,0,0,0,0,0],1),([0,0,0,0,0,1],1456),([0,0,0,0,0,2],208),([0,0,0,0,0,3],1456) ,([0,0,0,0,0,4],208),([0,0,0,0,0,5],7),([0,0,0,0,0,6],208),([0,0,0,0,0,7],1456), ([0,0,0,0,0,8],208),([0,0,0,0,0,9],1456),([0,0,0,0,1,0],1456),([0,0,0,0,1,2],145 6),([0,0,0,0,1,3],1456),([0,0,0,0,1,4],1456),([0,0,0,0,1,5],1456),([0,0,0,0,1,6] ,1456),([0,0,0,0,1,7],1456),([0,0,0,0,1,8],1456),([0,0,0,0,2,0],208),([0,0,0,0,2 ,1],1456),([0,0,0,0,2,4],208),([0,0,0,0,2,5],1456),([0,0,0,0,2,6],208),([0,0,0,0 ,2,9],1456),([0,0,0,0,3,0],1456),([0,0,0,0,3,1],1456),([0,0,0,0,3,2],1456),([0,0 ,0,0,3,4],1456),([0,0,0,0,3,5],1456),([0,0,0,0,3,6],1456),([0,0,0,0,3,8],1456),( [0,0,0,0,3,9],1456),([0,0,0,0,4,0],208),([0,0,0,0,4,2],208),([0,0,0,0,4,3],1456) ,([0,0,0,0,4,5],1456),([0,0,0,0,4,7],1456),([0,0,0,0,4,8],208),([0,0,0,0,5,0],7) ,([0,0,0,0,6,0],208),([0,0,0,0,6,2],208),([0,0,0,0,6,8],208),([0,0,0,0,7,0],1456 ),([0,0,0,0,7,4],1456),([0,0,0,0,7,6],1456),([0,0,0,0,8,0],208),([0,0,0,0,8,4],2 08),([0,0,0,0,8,6],208),([0,0,0,0,9,0],1456),([0,0,0,0,9,2],1456),([0,0,0,0,9,8] ,1456),([0,0,0,1,0,0],1456),([0,0,0,1,0,2],1456),([0,0,0,1,0,3],1456),([0,0,0,1, 0,4],1456),([0,0,0,1,0,5],1456),([0,0,0,1,0,6],1456),([0,0,0,1,0,7],1456),([0,0, 0,1,0,8],1456),([0,0,0,1,1,0],1456),([0,0,0,1,1,1],1456),([0,0,0,1,1,3],1456),([ 0,0,0,1,1,4],1456),([0,0,0,1,1,5],1456),([0,0,0,1,1,6],1456),([0,0,0,1,1,7],1456 ),([0,0,0,1,1,9],1456),([0,0,0,1,2,0],1456),([0,0,0,1,2,1],1456),([0,0,0,1,2,2], 1456),([0,0,0,1,2,4],1456),([0,0,0,1,2,5],1456),([0,0,0,1,2,6],1456),([0,0,0,1,2 ,8],1456),([0,0,0,1,2,9],1456),([0,0,0,1,3,0],1456),([0,0,0,1,3,1],1456),([0,0,0 ,1,3,2],1456),([0,0,0,1,3,3],1456),([0,0,0,1,3,5],1456),([0,0,0,1,3,7],1456),([0 ,0,0,1,3,8],1456),([0,0,0,1,3,9],1456),([0,0,0,1,4,0],1456),([0,0,0,1,4,2],1456) ,([0,0,0,1,4,4],1456),([0,0,0,1,4,7],1456),([0,0,0,1,4,8],1456),([0,0,0,1,4,9],1 456),([0,0,0,1,5,0],1456),([0,0,0,1,5,1],1456),([0,0,0,1,5,2],1456),([0,0,0,1,5, 5],1456),([0,0,0,1,5,7],1456),([0,0,0,1,5,9],1456),([0,0,0,1,6,0],1456),([0,0,0, 1,6,1],1456),([0,0,0,1,6,4],1456),([0,0,0,1,6,5],1456),([0,0,0,1,6,6],1456),([0, 0,0,1,6,8],1456),([0,0,0,1,6,9],1456),([0,0,0,1,7,0],1456),([0,0,0,1,7,1],1456), ([0,0,0,1,7,3],1456),([0,0,0,1,7,4],1456),([0,0,0,1,7,5],1456),([0,0,0,1,7,6],14 56),([0,0,0,1,7,9],1456),([0,0,0,1,8,0],1456),([0,0,0,1,8,2],1456),([0,0,0,1,8,4 ],1456),([0,0,0,1,8,5],1456),([0,0,0,1,8,6],1456),([0,0,0,1,8,7],1456),([0,0,0,1 ,9,2],1456),([0,0,0,1,9,3],1456),([0,0,0,1,9,4],1456),([0,0,0,1,9,5],1456),([0,0 ,0,1,9,7],1456),([0,0,0,1,9,9],1456),([0,0,0,2,0,0],208),([0,0,0,2,0,4],208),([0 ,0,0,2,0,5],1456),([0,0,0,2,0,6],208),([0,0,0,2,0,9],1456),([0,0,0,2,1,4],1456), ([0,0,0,2,1,9],1456),([0,0,0,2,2,0],208),([0,0,0,2,2,2],208),([0,0,0,2,2,3],1456 ),([0,0,0,2,2,5],1456),([0,0,0,2,2,7],1456),([0,0,0,2,2,8],208),([0,0,0,2,3,3],1 456),([0,0,0,2,3,4],1456),([0,0,0,2,3,8],1456),([0,0,0,2,3,9],1456),([0,0,0,2,4, 0],208),([0,0,0,2,4,2],208),([0,0,0,2,4,3],1456),([0,0,0,2,4,5],1456),([0,0,0,2, 4,8],208),([0,0,0,2,5,0],1456),([0,0,0,2,5,4],1456),([0,0,0,2,6,0],208),([0,0,0, 2,6,4],208),([0,0,0,2,7,0],1456),([0,0,0,2,7,2],1456),([0,0,0,2,7,8],1456),([0,0 ,0,2,8,4],208),([0,0,0,2,8,8],208),([0,0,0,2,9,0],1456),([0,0,0,2,9,8],1456),([0 ,0,0,3,0,0],1456),([0,0,0,3,0,1],1456),([0,0,0,3,0,2],1456),([0,0,0,3,0,4],1456) ,([0,0,0,3,0,6],1456),([0,0,0,3,0,8],1456),([0,0,0,3,0,9],1456),([0,0,0,3,1,0],1 456),([0,0,0,3,1,1],1456),([0,0,0,3,1,2],1456),([0,0,0,3,1,5],1456),([0,0,0,3,1, 7],1456),([0,0,0,3,1,9],1456),([0,0,0,3,2,6],1456),([0,0,0,3,3,2],1456),([0,0,0, 3,3,3],1456),([0,0,0,3,3,7],1456),([0,0,0,3,3,8],1456),([0,0,0,3,3,9],1456),([0, 0,0,3,4,0],1456),([0,0,0,3,4,1],1456),([0,0,0,3,4,2],1456),([0,0,0,3,4,5],1456), ([0,0,0,3,4,6],1456),([0,0,0,3,4,8],1456),([0,0,0,3,5,1],1456),([0,0,0,3,5,3],14 56),([0,0,0,3,5,4],1456),([0,0,0,3,5,5],1456),([0,0,0,3,5,6],1456),([0,0,0,3,5,7 ],1456),([0,0,0,3,5,9],1456),([0,0,0,3,6,0],1456),([0,0,0,3,6,2],1456),([0,0,0,3 ,6,4],1456),([0,0,0,3,6,5],1456),([0,0,0,3,6,6],1456),([0,0,0,3,6,7],1456),([0,0 ,0,3,7,1],1456),([0,0,0,3,8,2],1456),([0,0,0,3,8,3],1456),([0,0,0,3,8,4],1456),( [0,0,0,3,8,7],1456),([0,0,0,3,8,8],1456),([0,0,0,3,9,0],1456),([0,0,0,3,9,1],145 6),([0,0,0,3,9,3],1456),([0,0,0,3,9,5],1456),([0,0,0,3,9,6],1456),([0,0,0,3,9,7] ,1456),([0,0,0,4,0,0],208),([0,0,0,4,0,3],1456),([0,0,0,4,0,8],208),([0,0,0,4,2, 3],1456),([0,0,0,4,2,8],208),([0,0,0,4,3,0],1456),([0,0,0,4,3,1],1456),([0,0,0,4 ,3,5],1456),([0,0,0,4,3,6],1456),([0,0,0,4,4,0],208),([0,0,0,4,4,1],1456),([0,0, 0,4,4,4],208),([0,0,0,4,4,6],208),([0,0,0,4,4,9],1456),([0,0,0,4,5,8],1456),([0, 0,0,4,6,6],208),([0,0,0,4,6,8],208),([0,0,0,4,7,8],1456),([0,0,0,4,8,0],208),([0 ,0,0,4,8,6],208),([0,0,0,4,9,4],1456),([0,0,0,4,9,6],1456),([0,0,0,5,0,0],7),([0 ,0,0,5,5,5],7),([0,0,0,6,0,2],208),([0,0,0,6,0,8],208),([0,0,0,6,2,0],208),([0,0 ,0,6,2,4],208),([0,0,0,6,6,4],208),([0,0,0,6,6,6],208),([0,0,0,6,8,0],208),([0,0 ,0,6,8,2],208),([0,0,0,7,0,4],1456),([0,0,0,7,1,9],1456),([0,0,0,7,2,0],1456),([ 0,0,0,7,2,2],1456),([0,0,0,7,2,8],1456),([0,0,0,7,3,3],1456),([0,0,0,7,4,0],1456 ),([0,0,0,7,4,8],1456),([0,0,0,7,5,9],1456),([0,0,0,7,6,4],1456),([0,0,0,7,7,3], 1456),([0,0,0,7,7,5],1456),([0,0,0,7,7,7],1456),([0,0,0,7,8,8],1456),([0,0,0,7,9 ,3],1456),([0,0,0,7,9,5],1456),([0,0,0,8,0,6],208),([0,0,0,8,4,6],208),([0,0,0,8 ,6,0],208),([0,0,0,8,6,2],208),([0,0,0,8,8,2],208),([0,0,0,8,8,8],208),([0,0,0,9 ,0,8],1456),([0,0,0,9,2,8],1456),([0,0,0,9,3,1],1456),([0,0,0,9,3,5],1456),([0,0 ,0,9,4,4],1456),([0,0,0,9,4,6],1456),([0,0,0,9,5,3],1456),([0,0,0,9,7,3],1456),( [0,0,0,9,8,0],1456),([0,0,0,9,8,6],1456),([0,0,0,9,9,1],1456),([0,0,0,9,9,9],145 6),([0,0,1,0,0,3],1456),([0,0,1,0,1,1],1456),([0,0,1,0,1,3],1456),([0,0,1,0,1,4] ,1456),([0,0,1,0,1,5],1456),([0,0,1,0,1,6],1456),([0,0,1,0,1,7],1456),([0,0,1,0, 1,9],1456),([0,0,1,0,2,0],1456),([0,0,1,0,3,0],1456),([0,0,1,0,3,1],1456),([0,0, 1,0,3,3],1456),([0,0,1,0,3,5],1456),([0,0,1,0,3,7],1456),([0,0,1,0,3,9],1456),([ 0,0,1,0,4,4],1456),([0,0,1,0,5,1],1456),([0,0,1,0,5,3],1456),([0,0,1,0,5,5],1456 ),([0,0,1,0,5,8],1456),([0,0,1,0,5,9],1456),([0,0,1,0,6,1],1456),*** Exception:

无心人

Prelude List> let fr10 n = iterate (\(_, _, ex) -> let ls = sp (head ex) n in if (ex == []) then ([], 0, []) else (ls, cc ls, ex \\ check ls)) (replicate n 0, 1 , [1..10^n-1]) 修改了下最后的函数， 稍微精简了点

mathe

原帖由 无心人 于 2009-1-23 08:45 发表 n = 6的输出可能要违背mathe的结论了 只有短周期的序列， 最大周期是1456

这个不算违反。我计算的之际一个周期的倍数。而这个数值只有那些分解出来的多项式是本原多项式的时候才能够达到。 而只要实际的周期都是它的因子，就没有错。 而要计算准确的周期，那么多于每个多项式，我们需要计算最小的n使得$f(x)|1-x^n (mod p)$.而给定了上面一个周期的倍数的最大的好处是我们知道n必然是这个周期的因子，可以降低计算复杂度

medie2005

看样子无心人在死算. 要不无心人你算一下99阶的. 用mathe的方法,很好确定99阶的周期的.