The 3x+1 problem concerns an iterated function and the question of whether it always reaches 1 when starting from any positive integer. It is also known as the Collatz problem or the hailstone problem.
For example, 
. And 
. This leads to the sequence 3, 10, 5, 16, 4, 2, 1, 4, 2, 1, ... which indeed reaches 1. A sequence obtained by iterating the function from a given starting value is sometimes called "the trajectory" of that starting value.
Obviously there can be no consecutive odd numbers in any trajectory, but there may certainly be consecutive even numbers, especially when the trajectory reaches a power of 4, in which the trajectory quickly plummets to 1 after passing through all the intervening powers of 2. (Note that since the odd-indexed powers of 2 are congruent to 2 modulo 3, they are only reachable from halving a power of 4).
What is not so obvious is whether every trajectory eventually reaches a power of 4.
Pure hailstone numbers are those which do not occur in the trajectories of smaller numbers, while impure hailstone numbers are those which do occur in the trajectories of smaller numbers.
The Collatz conjecture stipulates that all 3x+1 problem trajectories eventually hit a power of 2 (thus falling straight down to 1, like hailstones.)
The number of halving and tripling steps for 
to reach 1 in 3x+1 problem (Cf. A006577) is
until known
until 1
to 1
(A127933)
(for n = 97)
A008908 gives the number of steps needed for 
to reach 1, while A006666 and A006667 give the number of halving steps and the number of tripling steps respectively. The numbers with a record number of steps are given by A006877.
A135282 records the largest exponent 
such that 
appears in the trajectory started with . It is believed that these exponents are only odd when itself is 
odd. That would mean, if the "conjecture" is true, that a given odd-indexed power of 2 is unreachable by iteration of the Collatz function, if you don't start with that given odd-indexed power of 2 initially. If we call the powers of 2, 
, the trivial argument values of the Collatz function (which trivially fall down to 1 in steps,) the "conjecture" would imply that for every nontrivial argument values of the Collatz function we must reach a power of 4 (even-indexed power of 2) for the Collatz conjecture to be true.
For the limited list provided in A135282, i.e. 
[1..105], if we consider only the non-trivial argument values of , thus not 2, it seems that the largest is predominantly 4, a few times 6 for {21, 42, 84} (is it continuing as 126, 168, ...?) and 8 for {75, 85} (is it continuing as 155, 165, ...?). In A135282, Masahiko Shin mentions that most of the first ten thousand terms are 4, and there only appear 4,6,8,and 10 in the extent (there are few exceptional terms, for example a(10920)=12, a(10922)=14,) unless is a power of 2, and it seems all terms are even, unless is an odd-indexed power of 2. For non-trivial argument values, it thus seems that the hailstones' final fall is essentially the result of hitting very low powers of 4 (even-indexed powers of 2.) It would be interesting to know, for a typical non-trivial argument value, whether the hailstone went through few big drops big hitting numbers with high evenness or went through many small drops big hitting numbers with low evenness, before it ended up hitting one of those very low powers of 4. Or it might be that for each non-trivial argument we obtain a hailstone history containing both situations in a very intricate way.
Sequences generated by iterating the Collatz function seemingly reach unpredictable heights.[1] Some starting values give sequences that jump up sharply, then come down and fluctuate in the neighborhood of the starting value before hitting a power of 2 and then proceeding predictably towards 1.
Thus the term "hailstone" is sometimes used to refer to this problem. But there are also starting values that don't jump up significantly until much later on, closer to the final fall. A025586 gives the largest value encountered in such sequences starting with each in turn, while A033493 gives the sum of all values in such a sequence from to the first instance of 1.
Since the powers of two give an element of predictability, it is natural that a tree graph of Collatz sequences put the powers of two on the central axis, or at least line them up.
In the tree graph above, halving steps are denoted by black lines, while blue lines signify tripling steps (plus the addition of 1). The top numbers of each column above can be found in A033491, though of course going from 
forward rather than backwards from 
.
until known
until 1
to 1
(A??????)
Paul Erdős said about the Collatz conjecture: "Mathematics is not yet ready for such problems." He offered $500 USD for its solution.[2] A generalization of the 
problem has been shown to be a computationally unsolvable problem.[3]
Computers, being generally unable to recognize an infinite loop, usually have f(1):= 1 hard-coded in investigations of this problem,[4] or they might get stuck in the 4, 2, 1 cycle.
But of course in the search for a counterexample to the Collatz conjecture, they would have to be programmed to keep track of previous numbers encountered in the sequence to compare them against new values. Regardless, the computer would first have to be directed to a specific number after a human mathematician determined the properties the counterexample would need to have.
Obviously a counterexample, if it exists, must not be a power of 2. But how can we know a given number's sequence will not reach a power of 2? By allowing to be negative, some possibilities are suggested: not all sequences for negative values of reach 
. Sequences for some values, such as 
, eventually enter this loop:
(Allowing 
is equivalent to changing the "tripling step" to 
while maintaining the restriction to positive numbers; see A008894).
