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

2 Answers 2

Reset to default
2
$\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$
    – Gottfried Helms
    Commented May 29, 2020 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
    Commented May 29, 2020 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
    Commented May 29, 2020 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
    Commented May 29, 2020 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$
    – Gottfried Helms
    Commented May 30, 2020 at 3:56

You must log in to answer this question.

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