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 *densout*. *Rsetcurs* 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