The purpose of including examples of systems which do not converge to some integer is to use their contrasting behavior to emphasize the qualities of the behavior which is permissive of convergence.
Two basic considerations rule the behavior of all these predecessor graphs. What is the relationship between successive predecessors of a given integer, appearing as right descents in the binary version of the predecessor graph (presumed for the moment to be a tree and referred to as "extensions" elsewhere in these pages)? What are the rules which govern the predecessors in the left descents in the graph (presumed tree) which formed left descent assemblies (l.d.a.s) in the classic (3n+1)/2i case?
For extensions, determine the relationship between the smallest predecessor of a given integer and each of its subsequent extensions. In the (5n+1)/2i case, each T(k,j) is 16*T(k,j-1)+3 where j indexes through a right descent from a given parent. E.g., for the integer 3, whose lowest predecessor is 19, has extensions 307, 4915, 78643, 1258291 ... , all of which result in 3 in the Collatz-like iteration. These are due to successive values of i = 9, 13, 17, 21, ... in the generating formula. Note in passing that the values of i may start at a much higher value than those in the l.d.a.s for (3n+1)/2i where i is always either 1 or 2 for the smallest of a set of extensions.
The following table gives the rules for determining the predecessor in the left descents according to the values of the parents in the predecessor tree mod 5.
For 5n+1 when T(k-1) mod 5 == 0, T(k-1) is a leaf node when T(k-1) mod 5 == 1, T(k):=(-1+2p(k)*T(k-1))/5 with p(k) mod 5 == 4 when T(k-1) mod 5 == 2, T(k):=(-1+2p(k)*T(k-1))/5 with p(k) mod 5 == 3 when T(k-1) mod 5 == 3, T(k):=(-1+2p(k)*T(k-1))/5 with p(k) mod 5 == 1 when T(k-1) mod 5 == 4, T(k):=(-1+2p(k)*T(k-1))/5 with p(k) mod 5 == 2
Using these rules, one can tediously work out the possible state transitions from every combination of integers mod 5 and mod 8. But the state diagram drawn to represent all 32 non-leaf states would be hopelessly complicated, so the picture was drawn using only integer values mod 16.
The graph is quite unlike that for the (3n+1)/2i) case, where the l.d.a. header nodes do not accept edges from any internal nodes which arise in an l.d.a. No node can be discerned as a header for any structural unit and, here in the (5n+1)/2i case, every node is reached in multiple ways, thus allowing loops to be constructed
Two well known loops occur in the (5n+1)/2i analogue, 83-13-33-83..., and 17-43-27-17... . In the predecessor graph these consist of nodes 3-1-13-3... and 1-11-11-1..., respectively. The potential for loops apparent in the state transition graph is realized during traversal of these particular itineraries.
While the state transition graph shows how the loops are possible, slightly greater detail may be of interest. In the case of the 17-43-27-17... (1-11-11-1... in the graph) loop, no extension is involved (i.e. the powers of 2 in the divisor are 1, 3, and 3). It just happens that (5*(5*(5*17+1)/2)+1)/8)+1)/8 is 17.
In the case of the 83-13-33-83 loop, the main feature is that 83 is the first extension of 5. The following segment of the predecessor graph (read from the bottom up) shows the relationship: 83 as the extension of 5 gives their common successor, 13. The usual ascent from 13 reaches 83 which restarts the cycle. It is the fact that 83 appears in two roles, both as an extension (of 5) and as a successor (of 33) in an l.d.a., that causes the generation of a cycle.
5 \ 83 / 33 / 13 / 5 \ 83
But 5*((5*((5*83+1)/32)+1)/2)+1)/2=83 with or without any story about l.d.a.s and extensions.
The presence of cycles in the graph is quite enough to show that the Collatz conjecture does not apply in the (5n+1)/2i case.
A Maple program was written to solve equations like n=(5*(5*(5*(5*n+1)/p1+1)/p2+1)/p3+1/p4 where p1 through p4 systematically explored combinations of powers of 2 from 2 through 256 and the depth of nesting was varied from 3 through 6. The program found only the trivial cycle 1-3 and the 2 three cycles cited above so these cycles are unique up to the stated limits.
Since it appears that a number of integers result in paths which diverge to infinity, it seemed to be of interest to pursue this point further.
This case represents a rather extreme example in that almost everything which can go wrong does.
There is the trivial loop at 1 ((5*3+3)/2^3) gives 1 immediately). In addition, there is a 2-loop (9--3--9...), and 5 3-loops (39--99--249--39..., 43--109--137--43..., 51--129--81--51..., 53--67--169--53..., and 61--77--97--61...). The first of these is reached from 15, but the others are subgraphs containing only the loop members.
A number of small integers either begin paths apparently diverging to infinity, namely 5, 65, 75, 105, 135, 145, 205, 225, 305, 1005, 2625, or values appearing early in those diverging paths, namely, 11, 21, 23, 63, 91, 101, 111, 123, and 191. These paths reach magnitudes from about 3*10^9 to about 1*10^20 in about 100 iterations of the (5n+3)/2^i rule.
Only rarely does any path appear with much length leading into these diverging paths, namely, 55, 265, 125, and 585. Some few values lead into the 2-loop or the 3-loop, namely 15, 45, and 75.
These observations were gathered by tracing the successors of the integers from 1 through 201. Where larger numbers appear above, they were determined by running path segments briefly in the predecessor direction. Probably many more diverging paths could be added to the list if time were taken to seek them. A predecessor graph would be quite useless (even if possible to construct) in a system with so many diverging paths.
After the speculation that (3*n+3j)/2i always converges to 3j arose, it seemed worth checking whether (3*n+3*p)/2i with p=5, 7, 11, and 13 similarly converges in some way. These cases were quickly checked for n in the range 1..201 and just as quickly shown to contain loops.
For (3n+15)/2i, there were trivial loops at 3 and 15, and a 3-loop at 57, 93, 147, implying that the predecessor graph contains at least 3 distinct subgraphs.
For (3n+21)/2i, only 21 gives a trivial loop and there is a 3-loop at 3, 15, 33, implying that there are at least 2 distinct subgraphs.
For (3n+33)/2i, only 33 gives a trivial loop but there is a 2-loop at 3 and 21. The 8-loop at 147, 237, 93, 39, 75, 129, 105, and 87 implies that there are at least 3 subgraphs.
For (3n+39)/2i, both 3 and 39 give a trivial loop. There is a 5-loop at 633, 969, 1473, 2229, 3363, and a 15-loop at 537, 825, 1257, 1905, 2877, 4335, 3261, 4911, 3693, 5559, 4179, 393, 609, 933, 1419. Thus there are at least 4 distinct subgraphs in this case.
This game could be played forever, but it does not appear likely that the predecessor graph will be a connected graph for any cases of this sort. Since these cases were so easily identified as non-Collatz, no state diagrams or predecessor graphs were constructed for display. Additionally, AT&T's Integer Sequences reports (in sequences A039508 through A039515) loops and minimum points for a large number of Collatz variants and a reference to D. Wasserman's listing of loops in many of these variants.
In June 2003 some web pages appeared (not known to me until Dec. 2003) which go into considerable detail about a large number of variant formulas most of which result in loops in their trajectories. Refer to one page in particular.