有效地找到完美的广场

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]),你甚至可以在这里找到一个实现,包括源代码和解决方法的解释.

¹:您可能认为这是一个圆锥曲线.它是,人们已经研究了几千年.因此,我们对它们的理解非常深刻,您的问题实际上非常有名.对它们的研究是一个非常深刻且仍然活跃的数学领域.