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

Everybody has heard of the Collatz conjecture and it is a nice programming exercise to write a function, that calculates for a given number $n$ the number of iterations it takes until one reaches $1$. However if one restricts to numbers of the form $2^n+1$ one gets the following sequence of integers (NO matches in oeis). It starts with

7,5,19,12,26,27,121,122,35,36,156,113,52,53,98,99,100,101,102, 72,166,167,168,169,170,171,247,173,187,188,251,252,178,179,317, 243,195,196,153,154,155,156,400,326,495,496,161,162,331,332,408, 471,410,411,337,338,339,340,553,479,480,481,482,483,559,560,561, 562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,626, 578,628,629,630,631,583,584,634,635,636,637,894,895,640,641,898,643

"Usually" it grows by $1$ and at some positions it takes a completely different value. Then sometimes it jumps back as if there was never a different value involved (like 575,576,626,578) This seemed to me a bit strange/interesting and funny.It there anything known about this special sequence. Maybe there is a characterization of those positions, where this sequence grows by $1$. I am not sure, how to make a well posed question out of this.

EDIT: and there is the same behavior for numbers of the form $2^n-1$

share|improve this question
I'm sorry -- I feel a little stupid -- but I am not understanding this. Let me ask a dumb question: why does this start with 7, and why is 5 the next number? –  Todd Trimble Jan 4 '11 at 15:55
Because starting with 3 takes 7 steps to get to 1, and starting with 5 takes 5 steps. –  Thomas Bloom Jan 4 '11 at 15:58
After $4 k= 4*\lfloor \frac{n}{2}\rfloor$ steps, you end up with either $3^k+1$ or $2*3^k +1$, with the former if $n$ is even and the latter if $n$ is odd. There seem to be some interesting relations between Collatz sequences of these numbers, but I'm not an expert at all, so I know nothing of research done in this field. Same holds for $2^n -1$, ends up at $3^k-1$ or $2*3^k -1$ after same $k$ steps. –  Jan Jitse Venselaar Jan 4 '11 at 16:23
Thank you, Thomas. –  Todd Trimble Jan 4 '11 at 16:37
Henrik, your question has produced a new sequence on oeis :-) oeis.org/A179118 –  Martin Brandenburg Jun 8 '11 at 6:51

1 Answer 1

You can find some closed formulas resembling your problem in

Andrei, S., Kudlek, M., Niculescu, R., S.: Some results on the Collatz problem. Acta Informatica No. 37, Vol. 2, pp. 145-160 (2000)


Hope it helps.

EDIT: (To complement the answer) You should also check the references in the chapter I.8 ``Consecutive numbers with the same height" in

The Dynamical System Generated by the 3n +1 Function - Gunther J. Wirsching - Lec. Notes in Mathematics v. 1681

There you'll find that there is a infinite number of very long sequences of consecutive numbers for which your Collatz function is constant, which is also very interesting.

share|improve this answer

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.