Th. The right descendant in the binary predecessor tree of an
arbitrary odd *m* is 4*m*+1.

Since adjacent descendants in the general tree become successive
right descent elements in the binary tree, we may consider
*m1* as the smaller, and *m2* as the larger, of
two adjacent descendants of a parental *n* in the general
tree. Since two successive descendants arise from powers of 2
differing by 2 to maintain evenness/oddness in the exponent, both
cases can be treated together.

With *n* as the parent, using the recursive predecessor
relationship, and *j* as the power of 2 to reach *m1*,
*m1*=(-1+*n**2^{j})/3, the value of the smaller
of two adjacent descendants.

For the larger of the two descendants, *m2*, use *j*+2
as the exponent
*m2*=(-1+*n**2^2(*j*+2))/3

so *m2*=(-1+*n**2^2*j**2^2)/3

so *m2*=(-1+4**n**2^2*j*)/3

so *m2*=(-1-4+4**n**2^2*j*)+4)/3

so *m2*=4*(-1+*n**2^2*j*)/3+3/3

so *m2*=4**m1*+1.

Th. Any odd integer, *n*, and all its extensions, when subjected to the
Collatz process give the same Collatz successor, 3*n*+1.

As just shown, every odd integer, *n* gives rise to an infinite
series of extensions by recursive application of 4*n*+1 to its
predecessor. Thus, 4n+1, 4(4*n*+1)+1,
4(4(4*n*+1)+1)+1, ... , or 4*n*+1, 16*n*+5,
64*n*+21, ... are the first few extensions of *n*.

The form of each extension is 4^(*j*+1)**n*+sum(4^*i*, *i*=0..j). Multiplying the first
term by 3 and dividing by 4^(*j*+1) gives 3*n*, and
multiplying the second term by 3, adding 1, and dividing by 4^(*j*+1) gives 1.
Thus the overall result of the Collatz step is 3*n*+1.

> (3*sum(4**i,i=0..j)+1)/4**(j+1); 1

Every descendant is derived from an odd parent, call it *m*.

Since every right descendant is derived from an odd parent, *m*,
so *m*=2*i*+1 and *n*= 4(2*i*+1)+1, or 8*i*+5, i.e.
congruent to 5 modulo 8.

Th. If *n* is the immediate left descendant of an odd *m*,
then *n* is not an extension. Let *n* be the immediate
left descendant of odd *m*. Then *m* is congruent to 1 or 2
mod 3, since odd numbers congruent to 0 mod 3 are leaves.

Case 1. *m* = 1+3*i*, but *m* odd, so
*i*=2*j*. From the descendant rules near the top of the
gentrees web page,
*n*=*mb*=[-1+4(1+6*j*)]/3=1+8j, congruent to 1 mod
8 and *n* is not an extension. The parent *m* may be an
extension depending on whether *j* is congruent to 2 mod 4.

Case 2. *m* = 2+3*i*, but *m* odd,
so *i*=1+2*j*. Then
*n*=*ms*=[-1+2(5+6*j*)]/3=3+4j, which is
congruent to 3 or 7 mod 8, depending on whether *j* is even
or odd. Then *n* is not an extension. The parent
*m* may be an extension, depending on whether *j* is
congruent to 0 mod 4.

From the contrapositive, an extension is not an immediate left descendant, i.e., no extension appears among left descents in the binary predecessor tree.

Th. Iff the *c*'s of two *dn+c* subsets are not
congruent mod *g*, where *g* is the gcd of the 2 *d*'s,
the two subsets are disjoint.

Suppose *dn+c* and *em+r* coincide at those
choices of *n* and *m*. Then if *d*=*gd'* and
*e*=*ge'*, we have
*c*-*r*=*g*(*em'*-*d'n*) congruent to 0 mod
*g*. This proves the if part of the iff.

{Note for the mathematically challenged: This assumes as hypothesis
that the subsets are NOT disjoint, so that they have a pair of equal
elements: *dn*+*c*=*em*+*r*. From that it follows
that the *c* and *r* constants would be congruent mod
*g*, the gcd of *d* and *e*. Proving such a *p*
implies *q* automatically proves the contrapositive not-p
implies not-q; that is, if *c* and *r* are NOT congruent
mod *g*, then their subsets do NOT overlap, but are disjoint.}

Now to the converse. The hypothesis is that *c* and *r* of
*dn+c* and *em+r* are congruent mod *g*, i.e. that
*g* divides *c-r*. Take the quotient to be *t*,
so that *c*=*r+gt*.

Divide *d* and *e* by their gcd, forming *d'*
and *e'* which are relatively prime, so that their gcd is
1. Their gcd can be expressed linearly as
*ue'*-*vd'*=1, for some integers *u* and *v*.

Now choose those terms in the subsets for which *m*=*ut*
and *n*=*vt*. Those two terms will be equal, so the subsets do
overlap. {The only if is thus established via the contrapositive.}

