5
$\begingroup$

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$.

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

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Fabian Schn. Sep 20 '17 at 4:50
  • $\begingroup$ Ok, I answer the question concerning Riesel numbers by reading the OEIS entry, thanks. $\endgroup$ – Fabian Schn. Sep 20 '17 at 4:54
  • $\begingroup$ @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. $\endgroup$ – Carl Schildkraut Sep 20 '17 at 4:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.