fibonacci(10^14) % 1234567891011是多少?

mathematica

我傻了！郭在二楼已经说过了！其实他是这个问题的行家！ 难不倒他的！ 毕竟他连这个程序都写出来了，我建议郭再用hugecalc核算一下 mathe的计算结果！虽然我相信mathe的是正确的！ 毕竟两个独立的计算软件更可靠一些！

gxqcn

这个其实不就是lucas序列吗？其实郭的素性判定算法中有，我在第一个回复的时候就说了，只是郭愿不愿意显露他的身手而已！ mathematica 发表于 2012-2-21 11:10

Lucas 序列与 Fibonacci序列是两个不同的序列， 虽然他们的递推公式是一样的，但前两项值不相同。 还有，我不是不愿显露身手，而是没有什么好显露的， 因为我的表达不够好，所以才先简单提一下，如果有疑问再继续展开。

gracias

谢谢各位,我也是用pari/gp算出来的

mathe

方法很妙，但最后还有个1/sqrt5如何处理？ gxqcn 发表于 2012-2-21 09:30

既然$\omega={sqrt{5}-1}/2$我们可以得到$sqrt{5}=2\omega+1$ 实际上，如果模是一个素数p，那么问题就变成在有限域$F_p$上fibonacci数列通项公式问题，由于是数域，我们可以求特征方程$x^2-x-1=0$的两个根。但是如果特征方程不可约，那么实际上根在扩张域上。而如果多项式可约(这时$p-=1,4(mod 5)$),那么通项公式会更加简单。但是无论哪种情况，我们都还是可以采用这种同样的符号运算方法。由此，当模是若干个互不相同的素数乘积（不包含5）时，必然也可以。但是如果模含有某个素因子的高次时，我不确定是否可以用这种方法，但是感觉应该是可行的。但是如果模是5的倍数，那么必然不可行，（因为$sqrt{5}$无法表示了),但是我们可以将模5的幂的部分分开处理，然后结果合并。

gxqcn

$sqrt{5}=2\omega+1$ 这步我也推出来了，但如何去分母我还不会做。。。

mathe

对于模不含素因子5，可以用数学归纳法证明符号运算方法均可以行。而$1/{sqrt{5}}-=2*\omega-3(mod m)$ (在Pari/gp中计算1/Mod(2*x+1,x^2-x-1)即可 于是全部只需要做乘法即可。

gxqcn

$(2\omega+1)(2\omega-3)=4(\omega^2-\omega-1)+1=1$，我怎么就没想到呢？ 非常感谢 mathe 的解答，现在我才茅塞顿开，畅快！

mathe

上面弄错了，这里的$\omega$不是黄金分割点，而是${1+sqrt{5}}/2$,所以$sqrt{5}=2\omega-1$,而$1/{sqrt{5}}={2\omega-1}/5$,这也是为什么模是5的倍数时无法使用，因为无法除5.

gxqcn

还好，不影响整体思路。

mathe

发现模是5的幂也有很快的算法，只是同前面的方法不同。 我们假设模为$5^k$,所以通常k不会很大，于是 $F_n=1/{sqrt{5}}(({1+sqrt{5}}/2)^n-({1-sqrt{5}}/2)^n)=1/{2^{n-1}}\sum_{h=0}^{+infty}((n),(2h+1))5^h -= 1/{2^{n-1}}\sum_{h=0}^{k-1} ((n),(2h+1))5^h (mod 5^k)$ 其中$((n),(2h+1))$就是组合数${n(n-1)...(n-2h)}/{(2h+1)!}$