This program was the first to be written of the four which deal in some way with problems of infinity among aspects of the Collatz conjecture. This one generates an arbitrarily large subset of the infinity of l.d.a.s by tracing the abstract predecessor tree.

The three more recently written are **nbigpath**,
**makepath**, and **npathtrk**. **Nbigpath** develops the general predecessor tree from its
root, ignoring the l.d.a.s. **Makepath** accepts a specification of a path fragment and a
replication factor and produces an (often very large) integer which will
(usually) produce a Collatz trajectory which exhibits the requested
number of sequential path fragments before a "tail" which takes the
trajectory to 1. **Npathtrk** accepts
the integer produced by makepath (or any other integer, for that matter),
follows the Collatz trajectory, and produces a little plot which
represents the entire Collatz trajectory.

**Treegrow** produces a huge file of lines, each detailing
an instance of an algebraic expression

The program consists of three procedures. The first
merely accepts the input parameter which will control the depth to which
the abstract connection tree will be pursued and initiates the recursive
descent into the abstract tree by making an initial call to
**treecurs**, the recursive procedure. Note that the
whole tree is grown from the first possible extension formula,
8*n*+5 or 5[8].

treegrow := proc(mxl) fopen(`treegrow.lst`, WRITE,TEXT); treecurs(e, 8, 5, 0, mxl); close(`treegrow.lst`) end

The **printem** routine is the routine which prints a line of output
for each element of a left descent
every time **treecurs** identifies a leaf set in its recursive descent. It
accepts as parameters the string describing the left descent path, the
coefficient appearing in the expression for the leaf set **treecurs** found
(in its top down traversal) and the constant appearing in the expression
for the leaf set **treecurs** found. It initializes its internal variables
and (in the first loop) determines the power-of-2 depth that the path
reached. It then (in its second loop) does the bottom-up trace of the
path outputting the expression describing each subset element in the
abstract predecessor tree path which was traversed by **treecurs**. The
active constant value, *acon*, is kept up to date as the path is
traversed upward. To reduce the volume of output, only subsets whose
constant value is less than 1024064 are actually printed. (That value
could be adjusted for more or less output.)

printem := proc(path::string, coeff, const) local n, p2, acon, p3, i; n := length(path); p2 := 3; acon := const; p3 := 1; for i to n do if substring(path, i .. i) = b then p2 := p2 + 2 elif substring(path, i .. i) = s then p2 := p2 + 1 fi od; while 0 < n do if acon < 1024064 then fprintf(`treegrow.lst`, `x%2d of %-23s is 2^%2d*3^%2d*n+%17d\n`, n, path, p2, p3, acon); fi if substring(path, n .. n) = b then acon := 3/4*acon + 1/4; p2 := p2 - 2; p3 := p3 + 1 elif substring(path, n .. n) = s then acon := 3/2*acon + 1/2; p2 := p2 - 1; p3 := p3 + 1 fi; n := n - 1 od end

The recursive routine accumulates in *level* the power-of-2
depth reached. When the tree is deeper than the requested maximum
depth recursion stops. If the constant in the expression reached by
a greater level of recursion is greater than 66096000 the recursion
stops. (Those values could be adjusted for more or less
output.) Otherwise we look at the three subsets in the node which
was specified by the parameters passed in, and print the leaf node
values, make the recursive call for a descent via a *b*
step, or make the recursive call for a descent via an *s*
step, updating the coefficient value, the constant
value, and the path information on the fly within each possible
procedure call. The comments (starting with "#") indicate how it
goes in the first major branch.

treecurs := proc(path::string, coeff, const, level, mxl) if mxl < level then RETURN(NULL) fi; if 66096000 < const then RETURN(NULL) fi; #look at children of const (i.e. c-value), itself #it might be a leaf if const mod 3 = 0 then printem(path, coeff, const) #it might be a b-step parent elif const mod 3 = 1 then treecurs(cat(path, b), 4*coeff, 4/3*const - 1/3, level + 2, mxl) #it must be an s-step parent else treecurs(cat(path, s), 2*coeff, 2/3*const - 1/3, level + 1, mxl) fi; #look at children of const + coeff (i.e. d-value) (same possibilities for children) if (const + coeff) mod 3 = 0 then printem(path, coeff, const + coeff) elif (const + coeff) mod 3 = 1 then treecurs(cat(path, b), 4*coeff, 4/3*const + 4/3*coeff - 1/3, level + 2, mxl) else treecurs(cat(path, s), 2*coeff, 2/3*const + 2/3*coeff - 1/3, level + 1, mxl) fi; #look at children of const + 2* coeff (same possibilities for children) if (const + 2*coeff) mod 3 = 0 then printem(path, coeff, const + 2*coeff) elif (const + 2*coeff) mod 3 = 1 then treecurs(cat(path, b), 4*coeff, 4/3*const + 8/3*coeff - 1/3, level + 2, mxl) else treecurs(cat(path, s), 2*coeff, 2/3*const + 4/3*coeff - 1/3, level + 1, mxl) fi; RETURN(NULL) end

And here, at last, is the statement invoking the whole program in a run which goes to a depth of 55. In the event, the 55 was not the limiting factor; the numeric values limiting output and further pursuit of recursion proved to be limiting.

> treegrow(55);

When the output from **treegrow** (some 61,000 lines) is sorted on
n, p2, and p3, all the lines at a given depth with common 2^a and 3^b
values are grouped together. Simply counting the lines sharing these
values produces a cardinality table. An
argument using the summation of densities of odd integers in this table
establishes that all odd positive integers appear in the predecessor tree.

While
the detailed structure of the predecessor tree is not so well detailed
from **treegrow** as it is from

rsetidea, **treegrow**
played an essential role in the development of the argument that the
prdecessor tree contains all the positive odd integers.