Does iterating $n \to 2n+1$ always eventually produce a prime number?

Solution 1:

The Riesel Numbers are odd numbers $k$ such that $k\cdot 2^N-1$ is never prime. It is known that there are infinitely many Riesel numbers. It follows that there are infinitely many $n$ such that your iteration, starting at $n$, produces no primes.

The smallest known Riesel number is $509203$, but there may be smaller ones. The Riesel numbers are the obscure cousins of the Sierpinski Numbers.

Solution 2:

The general formula for this sequence of iterations is $a_{n} = 2^{k}(n + 1) - 1$. So if we set $m = n + 1$, then you're asking if, for all $m \geq 1$, there's at least one prime of the form $2^{k}m - 1$. On the case of $m = 1$, we get the form of Mersenne primes. It is unknown whether there are infinitely many Mersenne primes. Your conjecture, however, would imply the existence of infinitely many of them.

Proof: suppose that $2^{p} - 1$ is the largest Mersenne prime. Then set $m = 2^{p + 1}$. By your conjecture there's at least one prime of the form $2^{k + p+1} - 1$. Regardless of the value of $k$, this prime is bigger than $2^{p} - 1$; therefore we reached a contradiction.

I do not know if there is a simple argument to disprove your conjecture; but certainly proving it true is not within our current abilities.

Solution 3:

As Andre mentioned, there is much prior related work on Riesel and Sierpinski numbers and related results. These results are prototypical covering set / system inferences. As an introduction I think you will find very interesting Wieb Bosma's Some computational experiments in number theory.

This is based on an earlier paper where the well-known Lucas–Lehmer type tests for $\rm\ 2^n\pm 1\ $ were generalized to numbers of the form $\rm\ h\cdot 2^n\pm 1\ $ and $\rm\ h\cdot 3^n \pm 1\ $ using covering systems. Here he shows how covering systems can be used, with cubic reciprocity, to produce a simple criterion for the primality of $\rm\ n = h\cdot 3^k + 1 $ in terms of a cubic recurrence modulo n; the starting value depends only on the residue class of k modulo some covering modulus M. The methods employed are closely connected to the techniques employed in the study of Riesel and Sierpinski numbers, so they will prove highly pertinent to your question.

The references of Wieb's paper will quickly lead you to the relevant literature. See also Lenny Jones, Variations on a Theme of Sierpinski, 2007; Brunner et al. Generalized Sierpinski numbers base b.