Development of Formulas Characterizing Every Left Descent Node

We can iteratively work out what expression describes the fate in the abstract predecessor tree of the elements of any node's set.  Some elements are leaves,  and the rest give smaller descendants or bigger descendants.

This process will be illustrated in considerable detail with specific examples.  We concentrate especially near the root of the abstract predecessor tree because we must necessarily start there to develop descriptions throughout the tree.  Of course,  the procedure can be applied at any level of the abstract predecessor tree.

Let's create a table to demonstrate development of the algebraic description of the elements of the sets in the predecessor tree.  As the tree grows through its generations each set (though always denumerably infinite)  represents "one-third the number" of integers its parent represented.  (We'll get more precise later about the "numbers" of integers in each set by determining the density of the integers each set represents.)

The sets resulting from a series of such steps may be briefly represented by a concatenation of s and b representing the steps traversed to reach them (as was done in the schematic of the abstract tree),  prefixed by an e to indicate that the point of departure was the extension set.  Starting from {8n+5} (or any nested parental set reached by iteration),  each set must be split into 3 subsets to discern which fall into {0,  1,  or 2} modulo 3.  Examination of any parental set shows that its members are equally in {0 mod 3},  {1 mod 3},  and {2 mod 3} and further that every third element in the parental set falls into a particular one of those subsets of children.  Thus the subdivision may be accomplished by multiplying the starting coefficient by 3 and adding 0,  1,  or 2 times the original coefficient to the original constant value to get three subsets each sharing a common value mod 3.  Which subset it falls into is determined entirely by the constant,  since the coefficient on n is always a multiple of 3.  (We just multiplied by 3 to get the three subsets.)  The constant in every expression developed in this way is necessarily smaller than the coefficient.  Each subset is treated appropriately in response to the value of its elements mod 3,  resulting in two descendant sets which will be parental in the next generation and a set of leaves terminating the current left descent.  All integers n congruent to 2 mod 3 have smaller children than their parents in the abstract predecessor tree in the s-direction with a value (2n-1)/3.  All integers n congruent to 1 mod 3 have bigger children than their parents in the predecessor tree in the b-direction with a value (4n-1)/3.  The members of the descendant sets are just the collection of individual integers which were segregated by these rules.  Each resulting set of non-leaves in turn is treated.

The table entries are developed only through three levels of growth,  corresponding to the depth in the schematic of the abstract tree.  The prefixed e is included in the set names to indicate that the envisioned root is a member of the extended set of parents of left descents; an sss sequence not rooted in the e set will be a superset (16n+15)  of that developed here for the esss sequence (64n+15).

This last is a partial example of an important general point.  The families of left descents will not be described in sufficient detail to enable all the results presented here if the left descents are not developed in enough detail to be rooted in an extension and terminated by a leaf node.  Without this degree of specificity in locating the left descent in the overall abstract predecessor tree,  the set contents overlap.  With this degree of specificity,  the sets appear to be completely disjoint to one another.

Note that the coefficients in all these expressions describing the contents of the sets are of the form 2^a*3^b.  Since the expressions are not yet in their final form,  we will content ourselves with just this observation for the moment.  A "t" is appended to the name of the paths which terminate by virtue of encountering values congruent to 0 mod 3.  (For those immersed in the history of the 3n+1 problem,  we parenthetically note that the culminating left descent to the infamous 27 is an "ebsssbssbsbbssssbst" descent where the parent is 445.  This illustrates both the power of the notation and the remarkable occurrence of a lengthy path among quite low numbers.)

The process of subsetting parental nodes to elaborate the abstract predecessor tree can be continued indefinitely to arbitrary depths.  The coefficients get larger and the constant terms both grow and fill in occasional spaces left vacant earlier.  The constant term is always smaller than the coefficient.

Now that we have segregated a few illustrative sets of nodes whose left descents are complete,  we may use the information gained to identify which subsets of each level of ancestor it was which were destined to complete each path to termination.  The "leaf set" column in the accompanying (up-directed) table comes from the leaf entries of the previous (down-directed) table,  plus three more obtained in the same way at the next level.  Its successive columns are derived by applying 3n+1 to a preceding column's contents and dividing by 2 or 4.  The coefficients are in factored form now.

The rightmost filled column in each row represents the subsets of the 8n+5 set whose destiny has now been worked out.  The subsets of the intervening sets on the path to the leaf set have been worked out,  as well,  as a useful side effect.  We'll use formulas of the form 2^a*3^b*n+c when the subsets have been completely specified so that the powers of 2 and 3 have been established and the subsets are disjoint.

Two subsets,  defined by d*n+c and d' *n+c' are disjoint iff c and c' are not congruent mod gcd(d,d').  Once again,  I thank Margaret Maxfield for the proof.  Thus,  8n+5 overlaps 24n+5,  24n+13,  and 24n+21 because 5,  13,  and 21 mod 8 are all 5.  But 48n+3 and 24n+21 are disjoint because 3 and 21 are distinct mod 24.  And 48n+3 and 768n+33 and 768n+39 are disjoint because 3,  33,  and 39 are distinct mod 48.

An Alternative Notation

The downwards stage of development of dn+c formulas to describe every element in every left descent in the abstract predecessor tree involves the formula of the parent,  d'n+c'.  The value of c in the predecessor will be chosen from {{0,1,2}*d'+c'},  which provides the three new cs among which are found the leaf node,  the result of the s-step and the result of the b-step.  We chose to represent the path of an l.d.a. by concatenation of the s's and b's,  ignoring whether each one was formed from 0,  1,  or 2 as the multiplier of d'.  This has seemed like a useful choice.

The alternative would have been to employ '0',  '1',  or '2' as the characters in a string to indicate the multiplier of  d'  used to reach the next level of predecessor.  This choice would reveal a different aspect of the left descent growth.  All l.d.a.s start from 8n+5.  Here are some examples.

   path from 445 to 27      ebsssbssbsbbssssbst
                             100200000000000000
   path from 9229 to 25569  ebsbsbbbbbbsbbsssbbt
                             102021100000000000
   path from 1621 to 5121   ebbbbt
                             11112

The long string of 0's in the first two examples are necessary to keep the values of c in the ultimate leaf node small;  the d' after a few steps is so large that adding it in would give in a large resulting c.  The third example shows that there can be paths composed entirely of non-zeros.


My Collatz Home Page        Index to Terms Used