Ex. Let the two subsets *dn+c* and
*em+r *be 10*n*+21 and 6*m*+7. In this
example, *g*=2 (gcd(10,6)), *t*=7
((21-7)/2), *d'*=5, *e'*=3,
*u*=2, *v*=1 (making *ue'-vd'* into
2*3-1*5=1), whence n=*vt*=7 and
*m*=*ut*=14, so 10*n*+21 becomes 10*7+21 and
6*m*+7 becomes 6*14+7, which are equal.

Th. Given any set *dn+c* in the abstract predecessor
tree, its two children sets and its leaf subset are disjoint with
one another.

We apply the preceding theorem by working out general formulas for
every case of an abstract predecessor tree growth step and the residue
mod the gcd of the three resulting subsets for each different
case. The gcd of the resulting coefficients is d
(i.e. 2^{i}).

In dividing a parental set, characterized as
*dn+c*, into three subsets which will represent (1) a
subset of leaves, (2) a subset parental to s-descendants
and (3) a subset parental to b-descendants, the three subsets
are 3*dn*+*c*, 3*dn*+*c*+*d*, and
3*dn*+*c*+2*d*. The constant term, *c* +
*i***d*, *i*<=2, determines the position taken in the abstract predecessor
tree by each subset.

The following table works out each subset produced in all six
cases, for odd/even *i* and *c*=={0,1,2} mod 3. A
little reminder of the relevant facts precedes the table for easy
reference. The first line indicates the kind of step, the
second line the formula for the result, and the third line the
residue mod 2^{i} for each formula. The third line
drops the *d***n* term which is always a multiple of
2^{i}, and the fourth line substitutes 2 or 1 for
the power of 2 to give the predecessor's value for c mod
2^{i}. These are distinct from one another for every case
so, by the preceding theorem, the formed sets in each case
are disjoint. ("==" is used to signify congruence.)

2^i == 2 for odd i 2^i == 1 for even i constant term == 2 mod 3 ==> s-step; constant term == 1 mod 3 ==> b-step constant term == 0 mod 3 ==> leaf subset for 3dn+c 3dn+c+d 3dn+c+2d ------------- ----- ------- -------- odd i, c==0 leaf set s-step b-step (result set) 3*2^i*n+c 2^(i+1)*n+(2(c+2^i)-1)/3 2^(i+2)*n+(4*(c+2*2^i)-1)/3 (drop d term) c (2c+2^(i+1)-1)/3 (4c+2^(i+3)-1)/3 (subst 2^i) c 2c/3 4c/3 odd i, c==1 b-step leaf set s-step (result set) 2^(i+2)*n+(4c-1)/3 3*2^i*n+c+2^i 2^(i+1)*n+(2*(c+2*2^i)-1)/3 (drop d term) (4c-1)/3 c+2^i (2c+2^(i+2)-1)/3 (subst 2^i) (4c-1)/3 c+2 (2c+1)/3 odd i, c==2 s-step b-step leaf set (result set) 2^(i+1)*n+(2c-1)/3 2^(i+2)*n+(4(c+2^i)-1)/3 3*2^i*n+c+2*2^i (drop d term) (2c-1)/3 (4c+2^(i+2)-1)/3 c+2^(i+1) (subst 2^i) (2c-1)/3 (4c+1)/3 c+1 even i, c==0 leaf set b-step s-step (result set) 3*2^i*n+c 2^(i+2)*n+(4(c+2^i)-1)/3 2^(i+1)*n+(2*(c+2*2^i)-1)/3 (drop d term) c (4c+2^(i+2)-1)/3 (2c+2^(i+2)-1)/3 (subst 2^i) c 4c/3 2c/3 even i, c==1 b-step s-step leaf set (result set) 2^(i+2)*n+(4c-1)/3 2^(i+1)*n+(2(c+2^i)-1)/3 3*2^i*n+c+2*2^i (drop d term) (4c-1)/3 (2c+2^(i+1)-1)/3 c+2^(i+1) (subst 2^i) (4c-1)/3 (2c+1)/3 c+2 even i, c==2 s-step leaf set b-step (result set) 2^(i+1)*n+(2c-1)/3 3*2^i*n+2+2^i 2^(i+2)*n+(4*(c+2*2^i)-1)/3 (drop d term) (2c-1)/3 c+2^i (4c+2^(i+3)-1)/3 (subst 2^i) (2c-1)/3 c+1 (4c+1)/3

The table contains results which are instructive in understanding why paths with interchanged or certain substituted steps often reach integers closely similar in magnitude.

Some additional pieces of proof have been provided by Alexandre Buisse, to whom I am indebted for much fruitful electronic correspondence.

Electronic communication from Oleg provides
some proofs of the way in which scaling applies to sequences in the
Collatz itinerary to produce parallel sequences in
(3*n*+3**k*)/2^{i} analogs, a somewhat
more general family of analogs than that developed herein.

My Collatz Home Page Index to Terms Used