The Infamous Chain to 27

I took a lap-top loaded with the Maple V Computer Algebra
System to the Jersey
shore in July '98, intending to learn as much as I could about Maple and
apply it to the Collatz 3*n*+1 problem. Maple contributed
immeasurably to the gestalt described in these pages. From the first
worthwhile clue (herein) to providing programming capability to develop
examples leading to key insights, Maple was the *sine qua non* for
this work.

I had in previous summers exhausted my other resources looking for a pattern which might cover the integers in an Escher-like way without any success. But I had developed some facility for navigating in the trajectories and the predecessor tree. So I asked Maple what it could do.

It is only a few minutes drudgery to discover that the left descent which
terminates in 27 is an *bsssbssbsbbssssbs* one and to present to
Maple the set of simultaneous equations which that sequence implies.
The number 27 is the frequently cited tough one,
so its investigation is particularly compelling. The session is
reproduced here (except I have put the set elements in order where Maple
scrambled them).

> bsssbssbsbbssssbs:={x2=(4*x1-1)/3, x3=(2*x2-1)/3, x4=(2*x3-1)/3,

> x5=(2*x4-1)/3, x6=(4*x5-1)/3, x7=(2*x6-1)/3, x8=(2*x7-1)/3,

> x9=(4*x8-1)/3, x10=(2*x9-1)/3, x11=(4*x10-1)/3, x12=(4*x11-1)/3,

> x13=(2*x12-1)/3, x14=(2*x13-1)/3, x15=(2*x14-1)/3, x16=(2*x15-1)/3,

> x17=(4*x16-1)/3, x18=(2*x17-1)/3}; bsssbssbsbbssssbs := {x2 = 4/3 x1 - 1/3, x3 = 2/3 x2 - 1/3, x4 = 2/3 x3 - 1/3, x5 = 2/3 x4 - 1/3, x6 = 4/3 x5 - 1/3, x7 = 2/3 x6 - 1/3, x8 = 2/3 x7 - 1/3, x9 = 4/3 x8 - 1/3, x10 = 2/3 x9 - 1/3, x11 = 4/3 x10 - 1/3, x12 = 4/3 x11 - 1/3, x13 = 2/3 x12 - 1/3, x14 = 2/3 x13 - 1/3, x15 = 2/3 x14 - 1/3, x16 = 2/3 x15 - 1/3, x17 = 4/3 x16 - 1/3, x18 = 2/3 x17 - 1/3}> bsssbssbsbbssssbsd:=isolve(bsssbssbsbbssssbs);

bsssbssbsbbssssbsd := {x1 = 445 + 129140163 _N1, x2 = 593 + 172186884 _N1, x3 = 395 + 114791256 _N1, x4 = 263 + 76527504 _N1, x5 = 175 + 51018336 _N1, x6 = 233 + 68024448 _N1, x7 = 155 + 45349632 _N1, x8 = 103 + 30233088 _N1, x9 = 137 + 40310784 _N1, x10 = 91 + 26873856 _N1, x11 = 121 + 35831808 _N1, x12 = 161 + 47775744 _N1, x13 = 107 + 31850496 _N1, x14 = 71 + 21233664 _N1, x15 = 47 + 14155776 _N1, x16 = 31 + 9437184 _N1, x17 = 41 + 12582912 _N1, x18 = 27 + 8388608 _N1}

Thus, Maple, on the basis of nothing more than the set of equations
which reflects the ordered sequence of Collatz steps which appears in
the left descent to 27, comes right up with the values of the elements
of that left descent as the constants in a set of equations of the form
*dn+c*. Note the considerable scatter in the step sizes among the
left descent members. No wonder it has been difficult to detect
patterns in the Collatz trajectories by inspection!

Suppose we factor those coefficients on n, given in order of ascending subscript on x,

> map(ifactor,[129140163,172186884,114791256,76527504,51018336,68024448,

> 45349632,30233088,40310784,26873856,35831808,47775744,31850496,

> 21233664,14155776,9437184,12582912,8388608]);17 2 16 3 15 4 14 5 13 7 12

[(3) , (2) (3) , (2) (3) , (2) (3) , (2) (3) , (2) (3) ,8 11 9 10 11 9 12 8 14 7

(2) (3) , (2) (3) , (2) (3) , (2) (3) , (2) (3) ,16 6 17 5 18 4 19 3 20 2

(2) (3) , (2) (3) , (2) (3) , (2) (3) , (2) (3) ,22 23

(2) (3), (2) ]

Those coefficients for _N1 in the equations for x(*i*) for
*i* =1..18 are all products of powers of 2 and 3. The power of 3
decreases by one for each increment in *i*, the power of two
increases by 1 for each *s* step and by 2 for each
*b* step. These observations, after some further adjustment to
properly root every left descent both in an extension at the top and in
a leaf node at the bottom, have been generalized to other left descents
and became central to the whole gestalt being described here.

Attempts to investigate other values of _N1 in the hope of finding
another instance of a *bsssbssbsbbssssbs* left descent headed (x1)
by an extension and ended (x18) by a leaf were frustrating. Sometimes
the x18 value was a leaf; sometimes the left descent just continues on
from x18. Often there was an extension nearby x1, but sometimes x1 was
just an interior node in a left descent already in progress. Evidently
only selected values of _N1 result in specification of left descents
which precisely fit the pattern established by the 445 ... 27 left
descent. This example, and similar simpler ones, underscored the
necessity of finding means to anchor both the extension and the leaf
elements of every left descent.

It is a matter of pure good fortune that x1 is an extension (55*8+5) and x18 is congruent to 0 mod 3, since nothing was done to force those conditions. It turns out that anchoring the left descent at both ends results in the coefficients being multiplied by 24 (i.e. 2^3*3).

Two lessons emerged here. (1)There is information enough in the mere
sequence of *s* and *b* steps in a left descent to reproduce the
numeric sequence observed in the left descent. (2)Left descents occur in
infinite sets containing the identical sequence of steps.

It may be of interest to contrast the above with a discussion of this left descent assembly in terms of a predecessor tree consisting of residue sets, which is what eventually evolved.