cp's OEIS Frontend

The 3x+1 or Collatz problem is as follows: start with any number n. If n is even, divide it by 2, otherwise multiply it by 3 and add 1. Do we always reach 1? This is a famous unsolved problem. It is conjectured that the answer is yes.

It seems that about half of the terms satisfy a(i) = a(i+1). For example, up to 10000000, 4964705 terms satisfy this condition.

n is an element of row a(n) in triangle A127824. - Reinhard Zumkeller, Oct 03 2012

The number of terms that satisfy a(i) = a(i+1) for i being a power of ten from 10^1 through 10^10 are: 0, 31, 365, 4161, 45022, 477245, 4964705, 51242281, 526051204, 5378743993. - John Mason, Mar 02 2018

5 seems to be the only number whose value matches its total number of steps (checked to n <= 10^9). - Peter Woodward, Feb 15 2021

See A075677 for the function R applied to the odd numbers once. The 3x+1 conjecture asserts that a(n) is a finite number for all n. The function R applied to the odd numbers shows the essential behavior of the 3x+1 iterations.

Bisection of A006667. - T. D. Noe, Jun 01 2006

Here we call the starting value iteration number 1, although usually the count is started at 0, which would subtract 1 from the values for n >= 2 - see A060445, A102419.

The (3x+1)/2 steps and the halving steps are counted. - Don Reble, May 13 2006

Where records occur in A102419 (could be prefixed by an initial 1). - N. J. A. Sloane, Oct 20 2012

We count only the 3x+1 steps of the usual Collatz iteration. We stop counting when the iteration produces a number less than the initial 2n+1. For a fixed dropping time k, let N(k)=A100982(k) and P(k)=2^(A020914(k)-1). There are exactly N(k) odd numbers less than P(k) with dropping time k. Moreover, the sequence is periodic: if d is one of the N(k) odd numbers, then k=a(d)=a(d+i*P(k)) for all i>=0. This periodicity makes it easy to compute the average dropping time of the reduced Collatz iteration: Sum_{k>0} k*N(k)/P(k) = 3.492651852186... (A122791).

Only these numbers appear in A060445, which tabulates the "dropping time" of odd numbers. Note that all even numbers have a "dropping time" of 1.

a(n) is also the number of binary digits of 6^(n-1); for example, a(4)=8 since 6^(4-1)=216 in binary is 11011000, an 8-digit number. - Julio Cesar de la Yncera, Mar 28 2009

A positive integer (x) is an allowable value if and only if (x-1)/(1+log(2)/log(3)) - floor(x/(1+log(2)/log(3))) is not negative. - K. Spage, Oct 22 2009

Here the word "allowable" means that it is necessary for a sequence of iterates starting from odd value m to arrive at a value x = f^{floor(1+n+n*log(3)/log(2))}(m) < m, where n gives the number of odds in such a sequence including m, to have undergone precisely floor(1+n+n*log(3)/log(2)) iterations of f, where f(2*m)=m, f(2*m+1)=6*m+4. However, the formula for a(n+1) does not fully account for the order of odds and evens in such a sequence because it does not account for the effects of the "+1". Thus it is unknown whether it maximizes the value x for all values m. For example, fix m = 1 and the "+1" is enough to give the trivial cycle. So it is possible that for some m we have f^{floor(1+n+n*log(3)/log(2))}(m) >= m. - Jeffrey R. Goodwin, Aug 24 2011

The indices of the powers of 3 in A006899. - Ruud H.G. van Tol, Nov 02 2022

The dropping time is the number of Collatz iterations required to reach a lower number than starting value. Garner mentions these congruences. The first term in row n is A122442(n+1) for n > 1. The length of row n is A100982(n).

The triangle means:

numbers 0 (mod 2) and > 0 have dropping time 1;

numbers 1 (mod 4) and > 1 have dropping time 3;

numbers 3 (mod 16) have dropping time 6;

numbers 11, 23 (mod 32) have dropping time 8;

numbers 7, 15, 59 (mod 128) have dropping time 11;

numbers 39, 79, 95, 123, 175, 199, 219 (mod 256) have dropping time 13.

Theorem: a(n) can be evaluated using a directed rooted tree produced by a precise algorithm. Each node of this tree is given by a unique Diophantine equation whose only positive solutions are the integers with a finite stopping time. The algorithm generates (in a three step loop) the parity vectors which define the Diophantine equations. The two directions of the construction principle gives the tree a triangular form which extends ever more downwards with each column. There exist explicit arithmetic relationships between the parent and child vertices. As a consequence, a(n) can be generated algorithmically. The algorithm also generates A100982. - Mike Winkler, Sep 12 2017

If the "1" is omitted, also records in A060445.