数论方面算法问题,如何快速判断n!+1为完全平方数的n
来源:学生作业帮 编辑:大师作文网作业帮 分类:数学作业 时间:2024/10/01 10:19:50
数论方面算法问题,如何快速判断n!+1为完全平方数的n
或者说快速得知一段区间内满足这种性质的n的个数
比如4!+1=5*5 +1=11*11 +1=71*71等等
拒绝一切只用暴力枚举的思想做的,要枚举也得有极强剪枝才行
欢迎一切数论思想、结论或方法!
或者说快速得知一段区间内满足这种性质的n的个数
比如4!+1=5*5 +1=11*11 +1=71*71等等
拒绝一切只用暴力枚举的思想做的,要枚举也得有极强剪枝才行
欢迎一切数论思想、结论或方法!
你先要讲清楚你所说的区间大致是从几到几的区间,这直接影响到什么样子的算法是可以接受的.不要很笼统地说区间越大越好,算法越快越好.
在n比较小的时候当然是枚举最方便,即使是需要考虑大数运算的复杂程度.
当n比较大之后n!的末尾是连续的k个0,k可以通过1:n中5的因子出现次数来得到,这样如果n!+1是平方数的话,其平方根必定是p*10^k+1或者p*10^k-1的形式,这样相当于验证n!=A(A+2),可以先用实数运算算出ln(n!)=ln((n-1)!)+ln(n)(这步的舍入误差其实是很小的),仅当估计得到的A或者A+2非常接近p*10^k的形式时才进一步验证.
当n大到一定程度的时候,A^2>>2A,只需要验证ln(n!)=2ln(A),当A非常接近p*10^k时才进一步验证.
再说一下所谓的“进一步验证”,首先是利用浮点舍入误差分析计算出误差界来估计所谓的“非常接近”,然后对A和A+2进行质因子分解(也要用大数计算).
在n比较小的时候当然是枚举最方便,即使是需要考虑大数运算的复杂程度.
当n比较大之后n!的末尾是连续的k个0,k可以通过1:n中5的因子出现次数来得到,这样如果n!+1是平方数的话,其平方根必定是p*10^k+1或者p*10^k-1的形式,这样相当于验证n!=A(A+2),可以先用实数运算算出ln(n!)=ln((n-1)!)+ln(n)(这步的舍入误差其实是很小的),仅当估计得到的A或者A+2非常接近p*10^k的形式时才进一步验证.
当n大到一定程度的时候,A^2>>2A,只需要验证ln(n!)=2ln(A),当A非常接近p*10^k时才进一步验证.
再说一下所谓的“进一步验证”,首先是利用浮点舍入误差分析计算出误差界来估计所谓的“非常接近”,然后对A和A+2进行质因子分解(也要用大数计算).
一道完全平方数问题,求详解:n为正整数,证明:n^7+1不是一个完全平方数
N是大于1的自然数,N的阶乘是否可能为完全平方数?结论如何证明?
n为正整数,n^2+(n+1)^2是一个完全平方数,求n的值
证明n乘(n+1)不可能是完全平方数(n为任何数)
如何证明对任和自然数n,n(n+1)都不可能是完全平方数?
2的n次幂+256是完全平方数(n为正整数)求n
求证:(n+2002)(n+2003)(n+2004)(n+2005)+1是一个完全平方数(n为正整数)
证明(n-2)n(n+1)(n+3)+9(n为正整数)是完全平方数
关于数论的一个小问题如果一个数只有0和1组成现在要求一个数是N的倍数的最小值这个数现在比如说是100 对N求余 余数为r
n为正整数,若n^2+5n+22为完全平方数,则n的值是多少.
求一数论问题,求一最小自然数n,使他的1/2是一个平方数,1/3是立方数,1/5是一个5次方数.
有关完全平方数的问题已知n是正整数 4^7+4^n+4^1998是一个完全平方数 求n的值