How can I find the first perfect square from the function: f(n)=An²+Bn+C? B and C are given. A,B,C and n are always integer numbers, and A is always 1. The problem is to find n.
Example: A=1, B=2182, C=3248
The answer for the first perfect square is n=16, because sqrt(f(16))=196.
My algorithm increments n and tests if the square root is a integer number.
This algorithm is very slow when B or C is large, because it takes n calculations to find the answer.
Is there a faster way to do this calculation? Is there a simple formula that can produce an answer?
Best Answer
First let's do the case where $B=2b$ is even.
$x^2=n^2+2bn+c=(n+b)^2+c-b^2$, $c-b^2=x^2-(n+b)^2=(x-n-b)(x+n+b)$. Factor $c-b^2$; if $c-b^2=de$ with $d\le e$ of the same parity then let $x-n-b=d,x+n+b=e$ so $n=(e-d)/2-b$.
So, the method is to compute $c-b^2$, write it as a product $de$ of two numbers both even or both odd, and then the formula gives you $n$. You want $n$ as small as possible, take $d,e$ so $(e-d)/2-b$ is small.
If $B$ is odd then first multiply by 4: $4x^2=4n^2+4Bn+4C=(2n+B)^2+4C-B^2$ and proceed as above.