Programs for Exploring Residue Sets in Collatz Graph

This page is concerned with the Maple programs employed in production of lists of residue sets which constitute the abstract predecessor tree.  The motivation and discussion of the major results appear elsewhere.

The recursive program treegrow   (used in the initial a priori integer-by-integer development of the predecessor tree)  provides a nearly complete basis for the central routine in the program rsetidea,  (named after "residue set idea").  All that is additionally required is to construct the predecessor tree displaying residue sets rather than indiviual integers to reveal the upward traversal in the entire path of every l.d.a. from its leaf node to its root.  Displaying this data provides the entire dataset of specific l.d.a.s elements on the path from root to leaf for every l.d.a.

The program rsetidea contains subroutines rsetcurs and densoutRsetcurs is the heart of the program. The equations employed in rsetcurs are presented in a prior page.

 rsetcurs := proc(path::string, cvalue, dvalue, levelp2)
 global lda, depth, c, fd, mylist, dlevel, outfile, mxng, mxlg;
 #this is the rsetidea source in text form
  if mxlg < nops(mylist) or mxng < cvalue then
    RETURN(NULL)
  end if;
 #push the next l.d.a. element onto the stack
    mylist := [op(mylist), [path, levelp2, cvalue, dvalue, evalf(1/dvalue)]];
 #an l.d.a. element can be a leaf, a ":b" parent or an "s" parent
 #the pattern of the recursive calls at each recursive invocation tracks
 #progress at each level to ensure complete exhaustion of the possibilities
 #look for children of cvalue itself
  if `mod`(cvalue,3) = 0 then
    densout(path)
  elif `mod`(cvalue,3) = 1 then
 #it might be a b-step parent
    rsetcurs(cat(path,"b"),4/3*cvalue-1/3,4*dvalue,levelp2+2);
  else
 #it must be an s-step parent
    rsetcurs(cat(path,"s"),2/3*cvalue-1/3,2*dvalue,levelp2+1);
  end if;
 #look for same possibilites for cvalue + dvalue
  if `mod`(cvalue+dvalue,3) = 0 then
    densout(path)
  elif `mod`(cvalue+dvalue,3) = 1 then
    rsetcurs(cat(path,"b"),4/3*cvalue+4/3*dvalue-1/3,4*dvalue,levelp2+2);
  else
    rsetcurs(cat(path,"s"),2/3*cvalue+2/3*dvalue-1/3,2*dvalue,levelp2+1);
  end if;
 #look for same possibilites for cvalue + 2*dvalue
  if `mod`(cvalue+2*dvalue,3) = 0 then
    densout(path)
  elif `mod`(cvalue+2*dvalue,3) = 1 then
    rsetcurs(cat(path,"b"),4/3*cvalue+8/3*dvalue-1/3,4*dvalue,levelp2+2);
  else
    rsetcurs(cat(path,"s"),2/3*cvalue+4/3*dvalue-1/3,2*dvalue,levelp2+1);
  end if;
 #pop that exhausted l.d.a. element
  mylist := subsop(nops(mylist) = NULL,mylist);
  RETURN(NULL);
end proc;

The densout.subroutine is called whenever a leaf is encountered and uses its sole loop to traverse the current l.d.a., outputting the {c[d]} value for each constituent element.along with its root's {c[d]} values in the current instantiation of the l.d.a.


    densout := proc(path::string)
      local step, llevel, dllevel, lcvalue, ldvalue;
      global mylist,lda,depth,c,d,fd,outfile;
 #data from main routine at depth reached for use here
 #need local variables starting at passed in value
      llevel := nops(mylist);
      lcvalue := mylist[llevel,c];
      ldvalue := mylist[llevel,d];
 #the data structure is a list (mylist) of lists [path,p2level,c,d,density]
 #five constants are used to facilitate the addressing into each list instance
 #these are coded in rsetidea procedure
 #each list instance records the accumulated values for a power-of-2 level
 #mylist is used as a stack to track the position in the abstract tree traversal
 #traverse the l.d.a. fragment upwards, i.e. from leaf to header,
 #keeping lcvalue and ldvalue current for the dllevel risen to
 #dllevel is local to densout and tracks upward path in mylist
       fprintf(outfile,`%20s %11d %12d %21s %12d %12d %13e \n`,
         mylist[llevel,lda],mylist[llevel,c],mylist[llevel,d],mylist[nops(mylist),lda],
         lcvalue,ldvalue,mylist[llevel,fd]);
    for dllevel from nops(mylist) -1 to 2 by -1 do;
        step := substring(path,dllevel+1..dllevel+1);
           if step="b" then  lcvalue := (lcvalue*3+1)/4; ldvalue := 3/4*ldvalue
               elif step="s" then lcvalue := (lcvalue*3+1)/2; ldvalue:= 3/2*ldvalue
           end if;
       fprintf(outfile,`%20s %11d %12d %21s % 12d %12d %13e \n`,
       mylist[dllevel,lda],mylist[dllevel,c],mylist[dllevel,d],mylist[nops(mylist),lda],
       lcvalue,ldvalue,mylist[dllevel,fd]);
    od;
 end;

