1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ May 29 '20 at 18:31
  • 1
    $\begingroup$ Do you have some references about this function g? $\endgroup$ Jun 2 '20 at 7:08
  • $\begingroup$ @OlivierPirson haven't seen anything, but I'm not well-read on collatz. $\endgroup$
    – Jake Mirra
    Jun 10 '20 at 18:16
3
$\begingroup$

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$

$\endgroup$
3
  • 2
    $\begingroup$ 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). $\endgroup$ May 29 '20 at 8:50
  • $\begingroup$ @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? $\endgroup$
    – Jake Mirra
    May 29 '20 at 22:11
  • $\begingroup$ 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! $\endgroup$
    – Jake Mirra
    May 29 '20 at 22:19
1
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ Forgive me, but I don't understand the work you did here, though I appreciate your response :) $\endgroup$
    – Jake Mirra
    May 29 '20 at 22:13
  • $\begingroup$ 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$. $\endgroup$ May 30 '20 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.