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

Is it the case that for every non-negative integer $n$, iterating $n \to 2n+1$ eventually produces a prime number? (This is the same as asking whether for every positive integer $n$, there is a non-negative integer $k$ such that $2^k n - 1$ is prime.) If this is not settled by proof, is there some heuristic argument either way?

• By "eventually", if you mean that after a finite number of iterations, $n \to 2n+1$ will always be prime, then the answer is NO.
– user21436
Dec 25 '11 at 20:54
• @KannappanSampath - No, "always eventually" is not the same as "eventually always". Dec 25 '11 at 21:06
• @Kannappan: No, r.e.s. is asking whether for each $n\in\mathbb{N}$ there is some $k\in\mathbb{Z}^+$ such that $f^k(n)$ is prime, where $f:\mathbb{N}\to\mathbb{Z}^+:n\mapsto 2n+1$ and $f^k$ is the $k$-fold iteration of $f$. Dec 25 '11 at 21:07
• Taking $n$ a large power of $2$ in the second formulation, we would deduce that there are infinitely many Mersenne primes. Which (although true :) ) has not been proved. Dec 25 '11 at 21:22
• I just now edited the question to allow $0$ as an exponent, because this corresponds to performing $0$ iterations (as when the starting $n$ is already prime). Dec 26 '11 at 3:33

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.

• That is right on target -- thank you. Dec 25 '11 at 23:00
• I just googled The little book of bigger primes (2004), which says (p. 238) there are still $101$ candidate Riesel numbers less than $509203$, the smallest being $659$. Ironically, when I was posting the present question, I had running in the background a program doing the $n \to 2n+1$ iterations starting at $n = 658$ (corresponding to candidate Riesel number $659$) -- just now, about six hours later, I interrupted it after it failed to reach a prime in more than $51000$ iterations. Dec 26 '11 at 3:18
• On the page mathworld.wolfram.com/RieselNumber.html it says that when you start at 659 the iterations produce a prime after 800516 iterations.
– KCd
Dec 26 '11 at 4:07
• @KCd - Thanks for the more-up-to-date info! I had only about 750000 iterations to go ;o) (But note that the iterations start with a number one less than the candidate Riesel number; e.g., for candidate $659$ the iterations start with $658$.) PS: Wilfrid Keller's page appears to be even more up-to-date. Dec 26 '11 at 5:14

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.

• If it cannot presently be proved that there exist infinitely many Mersenne primes, and yet (as @GEdgar suggests in his comment above) this is regarded as very likely the case, can some heuristic argument be given for it? Dec 25 '11 at 21:47
• @r.e.s. In fact, there's a conjecture on the density of Mersenne primes, known as the Lenstra-Pomerance-Wagstaff conjecture; there's a pretty good explanation of it at primes.utm.edu/mersenne/heuristic.html Dec 26 '11 at 4:29

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.

• Thanks for the references. Covering systems and Reisel/Sierpinski numbers are entirely new to me. Dec 26 '11 at 0:34
• @r.e.s. If you do delve into it further I'd be delighted to see a summary posted here (I haven't had a chance to keep up on recent work). Dec 26 '11 at 1:09
• Florian Luca and Dan Bacskowski have done some work in Reisel and Sierpinski numbers, if I may add. The former has a paper wherein he derives a covering system that leads to a proof that there exist infinitely many fibonacci numbers which are Reisel numbers as well. Same has been done by same author for Sierpinski numbers as well. The latter also has some papers regarding this.
– nb1
Dec 26 '11 at 8:41
• @NikhilBellarykar - Thanks for the info ... This article appears to be a preprint of "Lucas-Sierpiński and Lucas-Riesel numbers" by Daniel Baczkowski, Olaolu Fasoranti, and Carrie E. Finch, Fibonacci Quart. 49 (2011), no. 4, 334–339. Dec 26 '11 at 14:37
• Another mathematician who writes extensively on coverings is Zhi Wei Sun of Nanjing university- check out his webpage. math.nju.edu.cn/~zwsun/papers.htm
– nb1
Dec 26 '11 at 15:55

(Following up on the connection to Riesel numbers mentioned in other answers ...)

For an infinite set of counterexamples, here is a proof-sketch (adapted from Baczkowski, et al.) showing that $$n \equiv 33737173 \pmod{3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73} \implies \forall k\in \mathbb{N}\ \big(f^k(n-1) \text{ is composite}\big),$$ where $$f:\mathbb{N}\to\mathbb{Z}^+:n\mapsto 2n+1$$ and $$f^k$$ is the $$k$$-fold iteration of $$f$$.

Note that since $$f^k(n-1) = n\cdot 2^k - 1$$ for $$n\in\mathbb{Z}^+$$, the above is equivalent to
$$n \equiv 33737173 \pmod{3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73} \implies \forall k\in \mathbb{N}\ \big(n\cdot 2^k-1 \text{ is composite}\big),$$ which is to say that all such $$n$$ are Riesel numbers.

The following congruence classes are sufficient for this purpose:

$$\text{congruence classes for }k\text{ and }n\\ \begin{array}{|c|c|} k\equiv a_i\pmod{m_i} & n\equiv b_i\pmod{p_i} \\ \hline 0\pmod{2} & 1\pmod{3} \\ 0\pmod{3} & 1\pmod{7} \\ 1\pmod{4} & 3\pmod{5} \\ 11\pmod{12} & 2\pmod{13} \\ 7\pmod{36} & 4\pmod{73} \\ 19\pmod{36} & 18\pmod{37} \\ 31\pmod{36} & 13\pmod{19} \end{array}$$

As can be directly verified, the entries in the above table have the following properties:

1. The congruence classes for $$k$$ form a covering system for the integers; i.e., every integer $$k$$ satisfies at least one of the congruences $$k\equiv a_i\pmod{m_i}$$. (To verify this, it is necessary to check only $$k\in \{0,1,2,\dots,35 \}$$, because $$36$$ is the least common multiple of the moduli $$\{2,3,4,12,36\}$$.)

2. The congruences are such that in each row $$i\ (1\le i\le 7)$$, $$b_i\cdot 2^{a_i} \equiv 2^{m_i} \equiv 1\pmod{p_i}$$. Consequently, for all $$i\ (1\le i\le 7)$$ $$k\equiv a_i\pmod{m_i}\quad \& \quad n\equiv b_i\pmod{p_i}\\ \implies\ n\cdot2^k \equiv b_i\cdot 2^{a_i+r\cdot m_i} \equiv (b_i\cdot 2^{a_i})(2^{m_i})^r \equiv 1 \pmod{p_i}.$$

Now, by the Chinese Remainder Theorem, there exist simultaneous solutions to all seven of the congruences for $$n$$; in particular, the Extended Euclidean Algorithm yields the solutions $$n \equiv 33737173 \pmod{3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73}.$$ Therefore, for every such $$n$$, $$\forall k\in \mathbb{N}\ \big(n\cdot2^k-1\text{ has at least one divisor in the set }\{3,5,7,13,19,37,73 \}\big).\quad\quad\text{QED}$$