Perfect Square Problem

Is there a formula for determining the next highest number above a given number a, that is both a perfect square and is a "perfect square" above the given number? e.g. given number 33, 49 (a perfect square) is a value of 16 (a perfect square) higher than 33. In other words I am looking for the next highest square number above any number using only steps of increasing squares, e.g. 1,4,9,16 etc. Thanks in advance.

• Are you looking for the smallest $n$ such that $n^2-a=m^2$ ? – Yves Daoust Feb 2 '17 at 11:47
• If I understand your query, yes, but I don't know either n or m. – ratking Feb 2 '17 at 11:51
• For the number $a$ you want to find minimal $x>0$ and some integer $y>x$ such that $a+x^2=y^2$. This is equivalent to $a=(y-x)(y+x)$. So we're trying to split $a$ into product $a=bc$ such that $y-x=b,y+x=c$ and make $x=(c-b)/2$ as small as possible. That is, to represent $a$ as a product of numbers as close to each other as possible. Equivalently, with $b$ and $c$ as close to $\sqrt{a}$ as possible. That seems to not have any solution not involving some brute-force. – Wolfram Feb 2 '17 at 11:52
• Hmmm, thanks. Being a peaceful guy, I was looking for something NOT involving brute force. Oh well, I guess I should suit up! – ratking Feb 2 '17 at 11:56

As the condition can be written

$$n^2-a=m^2$$ or

$$(n-m)(n+m)=a,$$

you need to factor $a$ as $a=bc$ with $b\ge c$ and $b,c$ of the same parity, and set $$n=\frac{b+c}2,m=\frac{b-c}2.$$

For $a=33$, $b=11,c=3$ yields $n=7,m=4$.

• uh ... $33=3\times 11$ is prime! I never would have guessed. – Oscar Lanzi Feb 2 '17 at 12:27
• @OscarLanzi: oooops... – Yves Daoust Feb 2 '17 at 12:39

If you don't want to bother finding the factors of a, then you can always express a as $a= ((a+1)/2)^2 -((a-1)/2)^2$ provided a is odd. For the example of $a=33$, we get $a=33=17^2-16^2$ or if you want to write it as $33+16^2=17^2$. Note that $33=2\cdot16+1$ so the lhs becomes $(16+1)^2=17^2$.