4

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$?

Mark Fischler
  • 41,743
  • +1. A possibly relevant and related-in-spirit question: is it known that $C(p)={C_n(p): n\in\mathbb{N}}$ never has asymptotic density $1$? I don't even see why that should be easy to prove ... – Noah Schweber Jun 16 '17 at 01:01
  • Do I understand you correctly, that this means in a reverse view the following. (1) Let $R(a;A) =R^{1}(a;A) = {2^A - 1 \over 3} $ (where $A$ is chosen that $R(a;A)$ is integer) . (2) define the iteration $R^{n}(a;A_1,A_2,...,A_n) = R( R^{n-1}(a;A_1,A_2,...,A_{n-1});A_n) $ . Then you seem to ask the question: "does exist a non-prime number $m$ such that also all numbers $R^n(m;A_1,A_2,...A_n)$ are non-prime?" . Did I get you right? – Gottfried Helms Jun 16 '17 at 09:24
  • Upps., of course I meant $R(a;A)= { a \cdot 2^A-1 \over 3}$ (I forgot the $a$) in the earlier comment. – Gottfried Helms Jun 16 '17 at 15:29
  • What I can tell you is that you will never find one! Your best bet for proving this is to take any odd integer $x$ which is not a multiple of $3$ and show that the set ${f^q(x):f(x)=4x+1\land q\in\mathbb{N_{>0}}}$ must always contain a prime. Every odd number which is not a multiple of $3$ is a successor of such an $x$ and of every element in that set. – it's a hire car baby Jun 16 '17 at 16:23
  • Do I understand correctly you are asking for some integer $m$ which is not a multiple of $3$ and is not a successor of a prime number? – it's a hire car baby Jun 18 '17 at 13:43
  • I'm really curious to know what motivated this question? – it's a hire car baby Mar 24 '18 at 10:13
  • I can now prove this is equivalent to the conjecture itself. Did you know this already? A good mathematician having read Lagarias' work would be able to deduce this. – it's a hire car baby Oct 16 '18 at 07:54
  • I have read Jeff's work out of curiosity (he used to be a poker buddy of mine) but did not delve deeply enough to see how his paper lets you show that the non-existence of such an $m \not\in 3\Bbb{Z}$ implies the Collatz conjecture itself. I'd love to see that proof. – Mark Fischler Oct 19 '18 at 05:34
  • Sorry Mark I only just saw your comment as you didn't ping me. I say I can prove it, I now think that was a bit strong. My thinking was the following .. if you see Lagarias' work on the 3x+1 semigroup and its inverse, the group's generators can be thought of as an infinitely long Fractran program which takes any integer as an input. Add the rule that the program terminates upon reaching a power of $2$ and you have a turing-complete machine that stops for all inputs only if the Collatz conjecture is true. Lagarias proves the semigroup generates every integer so it generates every prime... – it's a hire car baby Nov 02 '18 at 17:38
  • ...now I had some argument in mind upon writing that comment that builds upon this idea but I can't bring it to mind again now. – it's a hire car baby Nov 02 '18 at 17:44

1 Answers1

0

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

it's a hire car baby
  • 9,243
  • Please see at my recent answer at https://math.stackexchange.com/a/4351868/1714 which shows another class of numbers $x_0$ which have prime-free (or "composites-only") associated sequences. The first $x_0$ is $x_0=371$. The proof uses primefactorization of the first $6$ $x_k$ but does not give a more common algebraical formula for the $x_0$. So it is so far unknown, whether this class of numbers $x_0$ is finite or infinite.The linked answer gives further candidates of prime-free sequences, (the first $x_0=35$) but which are only heuristically tested up to $N=8000$ iterations being primefree. – Gottfried Helms Jan 10 '22 at 14:18
  • @GottfriedHelms thanks, I saw that already. – it's a hire car baby Jan 11 '22 at 09:27
  • Hi samerivertwice ...:-) Yes, I know that. I thought such a comment were good for some casual lurker. Should possibly better have mentioned at the header of my comment... P.s. Only yesterday I've found the earlier comment of Peter in 2018, where he already discovered the "covering-by-small-primes" structure, and namely the number $371$ ... didn't know this when I wrote my small draft... – Gottfried Helms Jan 11 '22 at 11:19