TITLE: How well do prime-started Collatz sequences cover the integers?
QUESTION [4 upvotes]: Consider a liberal definition of the Collatz sequence starting from some prime number $p$:
$$
C_n(p) = \left\{ \matrix{p & n=0\\C_{n-1}(p)/2 & C_{n-1}(p) \mbox{ even}
\\ 3C_{n-1}(p)+1 & C_{n-1}(p) \mbox{ odd}}\right.
$$
That is, we are including the intermediate results rather than dividing by $2^k$ all at once.  
My curiosity is about the set $\bar{C}$ of all integers that cannot be reached as $C_n(p)$ for any prime $p$. $\bar{C}$ is not empty, since no number of the form $3t$ for $t>1$ is a non-starting member of a Collatz sequence.  

Is it known whether there exists any integer $m \not\in 3\Bbb Z$ such that $\forall (n,p) : C_n(p) \neq m$? 

If so, is anything known about whether there is a greatest such integer, and if there is not, then about the distribution of the members of  $\bar{C}-3\Bbb Z$?

REPLY [0 votes]: Almost certainly the prime-started Collatz sequences completely cover the integers (excepting multiples of 3).
If we take the immediate odd predecessors $X_x$ of any odd number $x\notin3\mathbb{N}$, they are of the form $f^n(x_0)$ where $f(y)=4y+1$ and $x_0$ is their least element.
For example $X_1=\{1,5,21,85,\ldots\}$ are the immediate odd predecessors of $1$
$x_0$ takes the value of either $\frac{2x-1}{3}$ or $\frac{4x-1}{3}$ dependent upon whether $x\equiv$ $1$ or $2$ mod $3$.
The prime number theorem for arithmetic progressions states that the prime numbers are evenly distributed among the residue classes $a$ modulo $n$ with greatest common divisor $(a,n)=1$.
A good candidate for an answer may be to extend this to provide an argument that $p\in Y_x$ for some $p\in$ prime $\forall x$ which would seem likely, and this would prove there is no $m$ you seek, which is not preceded by some prime.
This theorem isn't decided for geometric progressions but Paolo Leonetti has shown it's false for the exponential-type sequences of predecessors (like $X_1$) found in the Collatz graph.
EDIT 25 MAY 2018
If you can follow the trail, following this question Peter has searched for sequences of the above form not containing primes and identified some candidates then in this answer Paolo Leonetti has shown that sequences starting with some $x_0$ satisfying $3x_0+1$ is square, are never prime.
The smallest example is the sequence of odd numbers which lead directly to $25$:
$X_{25}=33,133,533,\ldots$
none of which is prime.  Apart from these predecessors of squares, sieving for primes shows sequences of predecessors containing no primes are rare (none else found).
However even if the immediate odd predecessors of some number are one of the prime-free sequences like $X_{25}$, two-thirds of the numbers in that sequence still have their own sequence of predecessors and every one of those, as well as their predecessors in turn, would have to also be sequences of squares and this is clearly impossible.
It remains to prove definitively that A) ONLY the sequences satisfying $3x+1$ is a square number, are the primefree sequences of immediate odd predecessors, and B) that no sequence $X_n$ and all of its predecessors are square numbers. But this looks far from possible
{"set_name": "stack_exchange", "score": 4, "question_id": 2324448}