Back to index

Introduction

The 3n+1 or Collatz conjecture states that the iteration of

C(n) = \left\lbrace \begin{array}{ll} 3n+1 & \mbox{if $n$ is odd} \\ n/2 & \mbox{if $n$ is even} \end{array} \right.

starting from any natural number, will always reach 1. (Further iteration will enter the cycle 1 \rightarrow 4 \rightarrow 2 \rightarrow 1.)

Previous work since Terras [5] would acknowledge that 3n+1 is always even whenever n is odd, and iterate instead

T(n) = \left\lbrace \begin{array}{ll} (3n+1)/2 & \mbox{if $n$ is odd} \\ n/2 & \mbox{if $n$ is even} \end{array} \right.

We will not be doing this here, as we are interested in counting how many times the n/2 rule is applied between each application of the 3n+1 rule. In this spirit, we could alternatively iterate a function (previously removing a power of 2, if the initial number is even) like

f(n) = \frac{3n+1}{2^{c_i}}

where c_i is, at each iteration, the exponent of 2 in the unique prime factorization of 3n+1. Note that the result of f(n) is always coprime to 3.

Stating the problem in reverse, we may start at 1 and ask whether all odd naturals can be reached by the iteration of

g(n,c_i) = \frac{2^{c_i}n - 1}{3}

where an appropriate positive c_i would need to be supplied at each iteration; at the very end, you may multiply by yet another power of 2, in order to yield even numbers. Note again that a multiple of 3 will not iterate any further, if you expect the result to be an integer.



A formula for the reverse iterates of the Collatz function

Substitution of m iterations of g(n,c_i) leads to the following expression for any n that can be reached from 1 in m iterations of the function g:

$ { \setlength{\fboxrule}{1pt} \setlength{\fboxsep}{8pt} \fcolorbox{blue}{white} { $ n = \frac{2^{a_m} - \displaystyle\sum_{i=0}^{m-1} \, 2^{a_i} \, 3^{m-1-i}}{3^m} \qquad (1) $ } } $

where the a_i are partial sums of the c_i (a_0 = c_0, ~a_1 = c_0+c_1, ~a_2=c_0+c_1+c_2,  etc.), thus strictly increasing.

Equation (1) has been seen elsewhere [2]. The "remainder representation" in Terras [5] (Theorem 1.1) is a covert version of equation (1).

As an example, consider starting with n=136; after initially dividing by 2^3 to obtain 17, iteration from f(17) will yield

f(17) = \frac{52}{2^2} = 13, \quad f(13) = \frac{40}{2^3} = 5, \quad f(5) = \frac{16}{2^4} = 1

or, in reverse,

g(1,4) = 5, \quad g(5,3) = 13, \quad g(13,2) = 17

and finally multiplying by 2^3 to get 136. In this example, c_3,c_2,c_1,c_0 are resp. 4,3,2,3, and a_3,a_2,a_1,a_0 are 12,8,5,3, so that

136 = \frac{2^{12} - (2^8 + 3 \cdot 2^5 + 9 \cdot 2^3)}{27}

Odd numbers would have a_0=0.

Conversely, if a number n is expressible as in (1), then n will reach 1 via iteration of the Collatz function: assume that we start with \displaystyle\frac{n}{2^{a_0}}, and initially subtract a_0 from all exponents of 2 in equation (1) (thus, to simplify the notation, we start with an odd number n, and renamed a_i with a_0=0); it is easy to verify that, if m > 0, then

3n+1 = 2^{a_1} \Bigg(~~ \frac{2^{a'_{m-1}} - \displaystyle\sum_{i=0}^{m-2} \, 2^{a'_i} \, 3^{m-2-i}}{3^{m-1}} ~~\Bigg)

where a'_i = a_{i+1} - a_1, and a'_0 is still 0. This procedure can be repeated (using the fraction in parentheses as the next odd number n) until the sum (from 0 to -1) has no terms, and the fraction is just 2^0/3^0=1.

Equation (1) encodes a path from n to 1, straightforward to decode from the differences between the a_i exponents.

