Observations within the (3n+3j)/2i Family

I have already discussed the simplest features of the 3j systems, j>0. Since interesting complications do arise,. but are complicated to demonstrate and/or explain, a separate page about them is presented herewith.

Another instance of the predecessor tree, this time presented as a general tree, arising for j=12, is presented. This example further illustrates the great width and relatively shallow and relatively constant depth of predecessor trees in this family. More particularly, close examination reveals that the number of steps to leaves varies among the the various paths from the root 531441 (312) to leaf nodes (<>0[3]).

While it is true that there must be at least j steps to a leaf in a tree formed for 3j,  it turns out that there are frequently paths with length greater than j.  For example,  in the tree rooted in 9,  the path 9,  189,  123,  79 fails to consume a power of three at its first step so the path has length 3 instead of 2.  In the same tree,  the path 9,  45,  27,  15,  7 fails to consume a power of 3 in its first 2 steps,  resulting in a path length of 4 instead of 2.

There is a spectacular example of a lengthy sequence of steps which keep a constant power of 3 as the steps progress.  The example was discovered at 103 during the scan of the integers from 1 to 201 for (3n+32)/2i for convergence to the root.  As mentioned elsewhere,  this simple scan served to make a preliminary separation between Collatz-like and Collatz-unlike behavior, and no untoward behavior was found.

The spectacular path in the  (3n+9)/2i predecessor tree has a leaf node (103) and its two successors  (159,  243) at the bottom and reaches 45 and 9 at the root,  with 40 steps between which leave the power of 3 in the c part of the dn+c set representation untouched.  I have factored 9 out of all the c values in the following table to make the numbers easier to see and to make it plain that the same power of 3 remains in the c values for this whole part of the trajectory.  The 5*9 at the top represents 45  (just short of the root)  and the 27*9 at the bottom represents 243,  two steps  (each of which does consume a power of 3)  up from the leaf node for this path.

From this discovery as a starting point, more detail was obtained from MapleV4 by having it solve the set of simultaneous equations shown in the left column followed by extensive reordering,  reformatting,  and additional processing.  MapleV4 gave the results in the central column,  from which the large coefficients were extracted and factored,  again using MapleV4.  The factors of the large coefficients are shown in the last column.  The decrement in the power of 3 in d at every stage combined with the increment in the power of 2 which agrees with the value of i in the 2i part of the defining iteration is familiar from the experience with (3n+1)/2i.  It is evident that this path recurs at extremely large intervals.

Remarkably, this itinerary, with the factor 9 removed from the c term starting at 243, the third element of the successor sequence starting from 103, is precisely the itinerary from 27 to 1 in the (3n+1)/2i case.

 isolve(setx3p2);
                                                                       40
