Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


Consider Collatz-type problems of the form $an + 1$, where $a > 2$ is a positive, odd integer (e.g., $3n + 1$, $5n +1 $, $7n + 1$, etc.). For convenience, automatically divide by two.

The $3n + 1$ problem has a single known positive cycle $(1, 2)$. This cycle has period $2$, and the maximum value this cycle obtains differs from its minimum value by a power of two; that is $2 = 2 \cdot 1$.

The $7n + 1$ problem has a positive cycle $(1, 4, 2)$. This cycle has period $3$, and the maximum value $4 = 2^2 \cdot 1$ is the minimum value multiplied by some power of two.

The $5n + 1$ problem has three positive cycles: $(1, 3, 8, 4, 2)$, $(13, 33, 83, 208, 104, 52, 26)$, and $(17, 43, 108, 54, 27, 68, 34)$. The first cycle has period $5$, and its maximum $8 = 2^3 \cdot 1$. The other two cycles have period $7$, and one of these $7$-cycles has a maximum value $208 = 2^4 \cdot 13$.


Is it known whether the existence of a positive $m$-cycle in such a Collatz-type problem implies the existence of a positive $m$-cycle such that its maximum $M$ and its minimum $\mu$ are related by $M = 2^k \mu$, for some $k \in \mathbb{N}$?


I used $m$-cycle to denote a cycle of period $m$ when it has already been standardized that $m$-cycle means a cycle with $m$ local minima. Either affirmative answer would serve just as well, however.

Question 2

Does the existence of a nontrivial (positive) cycle in the $3n+1$ problem imply the existence of a nontrivial (positive) cycle with maximum $M$ and minimum $m$ such that $M = 2^k m$, for some $k \in \mathbb{N}$?

Note: If you prefer to work with the odd-only transformation, the condition would be that the maximum element transforms into the minimum element.

