Two or three simple tests have emerged which prove useful in discovering whether or not any particular (d*n+c)/2i iteration on the odd positive integers will be Collatz-like.
First, there must be a root node for there to be a predecessor tree. I.e., a single integer must appear as its own predecessor/successor. In algebraic terms, there must be a single solution to the parametrized equation for n among the odd integers using any integer i.
n=(d*n+c)/2i
or, equivalently,
n*(2i-d)=c
Here are a few examples:
The equation is solved for d=3, n=1, c=1, i=2, the prototypic Collatz sequence (3n+1)/4 at n=1.
The equation is also solved for d=3, n=3j,
c=3j, and i=2, thus enabling a whole
family of additional Collatz-like examples,
(3n+3j)/2i.
(While i=2 at the root for all these 3j
cases with j>=1, i=1 elsewhere in the tree. This
single instance prevents use of a simpler expression for the iterative
process,
(3n+3j)/2
(without the i as superscript on 2)).
No integer solutions exist for d=5,c=1, i.e. (5n+1)/2i.
Solutions occur with d=3, n=3, c=15, i=3, ((3n+15)/23 at n=3). with d=3, n=1, c=3, and i=2, (3n+3)/22 at n=1), and with d=5, n=1, c=3, i=3, ((5n+3)/23 at n=1). But these systems are spoiled by the loops that appear.
Second, the state transition diagram must demonstrate that no possible paths exist which enable formation of a cycle in the predecessor graph. See both a positive (just below) and a negative example.
Finally, a quick and dirty traversal of the Collatz-like itinerary
from a few (say up to 200) small odd integers will often
quickly reveal a non-trivial loop or multiple trivial loops. See some examples.
I had fully expected that this analogue would quickly reveal itself as a failure in the sense that there would be loops or diverging itineraries, but it appears that this case mimics the noted Collatz (3n+1)/2i conjecture, showing the convergence of all positive integers to the root, thus deserving the full attention given to the original conjecture, j=0.
There is a difference at the root. The odd integer 3 is the root. Its first predecessor is 1. The trivial infinite loop at the root is 3 giving itself. (In the (3n+1)/2i case the root is 1, and the trivial loop is 1 giving itself).
We continue to ignore the even integers throughout since they trivially attach into any predecessor graph for the odd integers.
We present the state transition diagram for the predecesor graph
first, using the
values mod 3 of of the integers to represent the states which control predecessor selection..
This diagram is more complete than those of the (3n+1)/2i and the (5n+1)/2i cases. All states, including the leaf nodes, are shown, all elements have their extensions attached to them, and the beginnings of a second left descent reached from an extension is indicated. Nevertheless, the diagram is notably simple.
When a node in the left descent is 0[9], a leaf node 2[3] is produced whose extensions are also all 2[3] and thus also all leaf nodes. Otherwise, the first extension is 1[3] (also a leaf node) but the second extension is 0[3] which therefore heads a fresh left descent, the beginnings of which are shown.
We should look briefly at a short sample of the binary predecessor
tree for this (3n+3)/2i analog.
The only kind of left descents produced from this state diagram are like the e(s)nt ones of the (3n+1)/2i case in that the Collatz predecessor is smaller than the successor. Very long left descents can be obtained simply by starting with a value of n which contains a large power of 3.
To estimate the density of the integers included in these left
descents, instead of summing the densities of all the l.d.a.s
which represent all the paths in the abstract predecessor tree as was
done for (3n+1)/2i, we would have to sum the
densities of a list of left descents of this type, j from 1 to
infinity. But there is a difficulty. There is no
characterization of the headers of the would-be l.d.a.s except that its
successor (given by (3n+3)/2) will be an odd
positive integer. Then we must add in the density of the integers
represented among the right descents consisting entirely of leaf nodes,
which, again, appear difficult to characterize and
to sum.
Because of these difficulties, I have not made an estimate of
the integer densities to be expected here, so cannot even say that
these lists of l.d.a.s and right descents "appear" to contain all the
odd positive integers. However, we can see that the edges
in the state diagram (which are all directed) all map to
edges in the presumed binary tree. Hence, the directed graph
arguments would lead to the conclusion that all odd integers represented
in an abstract list of lists (serving the role of the abstract binary tree in
the (3n+1)/2i case) and the right descents of extensions will
all lead to the 3 at the root. Also, the limited degrees of the
nodes and the directed nature of the edges in the state transition
diagram implies that once they are used to construct a binary tree, no
further edges can be formed, no cycle can arise, and all paths
lead to the root.
I am indebted to
Ernst Berg for suggesting I
explore several (3x+y)/2i variants. These led me to the
3j generalization to be discussed here. Ernst Berg's web
page itself now gives a path for one trajectory for j=4, j=5,
and j=9 in (3n+3j)/2i.
Ernst Berg's
web page (on 6/23/03) references AT&T's Integer
Sequences which (in sequences A039508 through A039515) report loops
and minimum points for a large number of Collatz variants and a
reference to D.
Wasserman's listing of loops in similar variants. These sources
include indications that early instances among the
(3n+3j)/2i variants converge to
3j.
An interesting e-mail communication from
Oleg in October 2004 regards these variants of the orginal Collatz
iteration as scaling transformations or morphisms. He reveals a number
of potential applications of this viewpoint to future explorations of
the Collatz conjecture.
The state transition diagram for (3n+3j)/2i
is extremely simple, containing only a single node representing the left
descents and a small set of nodes representing leaf nodes.
The binary predecessor trees which can be constructed using the nodes
and edges from such a simple state transition diagram are necessarily
quite simple. There is a single root node whose value is
3j. The predecessors of a node with value
n are
calculated from
(2i*n-3j)/3.
The extensions of a node with value n are calculated from
2*n+3(j-1). The predecessors are depicted as
left children and the extensions as right children in the binary
predecessor trees.
The second of the predecessors of the root in all these trees is a
feature of interest. This predecessor has a value equal to that of
the root itself. When n is 3j, the
Collatz-like iteration
(3*3j+3j)/22 gives
4*3j/22 or
3j. This results in the trivial loop which concludes the
itineraries of all the integers in the tree.
The fact that a division by 3 occurs at each step to a predecessor
implies that a left descent of length at least j occurs at the left of
the tree, and that all paths to leaves contain at least j steps. Since
extensions can be generated without limit, every right descent is
infinitely long. The binary tree will tend to be very wide and rather
shallow.
The binary predecessor trees for other members of the
(3n+3j)/2i set follow the
same general behaviors, though there is much difference in
detail. As j is increased, the length of the shortest
paths to leaves is correspondingly increased, with the result that
every path from 1[3] and 2[3] is at least j long. The
binary tree will be deeper, but still very wide. The only
relatively short paths are for those values in 0[3] which happen to
reside somewhere high in the tree.
With all these idiosyncratic behaviors it again seems impossible to
calculate the densities of the integers represented in the binary
predecessor trees, and I have not made the attempt.
Properties of (3n+3j)/2i
for j>=2
(3n+3j)/2i
My Collatz Home Page
Index to Terms Used