setx3p2:={           { n0=   5*9+  12157665459056928801_N1,         (3)
                                                                  5    39
n1=(32*n0-1)/3,        n1=  53*9+ 129681764896607240544_N1,    (2)  (3)
                                                                  6    38
n2=(2*n1-1)/3,         n2=  35*9+  86454509931071493696_N1,    (2)  (3)
                                                                  7    37
n3=(2*n2-1)/3,         n3=  23*9+  57636339954047662464_N1,    (2)  (3)
                                                                 10    36
n4=(8*n3-1)/3,         n4=  61*9+ 153696906544127099904_N1,   (2)   (3)
                                                                 14    35
n5=(16*n4-1)/3,        n5= 325*9+ 819716834902011199488_N1,   (2)   (3)
                                                                 16    34
n6=(4*n5-1)/3,         n6= 433*9+1092955779869348265984_N1,   (2)   (3)
                                                                 18    33
n7=(4*n6-1)/3,         n7= 577*9+1457274373159131021312_N1,   (2)   (3)
                                                                 22    32
n8=(16*n7-1)/3,        n8=3077*9+7772129990182032113664_N1,   (2)   (3)
                                                                 23    31
n9=(2*n8-1)/3,         n9=2051*9+5181419993454688075776_N1,   (2)   (3)
                                                                 24    30
n10=(2*n9-1)/3,       n10=1367*9+3454279995636458717184_N1,   (2)   (3)
                                                                 25    29
n11=(2*n10-1)/3,      n11= 911*9+2302853330424305811456_N1,   (2)   (3)
                                                                 28    28
n12=(8*n11-1)/3,      n12=2429*9+6140942214464815497216_N1,   (2)   (3)
                                                                 29    27
n13=(2*n12-1)/3,      n13=1619*9+4093961476309876998144_N1,   (2)   (3)
                                                                 30    26
n14=(2*n13-1)/3,      n14=1079*9+2729307650873251332096_N1,   (2)   (3)
                                                                 31    25
n15=(2*n14-1)/3,      n15= 719*9+1819538433915500888064_N1,   (2)   (3)
                                                                 32    24
n16=(2*n15-1)/3,      n16= 479*9+1213025622610333925376_N1,   (2)   (3)
                                                                 33    23
n17=(2*n16-1)/3,      n17= 319*9+ 808683748406889283584_N1,   (2)   (3)
                                                                 35    22
n18=(4*n17-1)/3,      n18= 425*9+1078244997875852378112_N1,   (2)   (3)
                                                                 36    21
n19=(2*n18-1)/3,      n19= 283*9+ 718829998583901585408_N1,   (2)   (3)
                                                                 38    20
n20=(4*n19-1)/3,      n20= 377*9+ 958439998111868780544_N1,   (2)   (3)
                                                                 39    19
n21=(2*n20-1)/3,      n21= 251*9+ 638959998741245853696_N1,   (2)   (3)
                                                                 40    18
n22=(2*n21-1)/3,      n22= 167*9+ 425973332494163902464_N1,   (2)   (3)
                                                                 43    17
n23=(8*n22-1)/3,      n23= 445*9+1135928886651103739904_N1,   (2)   (3)
                                                                 45    16
n24=(4*n23-1)/3,      n24= 593*9+1514571848868138319872_N1,   (2)   (3)
                                                                 46    15
n25=(2*n24-1)/3,      n25= 395*9+1009714565912092213248_N1,   (2)   (3)
                                                                 47    14
n26=(2*n25-1)/3,      n26= 263*9+ 673143043941394808832_N1,   (2)   (3)
                                                                 48    13
n27=(2*n26-1)/3,      n27= 175*9+ 448762029294263205888_N1,   (2)   (3)
                                                                 50    12
n28=(4*n27-1)/3,      n28= 233*9+ 598349372392350941184_N1,   (2)   (3)
                                                                 51    11
n29=(2*n28-1)/3,      n29= 155*9+ 398899581594900627456_N1,   (2)   (3)
                                                                 52    10
n30=(2*n29-1)/3,      n30= 103*9+ 265933054396600418304_N1,    (2)   (3)
                                                                  54    9
n31=(4*n30-1)/3,      n31= 137*9+ 354577405862133891072_N1,    (2)   (3)
                                                                  55    8
n32=(2*n31-1)/3,      n32=  91*9+ 236384937241422594048_N1,    (2)   (3)
                                                                  57    7
n33=(4*n32-1)/3,      n33= 121*9+ 315179916321896792064_N1,    (2)   (3)
                                                                  59    6
n34=(4*n33-1)/3,      n34= 161*9+ 420239888429195722752_N1,    (2)   (3)
                                                                  60    5
n35=(2*n34-1)/3,      n35= 107*9+ 280159925619463815168_N1,    (2)   (3)
                                                                  61    4
n36=(2*n35-1)/3,      n36=  71*9+ 186773283746309210112_N1     (2)   (3)
                                                                  62    3
n37=(2*n36-1)/3,      n37=  47*9+ 124515522497539473408_N1,    (2)   (3)
                                                                  63    2
n38=(2*n37-1)/3,      n38=  31*9+  83010348331692982272_N1,    (2)   (3)
                                                                  65
n39=(4*n38-1)/3,      n39=  41*9+ 110680464442257309696_N1,    (2)   (3)
                                                                  66
n40=(2*n39-1)/3       n40=  27*9+  73786976294838206464_N1,    (2)

};                   }