share|improve this question
For 1-cycles, and some odd a, yes. For larger cycles, my guess is not only that it isn't known but that for many a it is not true. I would expect the same for an+b, but don't rely on my intuition. Gerhard "Ask Me About System Design" Paseman, 2011.10.14 –  Gerhard Paseman Oct 14 '11 at 14:59
What did you mean with "m-cycle"? (There is already a convention for that term in Simons/deWeger but I can't imagine you're referring to this here) <hr> J.Simons/B.de Weger: Theoretical and computational bounds for m-cycles of the 3n + 1 problem version 1.0, November 18, 2003 win.tue.nl/~bdeweger/3n+1_v1.0.pdf (newer versions available) –  Gottfried Helms Oct 15 '11 at 18:35
a better link (taken from [wikipedia][1] should be deweger.xs4all.nl/papers/… [1]: en.wikipedia.org/wiki/Collatz_conjecture –  Gottfried Helms Oct 15 '11 at 18:40
This is stupid but shouldn't the 7-cycle (1,2,4) be (1,4,2)? Am I missing something? –  Will Sawin Oct 17 '11 at 3:57
add comment

1 Answer

[update 2] Rereading the question after my own answer I note, that the doubly used symbol m for length of a series of collatz-transformation and the m for the minimal element (M for the maximal) irritated me and made me misunderstanding the question.
Anyway - the already given answer might be interesting for the background of my argument below as well as for further analysis of the problem at hand, so I'll leave it here for the cursory reader.

To answer the real question : "is there some requirement, that in a cyclic Collatz-trajectory the maximal element is a perfect-power-of-2-multiple of the minimal element (M=2^k m) ?" : there is no such requirement to all my knowledge.
Also this would only define a single special case according to my notation for a cycle, which by convention might begin with the smallest element m : $\small m = T(m; A_1,A_2,\ldots ,A_{n-1},A_n) $.
Here your requirement simply means, that the maximal element M must occur after the transformation $\small A_{n-1} $ (whose exponent must thus equal 1) frome where then the $\small A_n$ is the k in M=2^k m in your question. I didn't come across such a restriction in my own study or in any seen literature, and cannot see any reason for it (see derivations below). [end update 2]

If you write a collatz-transformation this way $ \small a_{k+1} = (3 a_k + 1)/2^A $ where A is the number of all following even (divide-by-2) steps, then also all $\small a_k$ must be odd.

With this write for one transformation $\small a_{k+1} = T(a_k;A) $ and for more $\small a_{k+m} = T(a_k;A_1,A_2,\ldots,A_m) $.
For $\small A=1 $ these steps are increasing and if $\small A>1$ the steps are decreasing.

A cycle occurs, if $\small a_m=T(a_0;A_0,A_1,\ldots,A_m) = a_0 $ thus $\small a_m = a_0 $.

Now let's look at two different types of cycles - the "general" one, where the exponents $\small A_k $ have no a priori restriction, and the "primitive" one, where all but the last $ \small A_k = 1 $, thus $\small a_0 = T(a_0;1,1,1,1,\ldots,1,A) $ with say $\small N-1 $ times 1 and only one $\small A_{N} \gt 1$

For the primitive cycle of the length N the smallest element $\small a_0 $ must have the form $\small a_0 = 2^{N-1} \cdot 2w - 1$ where w is some positive odd integer and that primitive cycle increases then up to $\small a_{N-1} = 3^{N-1}\cdot 2w-1 $ from where it must decrease by a consecutive set of A "even" transformations.

The proof of Ray Steiner (and the subsequent proofs of J.Simons and B.de Weger) use that requirement of the "primitive cycle" (in their nomenclature "1-cycle", see wikipedia) to show that such a cycle cannot exist except $\small a_0 = T(a_0;2) \qquad a_0=1 $ (where no exponents of value 1 occur - the degenerate case (also called "circuit").

For the general cycle this is much more complicated and does definitely not have the properties which you sketch in your op.

[added] Answering to the comment. A characterization of the general cycle of m collatz-steps (m=N + S in my notation, where I refer -writing "steps"- to the number N of abbreviated steps $\small T(a;A)$

Assume again one step as on the form $\small a_{k+1} = (3 a_k +1)/2^{ A_k} = T(a_k;A_k) $. Then to have a cycle this means (ignore the index k here) $\small a=(3a +1)/2^A $ and also $\small 2^A=(3a +1)/a = (3 + 1/a) $ This can only be solved if a=1 and A=2, so there is only one general-cycle of length N=1, S=2 and m=N+S=3 and we see a characteristic of the exponent A, which is much descriptive: the number of even steps of the original notation of the collatz-transformation is 2.
Now we assume a 2-step cycle $\small a = T(a;A,B) $ and dissolve this in two steps: $\small b=T(a;A) \qquad a=T(b;B) $ thus $\small b = (3 a +1)/2^A \qquad a=(3b+1)/2^B $. I'm used to write S for the sum A+B meaning the whole number of even steps, and N for the number of "odd steps", both wrt the original Collatz-notation, and in my notation N is the number of steps (and the power of 3 involved). If we write the (trivial) product of the two involved elements a and b in their direct notation and in their transformed expression we get $\small a\cdot b = (3b+1)/2^A \cdot (3a+1)/2^B $ and this can be rewritten as $\small 2^{A+B} = (3+1/a)(3+1/b) $ This is an interesting form and easily generalized for the analysis with bigger N (and respectively m) . Here we see, that a 2-step general cycle can only exist if $\small (3+1/a)(3+1/b) $ is a perfect power of 2; now considering the whole set of odd positive integers for a and b we see, that that product can vary only between $\small 9 \ldots 16 $ and thus must be S=A+B=4 and this requires a = b = 1 and thus A=B=2 (which is then only a concatenation of the trivial cycle $\small 1=T(1;2,2) $ . Here m=N+S=2+4=6 .

This way you may proceed studying longer assumed cycles. For instance it shows that the whole distance between two numbers $\small a_k - a_j = 2^S$ where S is the number of even transformations can never occur because there are always "odd Collatz steps" interspersed; even less can the distance between the minimal and maximal member of a loop be $\small 2^{N+S} = 2^m $, which were the whole length of the cycle in the counting of original Collatz-steps.

This formula describes pretty well important properties of the exponents of 2 in relation to the length of a "general cycle" , so it might be useful for the answering of your question. However - I can't relate anything in that formula to the asked property of a connection between the distance minimal...maximal member and 2^m where m is the number of all Collatz steps and actually is $\small m=S+N$ nd so I think there is none.

Addendum : It might be interesting to look at the existing cycles in the domain of negative odd numbers; they can also be identified using the procedere exercised above. The 2-step cycle was $\small 2^{A+B} = (3+1/a)(3+1/b) $ and allowing negative a and b gives the example: $\small 2^{A+B} = (3-1/5)(3-1/7) = {14 \over 5} \cdot {20 \over 7} = {8 \over 1} = 2^3 $ which is a perfect power of 2 as required. Then $\small A+B=3$ and one of them must equal 1. In fact we have the 2-step-cycle $\small -5=T(-5;1,2) $

Finally: a short treatize using the notation here is in that article of mine

1 Steiner,R.P.; A theorem on the syracuse problem, Proceedings of the 7th Manitoba Conference on Numerical Mathematics,pages 553...559, 1977

share|improve this answer
add comment

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.