Prime numbers in Collatz sequences

Solution 1:

We can produce an infinite family of counterexamples for the case where the starting value is odd.

Let $p\geq 7$ be an arbitrary prime. Then $p-1$ is even, so

$$2^{p-1}-1\equiv (-1)^{p-1} -1 \equiv 1-1 =0 \pmod 3$$

So $\frac{2^{p-1}-1}{3}\in\mathbb Z$ and this number is odd, because $2^{p-1}-1$ is odd. So, take it as starting value, the Collatz sequence is: $$\left(\frac{2^{p-1}-1}{3},2^{p-2},2^{p-3},\dots,1\right)$$ By Fermat's little theorem: $$2^{p-1}-1\equiv 0\pmod p$$ The condition on $p$ ensures, that $\frac{2^{p-1}-1}{3}>p$ holds. But $p\mid 2^{p-1}-1$ implies $p\mid\frac{2^{p-1}-1}{3}$ (because $p\neq 3$), so this number can not be prime. Hence, the sequence contains no primes (except $2$ of course).

You could always exclude this case. However, it seems like we could continue to produce other counter-examples using this very same "back-engineering" technique to produce a Collatz sequence with non-prime initial values, that leads to a power of $2$. This strongly suggests that a characterisation of such starting values is not easy.

Solution 2:

The problem could be better investigated when the Collatz-transformation is considered by its inverse. And usually I define the compressed Collatz-transformation as beginning at an odd integer $a$, doing one step $ a'=3a+1$ and including also all steps $a''=a'/2. a'''=a''/2,... b$ until $b$ is odd again. In short $$ a \to b \text{ is defined as } \qquad b = {3a+1 \over 2^A } \qquad \qquad \text{ where $A$ is such that $b$ is odd} $$ The "inverse" view at this is the 2-parametric map, depending on odd $b$ and $A$ $$ a = {b \cdot 2^A -1 \over 3}\qquad \qquad \text{ where $A$ is such that numerator is divisible by $3$} $$ For instance, for $b=1$ we get for increasing $A$ the sequence $$a_{b,k} = \{ 1,5,21,85,341,...\} = { 1 \cdot 4^k-1 \over 4-1} \qquad \text{and } A = 2k$$ giving us that all $a_{1,k}$ fall down to $b=1$ by one compressed Collatz transformation, thus involving only exactly 1 odd number. So we have already a handful of examples: $$ \begin{array} {} a_{1,2} \to 1 &:& 5,16,8,4,2,1 &\text { and $5$ is prime} \\ a_{1,3} \to 1 &:& 21,64,32,16,8,4,2,1 &\text { and $21$ is composite} \\ a_{1,4} \to 1 &:& 85,256,128,...,4,2,1 &\text { and $85$ is composite and } a_{1,2} | a_{1,4} \\ a_{1,5} \to 1 &:& 341,1024,512,...,4,2,1 &\text { and $341$ is composite and } 11 \cdot 31 = a_{1,5} \\ a_{1,6} \to 1 &:& 1365,4096,...,4,2,1 &\text { and $1365$ is composite and } a_{1,2} | a_{1,6} \text{ and } a_{1,3} | a_{1,6} \\ a_{1,7} \to 1 &:& 5461,16348,...,4,2,1 &\text { and $5461$ is composite and } 43 \cdot 127 = a_{1,7} \\ ... \end{array} $$ and I think the fact of $a_{1,k}$ being composite keeps on for all subsequent $k$. (I checked this up to $k=200$ and possibly this can also analytically be shown.)
After that we can proceed and using all $a_{1,k}$ we can set $b_k=a_{1,k}$ and as far as $b_k$ is not divisible by $3$ we can determine for increasing $A$ the sequences $a_{b_k,j} $. For instance for $b_2=5$ we get $$ a_{5,j}= \{ 3,13,53,213,...\} = { 5 \cdot 2 \cdot 4^{j-1}-1 \over 4-1} \qquad \text{and } A = 2j-1$$ and all of that numbers $a_{5,j}$ have the prime $5$ in their trajectory down to $1$: {$ 3,10,\quad 5,16,8,4,2,1$}, {$13,40,20,10,\quad 5,16,8,4,2,1$} and so on.

Of course all $a_{85,j}$,$a_{341,j}$, ... have the next odd number in their trajectory composite as far as $85,341,...$ are composite themselves - and this follows readily from the above discussed list.

The occurence of primes in the lists $a_{b,j}$ (for any valid $b$ and $j$) is at most spurious, and the more lists are involved in that iteratively expansible system the spuriousness of primes in the trajectories shall be exponentially improve, so most of the trajectories in this view of the Collatz-transformation show compositeness of at least one member and a conjecture might possibly better formulated as complementary of yours : "most trajectories contain at most one prime" - and perhaps this can be made much sharper by deeper consideration of the above scheme.