sqrt(d)用连分式公式展开问题
怎样判断某个数P是否是sqrt(d)用连分式公式展开时出现的P_{n+1}的值，有无简单的方法。该问题与因子分解密切相关，不知有无好的算法不通过展开直接计算判断。 到现在为止，还没发现啊，如果有了，分解因数不就简单了 将 sqrt(d)*P_{n+1}四舍五入，设为N，看N是否满足下面的式子：|\sqrt{d}-N/P_{n+1}|<1/P_{n+1}^2 我用几个数验证了一下，结果的确正确，不知wayne是怎样得到上述结论的呢。而为什么又是四舍五入呢 4# wsc810
这不是我得出来的，书上肯定有的，关于近似分数的那点理论。 wayne,今天我找到了反例，取d=4185,P=2,你的公式是不是|sqrt(d)-N/P|<1/P^2,（我这边手机浏览公式解析不太正确）不信你展开看看，你的公式的出处在什么地方，能否贴上图看看。 6# wsc810
准确的来说，如果q_n/p_n是sqrt(d)的近似分数，那么不难推出：
p_n * q_{n-1} -p_{n-1}*q_n =(-1)^(n-1)
由此，当n比较大时，我们可以放缩，就有|sqrt(d)-N/P|<1/P^2成立了 说来说去，咱们对P_n,Q_n的理解是不同的，难怪我找到了反例，我说的P_n,Q_n,是要求a_n时，得到的副产品，其中Q_n的值是如下pell方程式等号右边的值，即
p_{n-1}^2-d*q_{n-1}^2=(-1)^n*Q_n
而P_n是如下方程式等号右边的值。即
p_n*p_{n-1}-d*q_n*q_{n-1}=(-1)^n*P_n
页:
[1]