Rsetidea accepts two parameters; the first limits the depth of penetration through the recursive levels which will be performed and the second limits the magnitude of the c integers which the program will penetrate to.   The rsetidea program sets up the environment and establishes the residue set at the root of the abstract tree before it makes the initial call to rsetcurs.

    rsetidea := proc(mxl,mxn) global lda,depth,c,d,fd,densitysum,mylist,
       outfile,mxlg,mxng;
    outfile:=fopen(`\\maplev4\\mywork\\collatz\\rsetidea.lst`,WRITE);
    mxlg := mxl;  mxng := mxn;
    lda:=1;  depth:=2; c:=3;  d:=4;  fd:=5;
    fprintf(outfile,`%20s %11s %14s %23s %10s %11s %8s \n`,
       "modified lda","cdown","ddown","lda at leaf","cup","dup","addsin");
    mylist:=[];
    rsetcurs("e", 5, 8, 1);
    fclose(`\\maplev4\\mywork\\collatz\\rsetidea.lst`)
    end;

And the whole program is begun with a simple invocation, where the parameters specify the maximum number of levels and the maximum magnitude of integers explored during penetration into the abstract predecessor tree.

    rsetidea(13,1.0e10);

Rsetidea  is a recursive procedure with each invocation tracking progress in its particular level of the tree structure.  The data structure selected to represent each level in the current pathway back to the root is a list of lists called mylist.  At each level of mylist,  the variables recorded are the left descent assembly name,  the depth of the node,  the c value of the residue set,  the d value of the residue set,  and the density sum of the residue set to date.  The number of lists in the list of lists is to be maintained equal to the depth of recursion achieved in rsetcurs.  There must be an independent data structure because the whole stack of  l.d.a.  nodes traversed prior to an encounter of the leaf node must be available for output.

The program version shown maintains a floating number giving the sum of the densities of integers in the currently recognized l.d.a.  elements, but in the end that feature proved useless, because the values accumulated in the summed densities consistently come out unreasonably large.

A sole parameter, path, passed to densout is used to identify the l.d.a.  which has reached its leaf node.  The local variables within densout,  filled from mylist,   permit output of the l.d.a.  elements at each depth in the completed l.d.a. 

The lateral progress in the predecessor tree is reflected by returns to rsetidea where subsequent invocations of densout will reflect new l.d.a.s in a sibling branch of the tree.  When a particular recursive level in rsetcurs must end,  because all paths from its level have been explored,  the exhausted level of mylist is popped before RETURN from the recursive invocation, so that the prior level resumes in synchrony with its depth of mylist.   It can happen that a number of consecutive levels can be completed with some l.d.a. in which case several recursive levels are popped in rapid succession.

