Other Iterations Behaving like (3n+1)/2i

Some Diagnostic Criteria

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.

(3n+3)/2i (i.e. (3n+3j)/2i with j=1)

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.

Properties of (3n+3j)/2i for j>=2

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.

(3n+3j)/2i

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.



My Collatz Home Page        Index to Terms Used