MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

(Here I discuss the Collatz problem only for positive integers.)
It is possible, by computation, to find all cycles in the Collatz iteration of a fixed length.
It is clear that an increase must be followed by a decrease (for if $n$ is odd, then $3n+1$ is even) and a decrease can be followed by either an increase or decrease (for if $n$ is even, $\frac{n}{2}$ may be odd or even).
Using this, it is easy, for example, to show $4, 2, 1$ is the only cycle of length $3$:
Over the course of a cycle, we must have both increases and decreases. Position an increase at the beginning of the cycle. Then the changes of the cycle must be $IDD$ (where $I$ stands for increase and $D$ stands for decrease), for there is no other way to include an increase and avoid two consecutive increases. Then the cycle consists of $a, 3a+1, \frac{3a+1}{2}$, so that $a = \frac{3a+1}{4}$ and $a = 1$, leading to the familiar $1, 4, 2 = 4, 2, 1$ cycle.

For length $4$, there are two possibilities for a pattern of increase and decrease along a cycle which start with an increase: $IDID$ and $IDDD$.
The $IDID$ possibility leads to $a = \frac{9a+5}{4}$ so $a = -1$.
The $IDDD$ possibility leads to $a = \frac{3a+1}{8}$ so $a = \frac{1}{5}$. Neither of these values of $a$ is a positive integer, so there are no cycles of length $4$.

Likewise, for length $5$, there are only $3$ possibilities: $IDDDD$, $IDIDD$, and $IDDID$. Since last two are equivalent, this leads to $IDDDD$ and $IDIDD$.
$IDDDD$ leads to $a = \frac{3a+1}{16}$ so $a = \frac{1}{13}$.
$IDIDD$ leads to $a = \frac{9a+5}{8}$ so $a = -5$. So there are no cycles of length $5$.

There is more to be said for this way of considering cycles in the Collatz iteration. If a sequence of increases and decreases leads to the equation $a = Ta + U$, then $T$ is positive and $T \neq 1$, since $T = \frac{3^{m}}{2^{n}}$ for some positive integers $m, n$. The positivity of $T$ and the fact that $T \neq 1$ ensure that the solution of $a = Ta + U$ also solves (and therefore is the only solution to) $a = T(Ta + U) + U$ (or the equation for fixed points of higher-multiplicity iterates of the function $f(a) = Ta + U$), so that only cycles that form primitive circular words need to be considered (and $IDID$ was unnecessary, given how it reduces to $ID$). With this noted, it becomes very easy to handle cycles of length $6$:

The number of increases in a cycle is $1$, $2$, or $3$, since no two of them can be consecutive (and since there must be at least one increase). $3$ increases in a cycle can only be realized by $IDIDID$, which is not a primitive circular word. $2$ increases in a cycle can be realized by $IDIDDD$, $IDDIDD$, or $IDDDID$. $IDIDDD$ and $IDDDID$ are equivalent, while $IDDIDD$ is not a primitive circular word. So the only cases to consider are $IDDDDD$ and $IDIDDD$.
$IDDDDD$ leads to $a = \frac{3a+1}{32}$ so $a = \frac{1}{29}$.
$IDIDDD$ leads to $a = \frac{9a+5}{16}$ so $a = \frac{5}{7}$.
So there are no cycles of length $6$.

This is natural and simple enough that someone must have considered it before. Who has, and in what paper(s)? Also, has this been used to settle the question of whether or not there is a cycle in the positive integers larger (both in length, and in member-wise comparison) than the $4, 2, 1$ cycle?

share|cite|improve this question
Some of the earliest Internet pages on the Collatz problem refer to work done on cycle lengths. One result had a cycle length over the positive integers as being either the known cycle or else having length be large (more than 100000). A net search/should help you find it. Gerhard "Email Me About System Design" Paseman, 2011.06.24 – Gerhard Paseman Jun 24 '11 at 17:12
See… for up to date results on Collatz cycles. – Emil Jeřábek Jun 24 '11 at 17:15
What Gerhard means is probably . – Emil Jeřábek Jun 24 '11 at 17:19
Emil, I don't actually recall the paper containing the result, and I have a feeling that I am thinking of a different one. Your citation though is a good one, and I am happy to let that be the example until my memory improves. Thanks for the reference. Gerhard "Thanks For The Memory Substitutes" Paseman, 2011.06.24 – Gerhard Paseman Jun 24 '11 at 17:49
You may want to check and for an extensive overview of literature on the Collatz conjecture. One of those lists includes the reference to Simons, De Weger mentioned in the answer below, and there may be other papers relevant to your question listed there as well. – TMM Jun 25 '11 at 13:59

The cycle problem is simple enough for an amateurish approach. It is easy to find out, that a cycle must be longer than some minimal length. However, the only proof so far, which shows, that a cycle cannot occur even if arbitrary length is assumed, was done by means of transcendental number theory and the concept of rational approximation. Also, this could only be used for a special simple type of cycles. R. Steiner succeeded around [1977][3] with the first proof of this type (disproving the "1-cycle"); J.Simons 1996 and later in cooperation with Weger (since 2002)could extend this concept up to "68-cycles", a 68-fold concatenation of arbitrary long partial sequences of the same type. After that the currently best known bounds for that approximation are too weak, and Simons/deWeger assume, that finally some completely different method must be found to proceed fundamentally here.

[update] Perhaps I should make the relation of your question to the method of Steiner/Simons (and my own) clearer here.

The mentioned Steiner and Simons/deWeger theorems concern cycles of the general form: (ID)(ID)(ID)...(ID) DD...DD with u occurences of ID and d occurences of D, so u upwards steps followed by d downwards steps. To make this simpler we would denote the Steiner description with one letter, say U, for the combination ID.
So the general form were U...U D...D which is called "1-cycle" if this describes a cycle.
Then first, Steiner showed 1977 there is no cycle how many (u and d) U's (or (ID)'s in your notation) and D's in that specific arrangement occur.
Now let's denote one of that U...U D...D-constructions by $C^{u,d}$ where u again denotes the number of U and d the number of D. John Simons showed then 2004 that no cycle of the twofold concatenated form U...U D...D U...U D...D = $C^{u_1,d_1}C^{u_2,d_2}$ exists (besides of the "trivial" cycle).
The relation of your notation to the 3-, 4-, and up to the 68-cycle is then the obvious, I think.

If you look at my own article you'll find, that I reduce, for instance I DDD I DD, similarly to $b=T(a;3,2)$ - just counting the number of D's after one I, and introducing a and b as formal start- and endvalues of the full sequence of transformations, and analyze this in terms of powers of 3 and 2 as exponential diophantine expressions. This leads to very interesting (and more general) properties of the relation of powers of 2 with powers of 3.

[3]: http://???/ Steiner, R.P.; "A theorem on the syracuse problem", Proceedings of the 7th Manitoba Conference on Numerical Mathematics ,pages 553–559, 1977.

share|cite|improve this answer

Edit: Thanks to all for your comments. Because of the phrasing of the review of Eliahou's paper on MathSciNet, I was confused between the $3n+1$ and the $3n-1$ problems. But Eliahou's paper is indeed about the $3n+1$, hence is relevant to the OP. I edited my answer so that it should now make sense.

It is known that any non-trivial cycle must start after $2^{40}$, and have length $17 087 915b + kc$, where $b,c\in\mathbb{N}$ and $k\in\{301 994 , 85 137 581\}$: see Shalom Eliahou, {\it The $3x + 1$ problem: new lower bounds on nontrivial cycle lengths}. Discrete Math. 118 (1993), 45–56.

share|cite|improve this answer
Hmm? What about 5,14,7,20,10,5,... ? Another one is at 17 or 19 (if I recall right). But these two are then the only additional known ones besides the "trivial" 1,2,1,... – Gottfried Helms Jun 24 '11 at 22:12
The second was 17,50,25,74,37,110,55,164,82,41,122,61,182,91,272,136, 68,34,17,... (thanks to wikipedia) – Gottfried Helms Jun 24 '11 at 22:16
I guess Alain meant to write $3n+1$ there? As indeed, on the negative integers there are multiple known cycles and $\{1,2\}$ is not one of them. – TMM Jun 25 '11 at 13:27
Hmm, maybe the problem is already at Eliahou: I had a similar controverse in wikipedia, where someone stated the same idea, culminating in the sentence, that for 3n-1 the problem was solved. So there may be some urban legend around and I tried to look into the article of Eliahou. Unfortunately I can't get it online and our university-lib does not provide the "discrete mathematics" journal. So it is -unfortunately- too much hazzle for me to verify the origin of that statement at the moment - maybe someone else has the opportunity to look at "Eliahou/Discrete Math 118"? – Gottfried Helms Jun 25 '11 at 19:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.