Question

数论方面算法问题，如何快速判断n!+1为完全平方数的n

或者说快速得知一段区间内满足这种性质的n的个数

比如4!+1=5*5 5!+1=11*11 7!+1=71*71等等

谢谢
拒绝一切只用暴力枚举的思想做的，要枚举也得有极强剪枝才行

欢迎一切数论思想、结论或方法！

Answer 1

你先要讲清楚你所说的区间大致是从几到几的区间，这直接影响到什么样子的算法是可以接受的。不要很笼统地说区间越大越好，算法越快越好。

在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进行质因子分解(也要用大数计算)。

Answer 2

写一些个人的想法，谈不上解答，大家一起讨论讨论。

*****************************************************
（1）首先分析n!：

当n>=5时，这个数的末位数字必然是0，这个是很显然，因为n!里面有因数2和5，乘起来必然末位是0.

那么n!+1末位必然是1.

如果这个数是完全平方数，n!+1=a^2,那么a的末位数字不是1就是9.

（2）其次看n!的变化规律：

n!到(n+1)!就要扩大n+1倍！当n很大时，这种增长是相当剧烈的。如果我们把1!,2!,3!,...标在数轴上的话，我们会发现他们越来越稀疏。

比如，从10!到11！，这是一个很大的区间了（都已经差一个数量级了），然而这个区间理要考察的数只有两个。所以我觉得题中“得知一段区间内满足这种性质的n的个数”其实不想想象中的那样多，很有可能好大一个区间里只有一个数是n!+1，甚至一个都没有。

（3）结合上面两部分析：

好大的区间内只有少数几个数是n!+1，在这其中有可能是完全平方数的话，只有是“1^2”或者“9^2”这两种类型。那么我觉得只要用试验法就行了。找出有可能是答案的几个数试一下，如果都不是，那就能确定这段区间里没有这样的数.

**************************************************************

本人是学工科的，对《数论》《近世代数》只是略知一二，暂时无法想出纯数学解法，还请谅解。