Proofs of Some Little Pieces of the Structure

Extensions Grow Recursively via 4n+1

Th.  The right descendant in the binary predecessor tree of an arbitrary odd m is 4m+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*2j)/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^2j*2^2)/3
so m2=(-1+4*n*2^2j)/3
so m2=(-1-4+4*n*2^2j)+4)/3
so m2=4*(-1+n*2^2j)/3+3/3
so m2=4*m1+1.

All Extensions of an Arbitrary n Give the Same Collatz Successor,  3n+1

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

As just shown,  every odd integer,  n gives rise to an infinite series of extensions by recursive application of 4n+1 to its predecessor.  Thus,  4n+1,  4(4n+1)+1,  4(4(4n+1)+1)+1, ...  , or 4n+1,  16n+5,  64n+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 3n,  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 3n+1.

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

                                  1

Left Descendants and Extensions (Right Descendents) Are Disjoint Sets

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

Since every right descendant is derived from an odd parent,  m,  so m=2i+1 and n= 4(2i+1)+1,  or 8i+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+3i,  but m odd,  so i=2j.  From the descendant rules near the top of the gentrees web page, 
n=mb=[-1+4(1+6j)]/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+3i,  but m odd, so i=1+2j.  Then n=ms=[-1+2(5+6j)]/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.

Sets Disjoint iff d and d' Unequal mod gcd(c,c')

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 10n+21 and 6m+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 10n+21 becomes 10*7+21 and 6m+7 becomes 6*14+7,  which are equal.

Leaf, s, and b Sets Disjoint

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. 2i).

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 3dn+c,  3dn+c+d,  and 3dn+c+2d.  The constant term,  c + i*di<=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 2i for each formula.  The third line drops the d*n term which is always a multiple of 2i,  and the fourth line substitutes 2 or 1 for the power of 2 to give the predecessor's value for c mod 2i.  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.

Scaling of path segments among Collatz paths

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 (3n+3*k)/2i analogs,  a somewhat more general family of analogs than that developed herein.


My Collatz Home Page        Index to Terms Used