or Collatz conjecture states that the iteration of
The or Collatz conjecture states that the iteration of
starting from any natural number, will always reach 
.
(Further iteration will enter the cycle 
.)
Previous work since Terras [5] would acknowledge that is always even
whenever 
is odd, and iterate instead
We will not be doing this here, as we are interested in counting
how many times the 
rule is applied between each application of the rule.
In this spirit, we could alternatively iterate a function
(previously removing a power of 
, if the initial number is even)
like
where 
is, at each iteration, the exponent of in the unique prime factorization of .
Note that the result of 
is always coprime to 
.
Stating the problem in reverse,
we may start at and ask whether all odd naturals can be reached
by the iteration of
where an appropriate positive would need to be supplied at each iteration;
at the very end, you may multiply by yet another power of , in order to yield even numbers.
Note again that a multiple of will not iterate any further,
if you expect the result to be an integer.
Substitution of 
iterations of 
leads to the following expression for any that can
be reached from in iterations of the function 
:
where the 
are partial sums of the
(
, 
, 
, etc.), thus strictly increasing.
Equation 
has been seen elsewhere [2].
The "remainder representation" in Terras [5] (Theorem 1.1)
is a covert version of equation .
As an example, consider starting with 
;
after initially dividing by 
to obtain 
,
iteration from 
will yield
or, in reverse,
and finally multiplying by to get 
.
In this example, 
are resp. 
,
and 
are 
,
so that
Odd numbers would have 
.
Conversely, if a number is expressible as in ,
then will reach via iteration of the Collatz function:
assume that we start with 
,
and initially subtract 
from all exponents of in equation
(thus, to simplify the notation, we start with an odd number , and renamed with );
it is easy to verify that, if 
, then
where 
, and 
is still 
.
This procedure can be repeated (using the fraction in parentheses as the next odd number )
until the sum (from to 
) has no terms, and the fraction is just 
.
Equation encodes a path from to , straightforward to decode
from the differences between the exponents.
Sums of the form 
were termed special 3-smooth representations of level 
by the authors of [1].
These sums can be systematically built as subsets of the collection of powers of up to and including 
.
But notice that this is different from Terras' statements on periodicity (Theorem 1.2 and Corollary 1.3 in [5]),
also in Theorem B on Lagarias [4]. (A future page will elaborate on this.)
An interesting feature of equation is that it is the expression of a congruence:
the fraction is an integer if and only if
As it turns out, all
multiplicative groups modulo
powers of are cyclic,
and have as a primitive root [3].
Leaving aside the case 
(which reduces to a trivial congruence modulo ),
when the sum on the right-hand side is coprime to ,
since it contains at least the term 
and all other possible terms are multiples of .
The exponent of on the left, then, is an index (a discrete logarithm modulo 
)
for the result of the sum on the right-hand side.
From this it follows that, if can be reached from and is thus expressible as in equation ,
then the following family of numbers is also reachable from :
for any 
, where 
stands for
Euler's totient function.
Over this website, we shall abuse the shorthand
to represent an expression for
as in
above,
where is given by the length of the bracketed sequence minus .
As examples,
and a sequence like 
is the first instance of
a family that continues with
where the first number 
in the sequence increases by 
.
The following list contains representations for all numbers between and 
.
| 1 to 9999 | 10000 to 19999 | 20000 to 29999 | 30000 to 39999 | 40000 to 49999 |
| 50000 to 59999 | 60000 to 69999 | 70000 to 79999 | 80000 to 89999 | 90000 to 99999 |
R. Blecksmith, M. McCallum, J. L. Selfridge, 3-smooth representations of integers. Am. Math Monthly 105(6), 1998.
Corrado Böhm, Giovanna Sontacchi,
On the existence of cycles of given length
in integer sequences like 
if 
even,
and 
otherwise.
Atti Accad. Naz. Lincei, Rend. Cl. Sci. Fis. Mat. Natur. 8(64), 1978.
David M. Burton, Elementary number theory. 6th ed., McGraw-Hill, 2007; see the proof of Theorem 8.9.
Jeffrey C. Lagarias, The 3n+1 problem and its generalizations. Am. Math Monthly 92(1), 1985.
Niho Terras, A stopping time problem on the positive integers. Acta Arith. XXX, 1976.