# How many numbers $2^n-k$ are prime?

We are all familiar with the Mersenne primes $$M_n = 2^n-1$$ and we indeed know that there are some $M_n$ that are prime. However, it is still open whether there are infinitly many $M_n$ that are prime. Now consider $$F_n(k) = 2^n - k$$ with $k \geq 3$ and $k$ odd. I would like to know whether one can answer following questions for some $k$:

(1) Is $F_n(k)$ prime for some $n$?

(2) Is $F_n(k)$ prime for infinitely many $n$?

(3) (If not) For how many $n$ is $F_n(k)$ prime?

The first prime values of $F_n(3) = 2^n - 3$ are given in A050415 and the first prime values of $F_n(5) = 2^n - 5$ are given in A156560.

My hope is that it is easier to show (1), (2) and (3) for the form $2^n-k$ instead of $2^n-1$. In case someone is aware of papers, etc. concerning this 'generalization' I would be glad about the reference.

Edit: Another example: For $k=5$ the first prime value is $F_{39}(5)= 549755813881$.

• Now you've removed the question 'for all k' my answer is no longer a correct answer so I've deleted. – samerivertwice Sep 20 '17 at 4:48

Here's a partial answer (an answer to (1) and more of a comment about (2) and (3)). A lot of this can be found in this OEIS entry.

1) Not necessarily. If $k=509203$ (a Riesel Number), all of the terms are composite.

2) This is a hard problem, and I would be very surprised if anything of this form could be proven (problems of this form tend to be hard: as far as I know, close to the best known result like this is Dirichlet's theorem on arithmetic progressions, and it is not even known whether there exists infinitely many primes in the sequence $\{n^2+1\}$).

3) Again, this is hard in the general case. Due to the existence of Riesel numbers and their covering sets, I wouldn't be surprised if there exists one sufficiently close to a power of $2$ so that $2^n-k$ is indeed a prime, but no other terms are (or something like that). However, I don't think this problem is anything close to tractable in the general case.

Lemma: If there exists a set $P$ of primes such that, for all $n$, there exists a prime $p\in P$ such that $k2^n\equiv 1\bmod p$, then, for all $n$, there exists a prime $p\in P$ such that $2^n\equiv k\bmod p$.

Proof sketch:

Let the smallest $p\in P$ such that $k2^n\equiv 1\bmod p$ for a given $n$ be called $f(n)$, and let the smallest $p\in P$ such that $2^n\equiv k\bmod p$ be $g(n)$.

Step 1: Prove that $f(n)$ is periodic.

Step 2: Prove that one can "invert" the period of $f$ to obtain $g$.

• Thank you, this is already very helpful! For personal understanding: How is the Riesel number of the form $k\cdot 2^n-1$ (just looked it up) connected to the numbers $2^n-k$? Do you say that (concerning my notation) $F_n(509203) = 2^n - 509203$ is always composit, or was this just an example to be careful in general? – Fabian Schn. Sep 20 '17 at 4:50
• Ok, I answer the question concerning Riesel numbers by reading the OEIS entry, thanks. – Fabian Schn. Sep 20 '17 at 4:54
• @FabianSchn. Great! I added a proof sketch that I believe should work to prove that a covering set for one is a covering set for the other (it's been a while since I worked with these numbers so there might be some edge cases I'm not considering or something I'm flat-out doing wrong, but the general idea should be right). Also, just one more note: the Sierpinski numbers can be used to deal with negative odd $k$ correspondingly. – Carl Schildkraut Sep 20 '17 at 4:57