Locating an Arbitrary Integer in the Abstract Generation Tree

We claim that a predecessor tree reaches every odd integer in a unique manner so that one can safely "count" the integers reached and conclude that the predecessor tree does indeed span all the odd integers and thus prove the Collatz conjecture.  This claim invites development of a way of characterizing each odd integer in terms of its position in the abstract predecessor tree.  Certainly,  the position of any integer in the general tree form of the predecessor tree can be determined by running the Collatz trajectory back to one,  building the alphanumeric string which represents that total path from right to left as the trajectory is traversed,  as was done for several 'ebbt' examples.  This alternative seems unattractive because it capitalizes in no way upon the insights offered in the abstract predecessor tree,  and the resulting full-length alphanumeric strings obscure the insight about the systematic recurrence of left descents in the binary predecessor tree.  The method for placing any odd integer in the abstract predecessor tree offers some help in the proof of the Collatz conjecture by emphasizing the details of the process by which leaf nodes in the abstract predecessor tree are related back to subsets of the sets in the tree.  Ultimately,  this back mapping from leaf node sets to higher sets internal to the tree might provide the basis for showing that the tree is greedy,  i.e.  that all odd integers are reached by it.

An example will be given after the algorithm is presented.

Starting with an arbitrary odd integer,  o:

(1)  Determine whether it is an extension.  If o is congruent to 5 mod 8,  o is an extension,  e.  If the extension is a leaf (congruent to 0 mod 3),  we can solve the equation o=24n+21 for n and characterize o by saying that it represents the nth instance of a leaf node among right "extended" descents,  completing its characterization.  Otherwise,  proceed to (3).

(2)  Determine the left descent path upwards from o to the first right descent element encountered.  Using 3n+1 and divisions by 2,  follow the Collatz trajectory as long as only 1 or 2 divisions by 2 suffice to reach each parental odd number.  The last number before more than one or two divisions by 2 is the extension element,  e,  parental to the left descent in which o appears.

(3)  Work downwards to determine the complete left descent from e to its terminating leaf node in three parallel notations,  terminating with a leaf node in which T(k)  is congruent to zero mod 3.

(a)  (numeric formulation)  Using the recursive formula T(k):=(-1+T(k-1)*2^p(k))/3 with p(k)=1 when T(k-1)  is congruent to 2 mod 3 and p(k)=2 when T(k-1)  is congruent to 1 mod 3,  calculate each left child in turn.  This left descent will recreate in reverse order all the values visited in step (2),  o itself,  and any/all the further elements in the left descent from the parental extension element.  Call the element at which the odd integer o is reached the ith element.

(b)  (algebraic formulation)  Starting with the appropriate algebraic descriptor for the appropriate subset of the parental extension,  24n+5 (if e mod 3 is congruent to 2)  or 24n+13 (if e mod 3 is congruent to 1),  determine the algebraic expression for the generated subset at the next level of the abstract predecessor tree.  Continue subsetting and child generation as required.  This process was illustrated in a little more detail in Figure 5.

(c)  (string notation)  Starting with 'e' to indicate the departure from an extension,  append an 's' for a step where p(k)=1 was used in step (3a)  or a 'b' for a step in which p(k)=2 was used in step (3a).  When the leaf node is reached,  append 't' to the string to indicate termination of the left descent.

(4)  Work upwards to determine the subsets at each parental level which were destined to constitute the sets of instances of the entire left descent.  This process was illustrated in a little more detail in Figure 6.

(5)  Determine which instance of the left descent subsets o is a member of.  Any one of the expressions in step 4 when equated to the corresponding numeric value from step 2 (or 3a)  may be solved for n.  Solve for n.

We can now say that o is the ith element in the nth instance of the left descent represented by the string produced in step (3c).  That representation is the full extent of the characterization made possible by the current gestalt.

As an example,  let's work with 18839.  The first column was worked out upwards from the o value,  18839.  The upward pursuit stops when 6 divisions by 2 arise to reach 1987.  The extension value,  42389,  is moved to column 2 to head the descent calculation.  The second through sixth columns were worked out downward; column 3 denotes the value of column 2 mod 3 and column 4 the contribution to the accumulating string occasioned by each step.  The entire left descent comes to an 'esssbst' one.  Column 6 gives the algebraic formulas which describe the set membership of the successive child sets in the path in the abstract predecessor tree,  i.e.  the 'e' set,  then the 'es' set,  then the 'ess' set,  etc.  The correct subsets of the sets of column 6 are employed in the expression in the next line in column 5 to get to the next generation according as the left descent must be an 's' or a 'b' step as determined by the value of the parent mod 3.  The last entry in column 5 results from simply a subset choice,  without applying the recursive formula,  because it is a leaf node.  Finally,  column 7 is constructed in an upwards direction by applying the Collatz trajectory rules to the column 7 sets of the line below.  The formula for the leaf node is copied into the bottom of column 7 for use in the upwards traversal of the path in the abstract predecessor tree.

Solving any equation formed from columns 2 and 7 gives n=7.  Thus we can say that 18839 is the seventh instance of the third element of the 'esssbst' left descent subsets in the abstract predecessor tree.  All the items in column 2 are the respective elements of the seventh instance of that left descent subset in the abstract predecessor tree.  That is as much as we can say without running the whole Collatz trajectory to place the seventh instance of this particular left descent in the overall predecessor tree.

Note that the steps of the algorithm can be applied to any odd integer,  no matter how large it may be,  since they involve only simple arithmetic operations.  This simple observation serves to make this identification procedure applicable to all odd positive integers.



My Collatz Home Page         Index to Terms Used