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, 8n+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.