Is $3$ the only natural number $n$ such that $2^n – n – 2$ is prime?
If there is another, it is greater than $2 \times 10^4$; of course it must be odd, but not a prime, and not divisible by $3$. I don't think there can be an elementary proof that $2^n-n-2$ must be divisible by something related to $n$, because e.g. the least prime factor of $2^{323}-325$ is $2017403$.
Best Answer
As Serge Batalov points out here, $2^{39137}-39137-2$ and $2^{59819}-59819-2$ are both probable primes. According to the links there, both were discovered by Henri Lifchitz in 2005. They have 11782 and 18008 digits respectively, so someone with the right hardware and software should be able to prove their primality using ECPP.
(For what it's worth, I found the first using OpenPFGW, and googling it led me to the link above.)