This close parallel of the paths between (3n+1)/2^i and (3n+9)/2^i, differing only in that the factor of 9 is found in the value of c at each stage extends to (3n+3)/2^i,  (3n+27)/2^i,  (3n+81)/2^i,  and  (3n+243)/2^i.   In the dn+c descriptor of the sets of integers reached,  in each case,  the c value contains the factor equal to 3^j of the  (3n+3^j)/2^i,  while the d value remains constant across j at every level of descent in the predecessor path.  The number of additional descent steps beyond the 40th differs from one another across the value of j before a leaf node is reached.  See below for further details.

The remarkable reversal of roles between 0[3] nodes on the one hand and 1[3] and 2[3] nodes on the other hand is evident here.  In  (3n+1)/2^i the former are leaf nodes and the latter internal nodes in the path,  but in the j>0 instances the 0[3] nodes are internal and the leaf nodes are either 1[3] or 2[3].

This being so, paths in (3n+3^j)/2^i itineraries closely parallel to paths in the (3n+1)/2^i appear to occur for every integer in 0[3], i.e. from every leaf of the predecessor tree for (3n+1)/2^i.  I've checked relatively few,  of course,  but it isn't hard to show that this must be true in general.

One could build an inductive proof that a step which exists in the predecessor tree for any integer an+b for the Collatz sequence based on   (3n+3^j)/2^i must have a parallel step in 3n+3^(j+1)/2^i.

(a) Applying the first to an+b results in (3an+b)+3^j)/2.
(b) Applying the second to 3an+3b results in   (3(3an+b)+3^(j+1))/2, which is the same as 3(3(an+b)+3^i)/2 after factoring out the 3's.
(c) Thus,  generally,  piling on a factor of three produces exactly parallel paths  (may I say homologous paths?)  in the itineraries where j>1 analogous to the original Collatz itineraries where j=0.
(d) Since the l.d.a.s define important components of paths in the j=1 itineraries,  we may conclude that homologues of l.d.a.s must appear in the predecessor trees for j>1.

The 0[3] nodes are internal in the (3n+3^j)/2^i, for the j>0 cases,  so each must have a further few nodes below it in the predecessor tree to reach a leaf node in the (3n+3^j)/2^i analog.  Thus,  the main bodies  (so to speak, composed entirely of 0[3] nodes)  of the series of 3^j predecessor trees are homologous,  differing in the values of c and d of the dn+c formulation by successive multiples of 3 as j is increased by 1 through the series of analogs.  The question is where and how do all the odd 1[3] and 2[3] nodes attach in these homologous predecessor trees.  The answer for j=1 is that they show up in the extensions  (right descents)   from each node of a left descent and,   for j>1,  the leaf nodes which terminate every left descent.

For j>1, additional integers appear as tails leading to leaf nodes from that value which was the leaf node at j=0 (times 3^j) to terminate each left descent.  The elements in these tails are often (but not always) in {0[3] AND 5[8]},   thus drawing on the reservoir of values which in the j=0 case are the headers of null l.d.a.s.   The following table shows the series of tails below 27 and its multiples of 3 in the family of predecessor trees.

j=  0    1     2    3     4     5      6      7       8       9       10       11
   27   81   243  729  2189  6561  19683  59049  177147  531421  1594323  4782969
        53   159  477  1431  4293  12879  38637  115911  347733  1043199  3129597
             103  309   927  2781   8343  25029   75087  225261   675783  2027349
                  197   591  1773   5319  15957   47871  143613   430839  1292517
                        367  1101   3303   9909   29727   89181   267543   802529
                              653   1959   5877   17631   52893   158679   476037
                                    1063   3189    9567   28701    86103   258309
                                           1397    4191   12573    37719   113157
                                                    607    1821     5463    16389
                                                          -5347   -16041   -48123
      5[8] 7[8]  5[8]  7[8]  5[8]   7[8]   5[8]    7[8]    5[8]     7[8]     5[8]

The relationship between entries in one column and those displaced downward by one in the next column is n*2-3^j.  E.g.,  81*2-3 gives 159 and 103*2-9 gives 197.  The bottom row contains the values modulo 8 of the internal elements in each column in the path to the leaf.  Half of the columns seem to use numbers from the set of headers of null l.d.a.s.

The entries in columns j>0 remain in 0[3] until the leaf is reached,   where values in 1[3] or 2[3] are found.   For j>=9,  negative numbers are encountered before the expected leaf nodes are reached.   I don't know what to make of that. .



My Collatz Home Page        Index to Terms Used