It is almost impossible to make sense when talking about the output from rsetidea, but a (a href="allto27.html> detailed example of the descent to 27 may be helpful.

The program is driven primarily in the predecessor order, i.e. it starts at 5[8] and proceeds to explore all residue set predecessors in turn until it reaches some arbitrary preset limit which prevents the program from running forever. Whenever a leaf set is encountered, a new left descent assembly has been found, and further exploration of the predecessor tree is postponed while the properties of the left descent assembly are examined, partially recorded, and output for inspection. The output proceeds from the leaf node back to the root node, i.e. in the successor direction, but the output is arranged in columns, some of which appear to be in predecessor order and others of which appear to be in successor order. Since the accustomed presentation of a tree in computer science is with the root at the top with every node's children hanging below it, this view seems most natural to me. But the tree is a predecessor tree from the viewpoint of the Collatz trajectory, so the tracing of a Collatz trajectory starts internally within the tree and follows upwards along the paths to the root.

But it is worse. The stack used to record the key information about each element of each left descent assembly visited would customarily be built from the bottom upwards, which would result in the direction of the traced paths in the stack being in the predecessor diection, exactly contrary to the direction of tracing those same paths in the predecessor tree where an upward trace is in the successor direction. Of course, the orientation of the tree and of the stack are merely common conventions which happen to conflict in this instance. And still worse, the output from rsetidea needs to use both conventions in order that the residue sets as they exist in both the stack and the paths of the tree are displayed.

Below is a very small sample of the output from rsetidea. The last 2 columns were produced in the early version of the program, but deleted as useless after close study of the {c[d]} values revealed the source of the replication of certain integers.

A great deal is going on here, so some explanatory notes are given below. The unexpected numeric results presumably  (at least partially)  arise from instances like those in the following,  which are the first 12 output lines from rsetidea.lst.  The output has been embellished with "!" and "*" characters to point out two sources of the replicate integer counting which this approach encountered. 

The lines marked with "*" are ones which indicate some duplicative assignment of density into some residue sets which are visited in the upward paths within discovered left descent assemblies.   When "esbb" is first visited at its discovery as a leaf node, 33[256] is assigned a density of 1/256.  When it is again visited in the upward path from "esbbbb" its density is augmented by 1/2304 which means that 1/9 of its integers are recounted.  The same pattern of duplication is noted for 25[64] and 3[16] and countlessly more residue sets (not shown in this sample).

Also where cdown[ddown] differs from cup[dup]  (marked with "!", as in the second 'es' line and the third 'e' line),  the latter is a subset of the former.  Thus, a duplicate accounting is committed whenever such situations arise.

 modified lda cdown   ddown        lda at leaf   cup  dup    adds in      making
      es        3        16            es         3    16  6.250000e-02  6.250000e-02
       e        5         8   !        es         5    24  4.166667e-02  1.666667e-01
    esbb       33       256   *      esbb        33   256  3.906250e-03  3.906250e-03
     esb       25        64   **     esbb        25   192  5.208333e-03  2.083333e-02
      es        3        16   ***    esbb        19   144  6.944444e-03  6.944444e-02
       e        5         8   !      esbb        29   216  4.629630e-03  1.712963e-01
  esbbbb      513      4096        esbbbb       513  4096  2.441406e-04  2.441406e-04
   esbbb      385      1024        esbbbb       385  3072  3.255208e-04  1.302083e-03
    esbb       33       256   *    esbbbb       289  2304  4.340278e-04  4.340278e-03
     esb       25        64   **   esbbbb       217  1728  5.787037e-04  2.141204e-02
      es        3        16   ***  esbbbb       163  1296  7.716049e-04  7.021605e-02
       e        5         8   !    esbbbb       245  1944  5.144033e-04  1.718107e-01

Note in passing how the program works for the left descent assembly "esbbbb" (last six lines).  The path from "e" down   (in the abstract tree)  to "esbbbb" was created and its elements stacked.   Then at the leaf node the path is traversed   (upward in the abstract tree)  with calculation of the c[d] for each residue set.  The density sums are calculated and the residue sets' descriptive information for each visit are printed in parallel on a single line. While some of the features of this program proved irrelevant in the end, detailed verification of its correct behavior is worthwhile. The accuracy of the c[d] calculations and the 1/d calculations may easily be hand-checked in this output layout. The output also provides opportunity to check that the residue sets attributed to each level in the upward traversal are indeed subsets of the residue sets which occupy that level  (cup[dup])  and are therefore properly assigned as contributers to the inflated integer density in that node of the abstract tree in the downward traversal (cdown[ddown]).  For this purpose the c-value for the residue sets during both the upward- and downward- developments is maintained and output as part of the work of densout.  Checking the validity of the output against these requirements eliminates program errors as potential sources of error.

In this output read the cup column upwards for the series of Collatz predecessors of 5 in the "downward" path  (in the predecessor tree)   while for the "upward"  (Collatz successor path in the predecessor tree)   read downward in the cdown column.

We see (looking at the sequence after "esbbbb")  5, 3, 25, 33, 385, 513, are the predecessors of 5,  while 513, 385, 289, 217, 163, 245 are the successors of 513.  The early elements in the "upward" path are identical with the elements in the "downward" path at the same level. Thus it is not until 289[768] is reached that fresh increments to the density sum are observed.

In spite of the shortcomings of this program with regard to accurately accumulating the density sums of the left descent assemblies, it is useful in that it provided details about the residue sets which constitute the abstract tree, and those details permitted identification of the correct approach to summing the integer density in the abstract tree.

The skeptic might suggest that during the development of the abstract tree,  some loss of residue sets (or their members) could occur.  If this were to occur, it could not be said that the program identifies every odd integer in the predecessor tree.  However,  detailed tracing of the output in both the upward and downward portions of the program's progress,  facilitated by the presentation of the two directions on the sme output line,  shows that every step is fully developed in both directions.  Neither integers nor residue sets are lost or inserted into any path created.


My Collatz Home Page       Index to Terms Used