The "3N+1" problem involves starting with a particular integer N, and repeatedly performing the following operation:
If (N is even) divide N by 2
Else multiply N by 3, and add one.
For example, starting with the number 6, we get the following series:
6,3,10,5,16,8,4,2,1,4,2,1,4,2,1,4,2,1...
The 4,2,1 loop repeats over and over, so it's usually convenient to terminate the process once it is entered. All numbers tested so far eventually hit this loop, although it has not been proven that all numbers do. On the way to the 4,2,1 loop, the numbers go up and down, similar to the way hailstones do in a cloud - hence the name.
Note that the series above given for 6 includes the series generated for several other numbers, like 3, 10, and 5. Once a number falls onto this track, it can never leave. One can think of the track generated by a particular number as "casting its net" for other numbers along the way. For example, starting with N=12, one will hit this track in just one step. N=24 is 2 steps away, N=48 is 3 steps away, etc.
For any particular number N, there are two additional numbers of interest: The number of steps required to hit the 4,2,1 loop (HailSteps, in the graphs below), and the maximum number hit during the trip (HailMax). The following 3 graphs show the relationships between N and these 2 numbers for the numbers 5-1000.
There is a lot of structure in this graph - many repeating values, some apparant curves, etc. The crudely drawn arrow points to N=127, which is the beginning of a sparsely populated curve (one of many) going down and to the right. Let's take a look at some of the numbers on this curve - see table below. The number N=147 (2nd row of the table below) takes 114 steps to get to the 4,2,1 loop. The number 166 takes 5 fewer steps - and sure enough, we find that the 5th step from N=147 is 166. Have we figured out the whole table? Not hardly! If we start with the first number in the table, 129, we might expect to find that we hit 147 on the 5th step. But, we don't, we hit 146. What gives?
Well, we find that *both* 147 and 146 hit 166 on the 5th step. They do the same number of halve-steps (3) and the same number of 3N+1 steps(2), but the order is different, which throws in an extra 1. Basically, any ordering of the operations that can exist (as limited by the mod-2 parity rule) will give rise to 2 slightly different numbers that are essentially on the same track.
129 119 147 114 166 109 190 104 215 99 243 94 275 89 311 84 351 79 395 74 446 69 503 64
The vertical line just past 8000 on the X-axis represents the number 9232, which is the highest point reached on the track of many numbers. In other words, the descent from 9232 is an attractive one for this process. Once a number hits 9232 it starts on a 32-step path toward the 4,2,1 loop: 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4. But this path is (again) just 32 steps, and the graph above shows numbers landing on it from up to 150 steps away - so there are some very circituous, lengthy routes to 9232 (that never exceed 9232).
Again, we see interesting structure in this graph. Many numbers max out at low values, and once again we see the 9232 attractor (just below the Y=10000 line on the above graph) being the maximum point for many numbers.
Many searches have been made for a non 4,2,1 loop. None has ever been found, but it has never been proven that such a loop can't exist. Let's see if we can make some progress.
The 3N-1 problem (just the same as 3N+1, only the algorithm is changed in the obvious way) seems to have three loops:
1,2,1,2,1,2...
5,14,7,20,10...
17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34, ...
If there's another loop in 3N-1, it is large. [p.s.: In the 5N+1 problem, how many steps does 7 take before falling into the 1-loop or the 13-loop? :-)]
Anyway, the 3N-1 problem does not fundamentally differ from 3N+1. 3N-1 has multiple loops, why not 3N+1?
Assumption: If a loop exists in 3N+1, it is not small, since all the "small" numbers have been explicitly tested. I don't know what this bound is today, probably at least 10^15, possibly way larger.
Let's assume a non-4,2,1 loop exists. We know that it must be large. Let the smallest number in the loop be X. The loop then starts: X, 3X+1, (3X+1)/2, 3(3X+1)/2 + 1...
and we know it eventually wraps around ....4X, 2X, X.
This loop consists of M steps of X<-3X+1 and N steps of X<-X/2. We know X is big (or it would have been found already), so the addition of one to X in the 3X+1 operation really doesn't change things. If we temporarily ignore it, we can collapse all of these steps, and we'll find that:
X = X (3^M / 2^N)
Or, in other words: 3^M = 2^N. Now, of course, no integral power of three is equal to an integral power of two. But, if we can find ones that are close, maybe we can make up the difference with the addition of ones here and there.
So, we are searching for a pair of numbers M and N, probably pretty big ones, such that 2^N is just a bit bigger than 3^M, and then maybe we can make up the change with additions of one here and there. Now, let's see if we can quantify "just a bit": A bit of playing around with a spreadsheet seems to show that the difference between a bunch of steps of 3N and a bunch of steps of 3N+1 differ by a factor of (1 + 1/(2X)) where X is the starting point of the iteration. I suspect this is provable, but for now I'll just assume it and go on. If X is huge - say, on the order of 10^15 or higher (and we think it is), we need to find numbers A and B such that A log 2 ~= B log 3 (A and B are natural numbers). We have to work in log-space, the numbers are just too darn big otherwise. And, in log space, the numbers A log 2 and B log 3 better be close to equal. In fact, they better be so close that a mere double-precision variable won't be enough to discriminate between them.
One pair that my C program found (but it's nowhere near precise enough to verify) is
A=301994, B=190537
Even if we verified that the resulting numbers were close enough, we'd still have to find a starting point X (which is probably a similarly-sized number) and be able to iterate it a total of 301994+190537 = 492531 steps. Yikes! All this, for a very small chance of finding a loop.
Actually, it's "worse" than this. X is defined - or at least severely constrained to a narrow range of values - by the difference between 2^A and 3^B. And then the mod-2 parity rule has to take almost half a million steps, with a defined beginning, a defined end, a defined # of 3N+1 steps and N/2 steps, and a minimum value allowed for the entire process. It is starting to sound very unlikely!
So, I need Mathematica, or a bc program, or a high-precision C package, or I need to write one. Stay tuned.