4
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ +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 ... $\endgroup$
    – Noah Schweber
    Commented Jun 16, 2017 at 1:01
  • $\begingroup$ 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? $\endgroup$
    – Gottfried Helms
    Commented Jun 16, 2017 at 9:24
  • $\begingroup$ Upps., of course I meant $R(a;A)= { a \cdot 2^A-1 \over 3}$ (I forgot the $a$) in the earlier comment. $\endgroup$
    – Gottfried Helms
    Commented Jun 16, 2017 at 15:29
  • $\begingroup$ 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. $\endgroup$
    – Robert Frost
    Commented Jun 16, 2017 at 16:23
  • $\begingroup$ 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? $\endgroup$
    – Robert Frost
    Commented Jun 18, 2017 at 13:43

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Please see at my recent answer at 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. $\endgroup$
    – Gottfried Helms
    Commented Jan 10, 2022 at 14:18
  • $\begingroup$ @GottfriedHelms thanks, I saw that already. $\endgroup$
    – Robert Frost
    Commented Jan 11, 2022 at 9:27
  • $\begingroup$ 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... $\endgroup$
    – Gottfried Helms
    Commented Jan 11, 2022 at 11:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .