# A conjecture related to collatz

I will assume that the reader knows the Collatz (3n+1) conjecture.

Terminology: let's say that a natural number $$n$$ is a descendant of $$m$$ if the collatz procedure starting at $$m$$ eventually leads to $$n$$. For example, $$5$$ is a descendant of $$7$$ since the Collatz procedure starting at $$7$$ yields $$7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26\rightarrow 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5$$ In this case, let's also say that $$m$$ is an ancestor of $$n$$. (So $$7$$ is an ancestor of $$5$$.)

Question 1: Is it true that all natural numbers $$n$$ have an ancestor that is a multiple of $$3$$?

Question 2: If Question 1 is non-trivial, does anyone happen to know if it implies the Collatz conjecture? On the other hand, if it is trivial, or at least proven, can they point me to a proof?

Question 3: Assuming the answer to Question 1 is affirmative, can such an ancestor be found by repeatedly applying the "greedy" reverse-collatz function $$g(n) = \begin{cases} \frac{n-1}{3} & n \cong 4\ (\mathrm{mod}\ 6) \\ 2n & n \cong 1, 2,\mathrm{or}\ 5\ (\mathrm{mod}\ 6) \end{cases}$$

I find it interesting to note that, as wonderfully rich as is the topology of the collatz "tree" (whose topology is described by the ancestor/descendant relationship), the topology of the ancestor tree is trivial above any number which is a multiple of 3. (The tree does not branch above multiples of 3.) So an affirmative answer to Question 1 puts some interesting restrictions on the topology of this grand tree.

• Bit confused by the term trivial and non-trivial. We have one term which is an integer $n$, and the last term or terms which is the sum of iterations divided by $3$. The hamming distance or the difference of two power of twos and their sum are multiples of $3$. Q2: Yes, the form i am talking about implies the CC. Q3: Yes, but the function is a bit different, it kinda looks like: $n_ i+\sum_{i=0}^{max}\frac{A_{i-1}-A_i}{3}$ and don't use modulus. You will get this form by substituting the expression into the ancestor argument. Not sure if the subscript $i$ should be there. my notes are messy. May 29 '20 at 18:31
• @OlivierPirson haven't seen anything, but I'm not well-read on collatz. Jun 10 '20 at 18:16

For positive integer $$\ m\$$ , we need a positive integer $$\ n>m\$$ with $$\ 3\mid n\$$, such that the collatz-sequence beginning with $$\ n\$$ contains $$\ m\$$.

• If $$\ 3\mid m\$$ , $$\ n=2m\$$ does the job.
• If $$\ 3\nmid m\$$ , there exists positive integer $$\ s\$$ with $$\ 2^s\cdot m\equiv 1\mod 9\$$ Then, define $$\ n:=\frac{2^s\cdot m-1}{3}\$$. Since there are infinite many possible $$\ s\$$, we can choose $$\ s\$$ in the way that $$\ n>m\$$, also $$\ n\$$ is a multiple of $$\ 3\$$. Then, the collatz sequence obviously arrives at $$\ m\$$

So, question $$1$$ can be answered with "yes".

Not sure about question $$3$$

• This solves also question 2: the number of ancestors of any number $\equiv 0 \pmod 3$ is infinite - there are ancestors divisible by 3 and ancestors not divisible by 3. At he moment I think, there is rather no knowledge about the other way round: whether there are infinite threads (backwards-trajectories) of iterative ancestors only of the form not-divisble by 3. (Compare 5x+1 et al, where it is easier to believe that such threads exist). May 29 '20 at 8:50
• @Peter Very nice, we do have $3n + 1 = 2^s \cdot m$, but unfortunately, we do not know that $n$ is odd, so we do not necessarily have the relation $n \rightarrow 2^s m$. Is this a mistake, or am I not seeing something that you saw? May 29 '20 at 22:11
• Edit: I figured it out, thank you! We in fact have $2^s \cdot m \equiv 10 mod 18$. So your claim works out! Upvoting and accepting your answer. Thanks! May 29 '20 at 22:19

Perhaps you like the following overview.
I'll write for a number $$a_1$$ and its smallest ancestor $$a_2$$, which is larger than or equal to $$a_1$$ and is also not divisible by $$3$$.

This can then be thought to be iterated. For instance, beginning at $$a_1=5$$, iterating $$2$$ times gives the following protocol:

values: exponents at 2 along the iteration
a1 a3 : A1 A2
5  17 : 3  2

that means $$5 \to (5 \cdot 2^3-1)/3=13 \to (13 \cdot 2^2 -1 )/3 = 17$$

Here a protocol of the first $$27$$ examples of $$a_1=6 k -1$$ :

a1      a33             |  A1 A2 A3 ... Exponents at 2 ...                                                          A32
-------------------------+-------------------------------------------------------- --------------------------------------+
5    1629567600864557  |  3  2  5  2  4  4  2  3  3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  |
11    1847830689651265  |  3  3  3  4  2  5  4  2  3  3  4  2  2  3  3  3  2  5  4  2  5  2  3  2  3  3  3  3  4  4  2  |
17    5794018136407313  |  5  2  4  4  2  3  3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3  3  |
23      30467312081069  |  3  4  2  2  2  2  5  4  4  2  3  3  2  3  5  2  3  2  3  2  4  2  3  2  3  3  2  2  5  2  2  |
29    9855097011473413  |  3  3  4  2  5  4  2  3  3  4  2  2  3  3  3  2  5  4  2  5  2  3  2  3  3  3  3  4  4  2  2  |
35   23896770660498613  |  5  2  3  3  3  4  4  4  4  4  4  2  5  2  3  3  4  2  2  2  4  2  2  2  3  2  2  3  4  4  2  |
41     868065190823725  |  3  2  2  2  3  2  2  3  3  2  5  2  3  3  2  4  2  5  2  5  2  5  2  4  4  4  4  2  2  4  2  |
47    8011680485691313  |  3  5  2  2  3  5  4  2  3  3  5  2  2  5  4  2  2  2  3  3  2  4  4  2  3  3  2  2  3  5  4  |
53    4528745657817329  |  5  4  4  2  3  2  2  2  3  5  2  3  3  3  3  2  3  5  2  2  4  2  2  5  4  2  3  4  2  2  5  |
59    5022658183850245  |  3  2  3  5  2  2  2  3  2  4  2  2  3  3  4  4  2  4  2  4  4  4  2  3  4  2  2  4  4  4  2  |
65    1385166667016593  |  3  3  3  3  2  2  3  5  2  5  4  2  4  4  4  2  3  3  2  4  2  3  3  2  4  2  2  3  4  2  3  |
71     757921508018869  |  5  2  2  2  3  3  3  2  3  4  4  4  2  3  3  5  4  2  2  2  3  3  2  5  2  2  2  4  2  2  2  |
77   13140129348631217  |  3  4  2  5  4  2  3  3  4  2  2  3  3  3  2  5  4  2  5  2  3  2  3  3  3  3  4  4  2  2  4  |
83    1769460185153089  |  3  3  2  3  3  2  4  2  3  5  4  2  3  4  2  5  2  4  2  2  5  2  4  2  3  3  3  3  2  4  2  |
89   15209936237556805  |  5  2  3  4  4  2  2  3  3  2  2  3  2  5  2  3  2  2  4  4  4  4  2  3  5  2  2  5  2  3  3  |
95    1012199105165357  |  3  2  2  5  2  2  5  2  3  2  3  5  2  4  4  4  4  2  3  4  2  2  2  3  3  3  3  2  3  3  2  |
101    4312339992160045  |  3  5  4  2  4  2  3  3  2  5  2  2  3  3  4  2  5  2  2  3  3  3  4  4  2  2  3  3  2  4  2  |
107  146334932561525941  |  5  4  2  2  5  2  2  3  3  4  2  3  5  2  3  3  2  3  4  2  3  4  4  2  3  3  3  3  4  4  2  |
113   38559608325447409  |  3  2  3  4  2  3  2  4  4  2  4  4  2  2  3  2  5  2  3  3  3  5  2  5  2  2  5  4  2  3  5  |
119   10160472862670533  |  3  3  5  2  3  3  4  4  2  5  2  2  4  2  2  2  2  4  2  4  4  4  2  2  2  3  2  3  2  5  4  |
125   10682240647588417  |  5  2  2  3  5  4  2  3  3  5  2  2  5  4  2  2  2  3  3  2  4  4  2  3  3  2  2  3  5  4  2  |
131   89511465278846773  |  3  4  4  4  2  5  4  2  2  3  3  2  2  5  2  4  4  2  2  3  4  2  5  2  2  2  3  3  5  2  3  |
137    2922724885389493  |  3  3  2  2  2  2  2  3  5  2  2  4  4  2  2  4  2  5  2  4  2  4  4  4  2  5  2  2  3  3  2  |
143   97785619677512965  |  5  2  5  2  3  4  2  3  3  3  3  2  2  2  4  2  3  5  2  5  2  4  2  3  2  5  2  5  2  5  2  |
149    1589973825711857  |  3  2  4  2  5  2  3  3  4  2  3  3  3  5  2  3  3  2  3  3  2  3  3  3  2  4  2  2  3  3  5  |
155    6620575296987905  |  3  5  2  3  2  2  2  3  4  2  2  3  2  2  5  2  5  2  5  2  4  4  4  2  4  4  2  4  4  2  2  |
-                   -  +  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  +

and here the same for $$a_1 = 6 k +1$$

a1      a33             |  A1 A2 A3 ... Exponents at 2 ...                                                          A32
-------------------------+-------------------------------------------------------- --------------------------------------+
7     292183593823813  |  4  2  2  3  3  3  3  2  2  3  5  2  5  4  2  4  4  4  2  3  3  2  4  2  3  3  2  4  2  2  3  |
13    4345513602305485  |  2  5  2  4  4  2  3  3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3  |
19     399563157372085  |  2  4  4  4  2  2  4  4  2  5  2  2  4  2  2  3  2  3  3  3  3  2  3  3  2  2  3  3  4  4  2  |
25     532750876496113  |  4  4  4  2  2  4  4  2  5  2  2  4  2  2  3  2  3  3  3  3  2  3  3  2  2  3  3  4  4  2  5  |
31     325524446558897  |  2  3  2  2  2  3  2  2  3  3  2  5  2  3  3  2  4  2  5  2  5  2  5  2  4  4  4  4  2  2  4  |
37     389578125098417  |  2  2  3  3  3  3  2  2  3  5  2  5  4  2  4  4  4  2  3  3  2  4  2  3  3  2  4  2  2  3  4  |
43   14667849204846277  |  4  2  5  2  5  2  2  5  4  2  2  3  5  4  2  2  2  2  3  2  4  2  3  2  2  3  4  2  5  4  4  |
49    1038875000262445  |  2  3  3  3  3  2  2  3  5  2  5  4  2  4  4  4  2  3  3  2  4  2  3  3  2  4  2  2  3  4  2  |
55      72788213540101  |  2  2  4  2  3  2  2  4  4  4  2  5  2  3  2  2  3  2  3  2  2  2  5  2  3  4  2  2  3  5  2  |
61      81246165549517  |  4  2  2  2  2  5  4  4  2  3  3  2  3  5  2  3  2  3  2  4  2  3  2  3  3  2  2  5  2  2  3  |
67    2851863044541901  |  2  5  2  3  4  4  2  2  3  3  2  2  3  2  5  2  3  2  2  4  4  4  4  2  3  5  2  2  5  2  3  |
73      97050951386801  |  2  4  2  3  2  2  4  4  4  2  5  2  3  2  2  3  2  3  2  2  2  5  2  3  4  2  2  3  5  2  4  |
79  863744967943647473  |  4  4  2  3  4  2  5  4  4  2  4  2  2  2  5  2  2  5  2  3  5  4  2  3  4  4  2  3  5  2  5  |
85   28919706244085557  |  2  3  2  3  4  2  3  2  4  4  2  4  4  2  2  3  2  5  2  3  3  3  5  2  5  2  2  5  4  2  3  |
91     967757600546545  |  2  2  5  4  2  3  2  3  5  2  3  4  2  3  5  4  2  3  2  4  4  2  3  3  2  2  2  2  2  3  5  |
97    1035210148125877  |  4  2  3  2  2  4  4  4  2  5  2  3  2  2  3  2  3  2  2  2  5  2  3  4  2  2  3  5  2  4  2  |
103     274005458005265  |  2  3  3  2  2  2  2  2  3  5  2  2  4  4  2  2  4  2  5  2  4  2  4  4  4  2  5  2  2  3  3  |
109    4629681017726533  |  2  2  2  3  2  2  3  3  2  5  2  3  3  2  4  2  5  2  5  2  5  2  4  4  4  4  2  2  4  2  3  |
115     613915116385969  |  4  2  4  2  2  3  4  4  2  3  3  3  2  3  2  2  3  2  2  3  5  2  4  4  2  3  2  4  4  2  4  |
121    1290343467395393  |  2  5  4  2  3  2  3  5  2  3  4  2  3  5  4  2  3  2  4  4  2  3  3  2  2  2  2  2  3  5  2  |
127  173264499591143213  |  2  4  2  2  5  2  5  2  3  2  4  2  5  2  3  2  4  4  2  5  2  3  3  3  4  4  2  5  4  4  2  |
133     710334501994817  |  4  4  2  2  4  4  2  5  2  2  4  2  2  3  2  3  3  3  3  2  3  3  2  2  3  3  4  4  2  5  2  |
139   11852812255905349  |  2  3  4  2  2  3  3  2  4  4  2  3  2  2  4  4  4  2  3  4  2  3  4  4  2  5  2  2  5  2  3  |
145   24691632094541509  |  2  2  3  2  2  3  3  2  5  2  3  3  2  4  2  5  2  5  2  5  2  4  4  4  4  2  2  4  2  3  4  |
151   25802620180311985  |  4  2  3  5  4  2  2  2  5  2  2  2  4  4  4  2  5  4  2  3  2  2  2  4  2  3  5  2  2  5  4  |
157    6696877578466993  |  2  3  5  2  2  2  3  2  4  2  2  3  3  4  4  2  4  2  4  4  4  2  3  4  2  2  4  4  4  2  4  |
-                   -  +  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  +

Notes (just some scribbled thoughts, q&d):

• Of course, the vectors of exponents have unbounded length.

• Even if $$a_1$$ is member of a nontrivial cycle, the vector of exponents is not periodic because it cannot contain decreasing subsequences of $$a_k$$ (by design of the routine)

• Most of the $$a_1$$ shown on some row in the protocol occur as $$a_k$$ in an earlier row of the protocol, so the exponents-vectors are usually simply trailing parts of vectors of earlier rows.

• But not all: odd numbers $$a_1$$ which are result of $$(3 a_2+1)/2$$ are not in the trailing part of earlier $$a_1$$ , but as well have infinite exponents-vectors.
• This answers also the question whether all $$a_1$$ not divisible by $$3$$ have infinitely (iterated) ancestors.

• It might be fun to detect patterns in the $$k$$'th columns of exponents $$A_k$$. Of course $$A_1$$ and $$A_2$$ are simple periodics, but I didn't look at this deeper.

My idea of a Pari/GP-script is

{nextexpo(a0,it=1)=my(a1=a0,a2,A,vA); vA=vector(it);
for(k=1,it,
if(a1 % 3 ==1, a2=(4*a1-1)/3);
if(a1 % 3 ==2, a2=(2*a1-1)/3;if(a2<a1,a2=4*a2+1)); \\make sure a2 is >= a1!
if(a2 % 3==0,a2=4*a2+1);    \\ if a3 divisible by 3, exponent must be increased by 2
A = valuation(3*a2+1,2);
vA[k]=A; a1=a2;
);
return(concat([a0,a2],vA));}
\\ now generate protocol
forstep(a1=7,165,6,print(nextexpo(a1,32)))

Added A protocol of the subsequent $$a_k$$ beginning at $$a_1=5$$ shows how the later exponents-vectors are trailing vectors of the earlier ones:

a1      a33             |  A1 A2 A3 ... Exponents at 2 ...                                                             A32
-------------------------+-------------------------------------------------------- --------------------------------------+
5      1629567600864557  3  2  5  2  4  4  2  3  3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3
13      4345513602305485     2  5  2  4  4  2  3  3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3
17      5794018136407313        5  2  4  4  2  3  3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3
181     61802860121678005           2  4  4  2  3  3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3
241    329615253982282693              4  4  2  3  3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3
1285    439487005309710257                 4  2  3  3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3
6853   1171965347492560685                    2  3  3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3
9137  12500963706587313973                       3  3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3
24365  16667951608783085297                          3  3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3
64973  44447870956754894125                             3  3  3  2  5  2  3  4  2  4  4  4  2  4  2  3  4  2  3  2  5  2  3
• Forgive me, but I don't understand the work you did here, though I appreciate your response :) May 29 '20 at 22:13
• Hi @JakeMirra - it is just an illustration of the infiniteness of sequence of ancestors. We begin at $5$, its smallest ancestor greater $5$, having itself an ancestor (by not being divisible by $3$) is $13$. The smallest ancestor of $13$ greater than $13$, having itself an ancestor is $17$. The smallest ancestor of $17$ greater than $17$, having itself an ancestor is $181$ and so on. The condition to ask for the smallest ancestor of $a_k$ larger than $a_k$ itself is to make sure, we get an infinite sequence. After that I just look at the sequence of occuring exponents of $2$. May 30 '20 at 3:56