高效找到完美广场

Question

如何从功能中找到第一个完美广场：f(n)=An²+Bn+C？ B和C给出。 A，B，C和n总是整数，A总是1.问题是找到n。

Example: A=1, B=2182, C=3248

第一个完全平方答案为n = 16，因为sqrt(f(16))=196。

我的算法递增n并测试平方根是否是整数nunber。

当B或C很大时，该算法非常慢，因为需要n次计算才能找到答案。

有没有更快的方法来做这个计算？有一个简单的公式可以产生答案吗？

Answer 1

你在找什么是整数解的一般二次丢番图方程

Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0 

，你有一个特殊的情况下

ax^2 + bx + c = y^2 

使A = a, B = 0, C = -1, D = b, E = 0, F = c其中a，b， c是已知的整数，您正在寻找满足此方程的未知x和y。一旦你意识到这一点，这个普遍问题的解决方案是丰富的。 Mathematica可以做到这一点（使用Reduce[eqn && Element[x|y, Integers], x, y]），你甚至可以找到一个实现here，包括source code和method of solution的解释。

：您可能会将其识别为conic section。它是，并且人们已经studying them for thousands of years。因此，我们对它们的理解非常深刻，您的问题其实非常有名。他们的研究是immensely deep and still active area of mathematics。