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阶的周期的.