1
$\begingroup$

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.

  • 1
    Is $p$ just an integer, or a prime? The symbol $p$ is usually reserved for primes.2012-09-12
  • 0
    You are right, im going to change this, p is not necessarily a prime.2012-09-12
  • 0
    What is special about this? You can test if a natural is square, and all squares $a^2$ can be written in this form in $\lfloor \log_2 a^2 +1 \rfloor$ ways (assuming $0 \in \mathbb N$).2012-09-12
  • 0
    @Ross Millikan is right: unless $p$ IS a prime, this isn't very interesting.2012-09-12
  • 0
    This problem is suposed to work with $n,m$ very big. I was looking for some general method working fast enough with big numbers, or maybe some formula like $F(n,m)=$ $Yes$ or $No$. $Yes$ for "is a perfect square" and $No$ for "not a perfect square".2012-09-12
  • 0
    What is not interesting today may be interesting tomorrow2012-09-12
  • 1
    @Integral For very large $m$, $n$ this will be an exceedingly rare event (assuming a reasonably uniform distribution). In this case you may want to use a probabilistic method to rule out cases quickly: for instance compute $2^n+m$ modulo products of small primes and check that the result is a quadratic residue.2012-09-12
  • 0
    @Integral Also when $n$ is even you can be assured that $2^n+m$ is never a square unless $m=0$ or $|m| > 2^{n/2+1}$.2012-09-12
  • 0
    Thank you very much Erick.2012-09-12

1 Answers 1

4

Assume $2^n+m=a^2$ with $a,m,n\in\mathbb N$, $0.

If $n=2k$ is even, then $(2^k)^2=2^n 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$.

  • 0
    at the beggining, its a,m,n in naturals, not a,b,n, right?2012-09-12
  • 0
    Thank you Hagen, your answer is very helpfull!2012-09-12
  • 0
    @Integral: Oops, sure - thanks2012-09-12