高效找到完美廣場

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。