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?
 A: 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.
A: 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.
It follows from this that your conjecture is wrong for $n = 509202$.
A: (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:


*

*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\}$.)

*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}$$
A: 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.