Sums of the form \displaystyle\sum_{i=0}^k 2^{a_i} 3^{k-i} were termed special 3-smooth representations of level k by the authors of [1]. These sums can be systematically built as subsets of the collection of powers of 2 up to and including 2^{a_k}. 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.)



Multiplicative groups modulo powers of 3

An interesting feature of equation (1) is that it is the expression of a congruence: the fraction is an integer if and only if

2^{a_m} \equiv \displaystyle\sum_{i=0}^{m-1} 2^{a_i} 3^{m-1-i} \pmod{3^m}

As it turns out, all multiplicative groups modulo powers of 3 are cyclic, and have 2 as a primitive root [3].

Leaving aside the case m=0 (which reduces to a trivial congruence modulo 1), when m > 0 the sum on the right-hand side is coprime to 3, since it contains at least the term 2^{a_{m-1}} and all other possible terms are multiples of 3.

The exponent of 2 on the left, then, is an index (a discrete logarithm modulo 3^m) for the result of the sum on the right-hand side.

From this it follows that, if n can be reached from 1 and is thus expressible as in equation (1), then the following family of numbers is also reachable from 1:

\frac{2^{a_m + k\varphi(3^m)} - \displaystyle\sum_{i=0}^{m-1} 2^{a_i} 3^{m-1-i}}{3^m}

for any k \ge 0, where \varphi stands for Euler's totient function.



Website notation

Over this website, we shall abuse the shorthand

n = \lbrace a_m, a_{m-1}, a_{m-2}, \ldots, a_2, a_1, a_0 \rbrace

to represent an expression for n as in $ { \setlength{\fboxrule}{1pt} \fcolorbox{blue}{white} { equation $(1)$ } } $ above,

n = \frac{2^{a_m} - \left(2^{a_{m-1}} \, 3^0 + 2^{a_{m-2}} \, 3^1 + \ldots + 2^{a_1} \, 3^{m-2} + 2^{a_0} \, 3^{m-1} \right)}{3^m}

where m is given by the length of the bracketed sequence minus 1.

As examples,

1 = \lbrace & 0 \rbrace = 2^0/3^0 \\ 3 = \lbrace & 5,1,0 \rbrace = \frac{2^5 - (2^1 + 3)}{9} \\ 22 = \lbrace & 11,7,4,2,1 \rbrace = \frac{2^{11} - (2^7 + 3 \cdot 2^4 + 9 \cdot 2^2 + 27 \cdot 2^1)}{81} \\ 27 = \lbrace & 70,66,61,60,59,56,52,50,48,44,43,42,41,38,37,36,35,34,33,31, \\ & 30,28,27,26,23,21,20,19,18,16,15,14,12,11,9,7,6,5,4,3,1,0 \rbrace \qquad (\mbox{with } m=41)

and a sequence like 11 = \lbrace 10,6,3,1,0 \rbrace is the first instance of a family that continues with

227737581156908043 &= \lbrace ~~ 64,6,3,1,0 \rbrace \\ 4102555542546036644764836605803531 &= \lbrace 118,6,3,1,0 \rbrace \\ 73905070450708374727929544133406114179144440691723 &= \lbrace 172,6,3,1,0 \rbrace \qquad \ldots

where the first number a_4 in the sequence increases by \varphi(3^4) = 54.

The following list contains representations for all numbers between 1 and 99999.

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


References

  1. R. Blecksmith, M. McCallum, J. L. Selfridge, 3-smooth representations of integers. Am. Math Monthly 105(6), 1998.

  2. Corrado Böhm, Giovanna Sontacchi, On the existence of cycles of given length in integer sequences like x_{n+1} = x_n/2 if x_n even, and x_{n+1} = 3x_n + 1 otherwise. Atti Accad. Naz. Lincei, Rend. Cl. Sci. Fis. Mat. Natur. 8(64), 1978.

  3. David M. Burton, Elementary number theory. 6th ed., McGraw-Hill, 2007; see the proof of Theorem 8.9.

  4. Jeffrey C. Lagarias, The 3n+1 problem and its generalizations. Am. Math Monthly 92(1), 1985.

  5. Niho Terras, A stopping time problem on the positive integers. Acta Arith. XXX, 1976.