1

How to 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 finding 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 nunber.

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?

Improve this question
2
  • If I were you I would ask this in the math stackexchange. Commented Feb 2, 2012 at 15:27
  • 4
    Maybe one for math.stackexchange.com Commented Feb 2, 2012 at 15:27

1 Answer 1

Reset to default
11

What you are looking for are integer solutions to a special case of the general quadratic Diophantine equation1

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

where you have

ax^2 + bx + c = y^2

so that A = a, B = 0, C = -1, D = b, E = 0, F = c where a, b, c are known integers and you are looking for unknown x and y that satisfy this equation. Once you recognize this, solutions to this general problem are in abundance. Mathematica can do it (use Reduce[eqn && Element[x|y, Integers], x, y]) and you can even find one implementation here including source code and an explanation of the method of solution.

1: You might recognize this as a conic section. It is, and people have been studying them for thousands of years. As such, our understanding of them is very deep and your problem is actually quite famous. The study of them is an immensely deep and still active area of mathematics.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

You may also want to add a link to a pdf on Solving the generalized Pell equation
Jim and Jason, thanks a lot for your help, your answer were very helpfull

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.