Behavior of Powers of 2 and 3 in (2^a*3^b*n+c)/2^i in Extended Paths

We have shown that l.d.a.s are the recurring structural feature which appears in the binary version of the Collatz predecessor tree.  Using the abstract version of the Collatz predecessor tree we have an indication that every odd positive integer appears in the predecessor tree (see a picture also).  By developing unique formulas as descriptors for every element of each infinite set which constitutes the nodes in the l.d.a.s,  using a two-stage,  downward and upward process,  we have shown that every such set is disjoint with every other such set.  We have shown that there are no loops  (other than the trivial one which appears at the root node)  in the predecessor graph.  The extensions serve to provide a path from the terminus  (i.e. root)  of an l.d.a. to some point in a subsequent l.d.a. during the Collatz itinerary,  thus providing the "glue" which links a series of  l.d.a.s into the complete itinerary from any given integer to the root at 1.  We have provided an algorithm by which any odd positive integer may be located in the abstract tree as to its l.d.a.,  its element within its l.d.a.,  and the instantiation of the l.d.a.

With that amount of equipment at hand,  it surely seems that the proof of the Collatz 3n+1 conjecture cannot be far away.  The following paragraphs represent my attempt to adapt Joseph Parranto's ideas into my framework.

The characterization of the contents of each element of the  l.d.a.s has been expressed in two equivalent ways,  as dn+c and as c[d],  both indicating that the members of the set are congruent to c modulo d.  It developed that d is always a product of powers of 2 and 3,  i.e.  2^a*3^b.  A list in this form of the contents of a complete l.d.a. is spectacular for long l.d.a.s,  e.g.  that for the descent to 27.   The values of d in the successive steps of any path can be written by inspection.  When building l.d.a.s from root down through the predecessors,  the values of c need to be developed laboriously by downward and upward processing.  However,  when examining known paths from leaves,  the values of c   (or their integer multiples if the instantiation is one with n>0)  are right at hand, occurring as the successive values reached in the itinerary.  

But there is no reason that the c[d] notation be restrained to indicate the progression of set contents within an l.d.a.  It could just as easily be applied to any path or segment of a path,  even those starting within an l.d.a. or progressing across several extensions and portions of   (or entire)  l.d.a.s before reaching the root.   All that needs to be done is to start at the proximal end of the path  (i.e. that nearer the root)  with a d value containing the product of a low power of 2 (a) and a power of 3 (b) equal to the number of steps in the path   (counting steps between successive odd integers only),  then add to a at each stage the value of  i   (from (3n+1)/2^i)  utilized in that step and subtract 1 from the value of b.  The values of c are the values (modulo d, always) observed in the itinerary at each stage. 

The point to note is that in paths from leaf nodes to the root,  the power of 2 in the d value decreases by 1 for every division by 2 applied in the Collatz iteration.  The power of 2 in d therefore is a reliable measure of the progress toward the root.

This is far from surprising.  After all,  the formula for developing the Collatz predecessor,  applied step by step, results in increasing the power of 2 by i and decreasing the power of 3 by 1 each time.  Whether i is <=2  (as within l.d.a.s)  or >=3   (as in steps involving extensions)  the formula applies,  and the above described behavior of the exponents must result.

The behavior of the successors of any given l.d.a.  (or larger, arbitrary, portion of a path)  differs from one of its instantiations to another.  This differing behavior is simply a result of the fact that the value of the header (extension) reached differs for each instantiation.   Since every integer has its own unique path to the root,  the several instantiations of l.d.a.s must be connected to the root by differing paths.

Let us illustrate this behavior using the complete path of the first instantiation of the  'ebbt'  l.d.a.  (whose leaf node appears at 321).   The following table shows in column one the number of divisions by 2 to reach the c in each line from the c in the line below.  The second column is produced by the recipe used for assigning a and b values for the elements of  l.d.a.s and the third column is the numeric value for the resulting d value.   The remaining columns are the complete instantiations for successive occurrences of the path segment which was suggested by the complete path from 321.

       complete path                         paths instantiated:
     as extended from                complete for n=0, but terminated for
     first ebbt l.d.a                n>0 at the length completing n=0 path
     (dn+c at n=0)                   ---------------------------------------
    ---------------------            _________values at shown n's___________
                            d as        c
  step    d as powers      number   i.e.n=0     n=1         n=2         n=3
    4       2^0*3^7         729         1       729        1459        2917
    3       2^4*3^6        3888         5      3893        7781       15557
    b       2^7*3^5       10368        13     10381       20749       41485
    5       2^9*3^4       13824        17     13841       27665       55313
    b      2^14*3^3      147456       181    147637      295093      690005
    b      2^16*3^2      196608       241    196849      393457      786673
    t      2^18*3^1      262144       321    262465      524609     1048897

To make sense of that you probably need to use your pocket calculator to follow both the original  'ebbt'  path to the root and then the successive instantiations of the complete path.  Note that the  'ebbt'   parts of the paths extend only up through the bottom four lines of the table,  though the entire paths as instantiated use all the lines of the table.   Note that the number of divisions by 2 at each step is in lock step across the four 'values' columns, thus demonstrating that the paths other than those identified as l.d.a.s can be shown to replicate via the dn+c formula to indefinitely large numbers.  Since the upward end of these paths have different values, you can expect that the rest of the paths to the root  (other than that of the column for n=0, of course, which is already at the root)  will differ from one another.

When one sees that any path may be described by a series of formulas in which the power of 2 decreases and the power of 3 increases in the value of d as the path proceeds to the root,  one better appreciates the nature of the directionality in the Collatz trajectories.   The directed nature of the edges in the Collatz graph has already been mentioned.   These two points of view concur in establishing a constant directionality   (upward in the general predecessor tree)  for all the steps in a trajectory.  It follows that a tree is the only graph structure which can be formed and,  since a tree is a weakly connected graph,   that the Collatz conjecture is proven (see Lagarias). .


My Collatz Home Page        Index to Terms Used