The 3n+1 problem

The system described here is similar to the so-called 3n+1 problem, in which one looks at the rule n  If[EvenQ[n], n/2, (3n + 1)/2] and asks whether for any initial value of n the system eventually evolves to 1 (and thereafter simply repeats the sequence 1, 2, 1, 2, ...). It has been observed that this happens for all initial values of n up to at least 10¹⁶, but despite a fair amount of mathematical effort since the problem was first posed in the 1930s, no general proof for all values of n has ever been found. (For negative initial n, the evolution appears always to reach -1, -5 or -17, and then repeat with periods 1, 3 or 11 respectively.) An alternative formulation is to ask whether for all n

FixedPoint[(3#/2^IntegerExponent[#, 2] + 1)/2 &, n]  2

With the rule n  If[EvenQ[n], 5n/2, (n + 1)/2] used in the main text, the sequence produced repeats if n ever reaches 2, 4 or 40 (and possibly higher numbers). But with initial values of n up to 10,000, this happens in only 642 cases, and with values up to 100,000 it happens in only 2683 cases. In all other cases, the values of n in the sequence appear to grow forever.

To get some idea about the origin of this behavior, one can assume that successive values of n are randomly even and odd with equal probability. And with this assumption, n should increase by a factor of 5/2 half the time, and decrease by a factor close to 1/2 the rest of the time—so that after t steps it should be multiplied by an overall factor of about (√5/2)^t. Starting with n = 6, the effective exponents for t = 10^Range[6] are {39.6, 245.1, 1202.8, 9250.7, 98269.8, 1002020.4}. One reason that all sequences do not grow forever is that even with perfect randomness, there will be fluctuations, and occasionally n will reach a low value that makes it get stuck in a repetitive sequence.

If one applies the same kind of argument to the standard 3n+1 problem, then one concludes that n should on average decrease by a factor of √3/2 at each step, making it unsurprising that at least in most cases n eventually reaches the value 1. Indeed, averaging over many initial values of n, there is good quantitative agreement between the predictions of the randomness approximation and the actual 3n+1 problem. But since there is no fundamental basis for the randomness approximation, it is still conceivable that a particular value of n exists that does not follow its predictions.

The pictures below show how many steps are needed to reach value 1 starting from different values of n. Case (a) is the standard 3n+1 problem. Cases (b) and (c) use somewhat different rules that yield considerably simpler behavior. In case (b), the number of steps is equal to the number of base 2 digits in n, while in case (c) it is determined by the number of 1's in the base 2 digit sequence of n.