Эффективно найти идеальный квадрат

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 и проверяет, является ли квадратный корень целым числом.

Этот алгоритм очень медленный, когда 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]), и вы даже можете найти одну реализацию здесь , включая исходный код и объяснение метода решения .

¹ : Вы можете распознать это как коническое сечение . Это так, и люди изучают их в течение тысяч лет . Таким образом, наше понимание их очень глубокое, и ваша проблема на самом деле довольно известна. Изучение их - чрезвычайно глубокая и все еще активная область математики .