This question/request is twofold. First, if this is a stupid question or if it has been addressed before, please say so (bluntness is optional), and I will crawl back into my cave...
My question: is there always at least one prime number in a Collatz sequence? If so, why? If anyone more knowledgable in number theory can provide me with (a link to) a proof, I'd appreciate it.
I have been playing around with this idea and if we disregard the prime number 2 the sequence will always be "attracted" to the prime number 5, which will then provide the ending sequence 16, 8, 4, 2, 1.
I then tried a number of starting values, ran them through the Collatz algorithm to see how many prime numbers there are before the sequence hits 5. There is always at least one prime number, most of the time there are more. Starting the sequence with 363 I came up with 9 primes before hitting on 5. With 364 there are 18. Some other starting values:
363 - 9 primes, 364 - 18, 365 - 18, 366 - 16, 367 - 9, 368 - 2, 369 - 2, 370 - 11
Even if you disregard this as a silly question, thanks for reading it anyway.
John
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.