Diverging Trajectories

Discussion of Cases Where Collatz Trajectories Diverge to Infinity

Although this page discusses (5n+1)/2i, the situation with (5n+3)/2i is closely parallel.

Although state transition diagrams for the predecessor transitions have proved very useful for examining the Collatz 3n+1 conjecture and a number of its immediate analogs,  it does not seem helpful for analogs which diverge to infinity, due to the absence of any predecessor header nodes.  For such cases,  we must deal with successor graphs,  not predecessor graphs. Accordingly,  a state transition diagram for the successor transitions was prepared for the (5n+1)/2i case.

This diagram contains nodes which collect together all the integers sharing a residue modulo 5.  Thus all the leaf nodes (0[5]) from the predecessor graph are collected together as the root node in the successor state transition graph.   Under the header there appear the four kinds of internal nodes in the trajectories,  which,  as it turns out,  form a complete graph among themselves -- every one is connected to every other one with directed edges in both directions.  No leaf nodes appear (as is expected since there were no header nodes in the predecessor version).   Thus,   there can be no termination in trajectories which start from one of the headers.  The trajectories must either terminate in a loop or diverge to infinity.

The state transition diagram is permissive of loops.   In fact,  there are loops  (see below).  The loops do intercept many of the trajectories which start out from 0[5] root nodes.  One wonders whether these intercepting loops might in some way block access to certain odd integers,  so that the family of trees rooted at 0[5] fails to include all the odd positive integers.  One notes that the integers involved in the loops are small, consisting of 1- and 2-digit numbers.  If there were integers whose access from the roots were blocked at least a few of them should be among 2-,  3-,  and 4-digit numbers.

To test this possibility,  a program was written to find the successor of every odd integer from 1 to 5001.  Another program was written to trace 500 steps for every 0[5] integer from 5 to 5005,  checking for the appearance of loops and for convergences with the trajectories from other 0[5] roots.

Not surprisingly in view of the state transition diagram,  every ingteger tested has a successor,  as the diagram indicates they must. But still,  there could be missing predecessors. 

The output from this program was sorted into various orders to enable checking the completeness of coverage of the integers among the predecessors and the successors in this one-edge-at-a-time representation of the successor graph.   If one examines this graph in much the same manner as was done for the abstract predecessor tree defining the l.d.a.s  for the  (3n+1)/2i  case in an effort to determine the densities represented by the integers encountered at each successive generation,  one soon finds that the root  (i=0)  contains 1/5 of the odd numbers,  the i=1 generation contains 4/10 of the odd numbers,  the i=2 generation contains 4/20 of the odd numbers,  the i=3 ,  4/40,  the i=4,  4/80,  etc.,  which starts an infinite process which will sum to 1,  thus accounting for all the odd numbers.  The process seems immutable, and may be expected to continue through higher and higher generations to eventually include the whole infinity of odd positive integers.

Here is a little table showing how the integers get covered for the (5n+1)/2i successor tree.  This information is as close to providing a proof that all odd integers are reached as I have developed.   There seems to be no pattern in the trajectories,  otherwise.

                                Odd Integers,
   i    formula of covered    not yet included   density at ith level
   _    ____________________  __________________ ____________________
   0    10n+5                 {1,3,7,9}[20]         1/5   or .20000
   1    20n+{1,9,13,17}       {3,7,11,19}[20]       4/10  or .40000
   2    40n+{7,23,31,39}      {3,11,19,27}[40]      4/20  or .20000
   3    80n+{11,27,43,59}     {3,19,51,67}[80]      4/40  or .10000
   4   160n+{3,67,99,131}     {19,51,83,147[160]    4/80  or .05000
   5   320n+{19,83,147,211}   {51,179,243,307}[320] 4/160 or .02500
   6   640n+{243,371,499,627} {51,179,307,563}[640] 4/320 or .01250
   . . . .

This is parallel to the process which indicated that the abstract prdecessor tree in the (3n+1)/2i case also contains all the odd numbers.  In the two cases,  the trees are different sides up  (i.e. one is a predecessor-  and the other a successor-tree)  but they share what appears to be a similar compulsion to include all the odd numbers.

The second program revealed what mergers appeared among the various trajectories from 0[5] and what trajectories were intercepted by the loops.  A first run showed that merging trajectories did so well within 200 steps, so a second run covered the 0[5] integers from 5 to 9995 to a depth of 200 steps in the trajectories.  The following little table shows what trajectories (labelled by their root's values) lead into loops for roots from 5 to 5005.

 for the 1-3-1--- loop
        15, 65, 175, 635, 655, 1555, 4065, 4915
 for the 13-33-83-13--- loop
   5, 105, 185, 215, 245, 675, 1005, 1185, 1255, 1285, 1855, 2255, 2265, 2955, 3065,
   4455, 4465
 for the 17-27-43-17--- loop
   275, 435, 945, 2785, 3325

The information from this program detailing the merges between trajectories from pairwise tracing from the roots in 0[5] proved overwhelming,  especially since there was a very high degree of redundancy.  It proved easy to segregate the individual merge instances into sets which merge into a common descent to infinity.   But there were often dozens of initiating 0[5]s in a given tree even though working with a very limited sample,  and constructing a picture of a single such tree proved very time-consuming.  The above lists of roots collecting into the individual loops give some feeling for the sets which congregate,  so it seems useless to detail any of that information here.

Just for a couple extreme examples,  133 steps from 5655,  114 steps from 6125,  and 137 steps from 9265 all merge at 623.  These are the longest combined number of steps found by the program,  and provide examples where the divergence to infinity makes a leisurely start.  The highest numeric value at which merge was observed was 3663203 which comes from 21 steps from 1055 and 15 steps from 8055,  providing examples where fairly quick progress toward large numbers occurred.  One has no way of knowing whether there will be instances of merges after longer paths or at higher values between some or all of the merged sets observed in the limited program run,  but one supposes there will be.   .

Still another little program was written to identify predecessors of every odd number from 1 to 20000,  with which must be included the extensions,  16n+3,  n odd from 1 to 1250,  since extensions don't have predecessors.   Every odd integer from 1 to 8000 appeared,  again indicating that no integer is lost from the successor graph by being "shaded" by the two 3-loops.

My Collatz Home Page      

Index to Terms Used