When $2^n + m$ is a perfect square This problem showed up when I was doing some recreative math, but the problem was interesting itself and I found very difficult to solve.
Given $n\in\mathbb{N}$ and $m\in\mathbb{Z}$, the question is: There is a method to know if $2^n + m$ is a perfect square? 
Thank you very much.

Assume $2^n+m=a^2$ with $a,m,n\in\mathbb N$, $0<m\le\sqrt{2^n}$.
If $n=2k$ is even, then $(2^k)^2=2^n<a$ and $(2^k+1)^2=2^n+2\cdot 2^k+1>2^n+m$, contradiction.
If $n=2k+1$ is odd, then $\left(\frac a{2^k}\right)^2=2+\frac m{2^{2k}}$, i.e. $\frac a{2^k}$ is a relatively good approximation for $\sqrt 2$.
In fact with $\frac a{2^k}>\sqrt 2$ we find that
$$\frac m{2^{2k}}=\left(\frac a{2^k}\right)^2-2=\left(\frac a{2^k}+\sqrt2\right)\left(\frac a{2^k}-\sqrt2\right)>2\sqrt 2 \cdot\left(\frac a{2^k}-\sqrt2\right),$$
hence 
$$0<\frac a{2^k}-\sqrt2<\frac{m}{2^n\sqrt 2}\le \frac{\sqrt{2^n}}{2^n\sqrt 2}=\frac1{2^{k+1}}.$$
Letting $a=\lceil2^k\sqrt 2\rceil$ will therefore lead to an instance of $2^n+m=a^2$ about 50% of the time.
If we relax the restriction on $m$ to $m\le 2\cdot\sqrt{  2^n}$, this rate will go up to 100%.
For example $2^{59}+9092137 = 759250125^2$.
