Showing Complete Path Strings and the Huge Scatter in the Generation Tree of Instances of a Given Left Descent Set

This page shows a number of things.  First there is a SPITBOL program which accepts a coefficient (from 2^a*3^b),  and a constant (c)  and determines the series of integers for n=0,  1,  2,  ...  reached by several successive instances of that formula.  It then traces the full path from 1 to each integer in the series.  The example shown is for the terminating integer in the ebbt set whose formula is 384n+321.  Each line of program output is the integer whose path is being traced and the string which compactly denotes the path to it.

Note that the program is written to run to infinity; there is no provision made for termination.  But since this SPITBOL version is limited to halfword precision,  numeric overflow stops the program as soon as a value greater than 32767 is encountered in the arithmetic processing.  This is the cause of the error message which terminates the output.

*pathtrck
            &TRACE = 300; &DUMP = 2; &STLIMIT = 32000
            input break(' ') . sname ' ' break(' ') . coeff ' ' rem . const
            output = 'For string: ' sname ', formula: ' coeff 'n+' const '...'
            tval = otval = const
            ostring = ''
oloop       count = 0
            tval = 3 * tval + 1
iloop       tval = tval / 2
            count = count + 1
            eq(tval,1)                           :f(notdone)
            ostring = substr('sb3456789ABCDEF',count,1) ostring
            output = lpad(otval,6) lpad(ostring,60)
            ostring = ''
            tval = otval = otval + coeff         :(oloop)
notdone
            '02468' substr(tval,size(tval),1)    :s(iloop)
            ostring = substr('sb3456789ABCDEF',count,1) ostring:(oloop)
end
ebbt 384 321
--------end of source; start of output------------------------------
For string: ebbt formula: 384n+321
   321                                                      43b5bb
   705                                                   43bss63bb
  1089                                               43bss4bb3s4bb
  1473                           45ss34bb4sss3sssssbsbss3bss3ss3bb
  1857                                                  43bss4b6bb
  2241                                               43bs3sb6sb3bb
  2625                                                      4364bb
  3009                                                 Ass4bsbs3bb
  3393                                                43bs3s43s5bb
  3777              45ss34bb4sss3sssssbsbss3bsssbssbs4ssss3bbs33bb
  4161                                        43bs3s4sbs3b3s3ss4bb

ERROR 028 -- Multiplication caused integer overflow

The notation used to denote the paths is simply a concatenation of the number of twos which divide the even number reached from the 3n+1 step of the Collatz process.  The program builds this right to left.  The usual 's' and 'b' denotations indicate 1 or two divisions by 2,  and for bigger numbers hexadecimal digits are used ("extended" if necessary,  i.e.  if a digit greater than 15 is required,  a letter above 'F' is used to represent it).  The contrast between 's' and 'b' and the hexadecimal digits in the complete strings makes it quickly apparent what combination of left descents and right descents comprised the entire path.

The paths may be traversed starting from 1 by use of the successive elements in the descriptive string from left to right as the values of p(k)  in the recursive formula

Z(k):=(-1+Z(k-1)*2^p(k))/3.

Note that the complete strings all end with an 'bb' string which is immediately preceded by a hexadecimal digit,  as they must since the formula used to generate the probed numbers is that for 'ebbt' left descents,  i.e.  left descents originating in an extension and terminated at a leaf node.

Note the very disparate lengths of the paths and their combinations in the overall predecessor tree at which successive instances of the 'ebbt' string occur.  This phenomenon is evident in all similar runs of this program.  There simply appears to be no regularity to the behavior of integers in the Collatz trajectory at a more pervasive level than that represented by the rooted and terminated left descents.

There is a severely limited mechanism by which some control is passed from elements in a left descent through their extensions to the first elements of left descents from the extensions.


My Collatz Home Page         Index to Terms Used