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*=24*n*+21 for *n* and characterize
*o* by saying that it represents the *n*th 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 3*n*+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 *i*th
element.

(b) (algebraic formulation) Starting with the appropriate algebraic
descriptor for the appropriate subset of the parental extension, 24*n*+5
(if *e* mod 3 is congruent to 2) or 24*n*+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 *i*th element in the *n*th
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