I searched for natural numbers $n$, where $2^n-n$ and $2^n+n$ are both prime for the range of $n \le 10^5$ on PARI/GP and found that 3, 9 are the only solutions in this range.

Note that since $2^n-n$, $2^n$, $2^n+n$ are in arithmetic progression and $2^n$ is not divisible by 3, $n$ must be a multiple of 3.


$(1)$ Are $3$, $9$ the only natural numbers $n$ for which both $2^n-n$ and $2^n+n$ are prime?

$(2)$ If not, then can you prove or disprove that there are finite natural numbers of this type?

  • 1
    $\begingroup$ guess mod 5 was too complicated. $\endgroup$ – Roddy MacPhee May 8 at 23:41
  • 2
    $\begingroup$ Ignoring small factors, the chance that either is prime is about$1/\ln (2^n)=1/(n\ln 2)$. The chance that both are prime is the square of that, or $2.08/n^2$. This has a finite sum, so I expect a finite number of solutions. $\endgroup$ – Empy2 May 9 at 11:16
  • $\begingroup$ Since you have checked up to $10^5$, and the tail of my sum is $\sum_{n=10^5}^\infty 2.08/n^2\approx 2/10^5$, I would put the chances of any more solutions as $0.00002$ $\endgroup$ – Empy2 May 9 at 11:26
  • $\begingroup$ but 31% of valid n values restricted to by 2, and 3 have small factors ( <13). $\endgroup$ – Roddy MacPhee May 9 at 11:29
  • $\begingroup$ @Empy2 how do you know that the chance for finding either prime is $1/ \ln (2^n)$ ? $\endgroup$ – Mathphile May 9 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.