Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

I am writing an undergraduate paper on the $3n+1$ problem, and I am looking for some theorems related to the problem that would be reasonable for someone with my mathematical background to prove. I'm near the end of my undergraduate studies. I have had a pretty basic introduction to Number Theory and Group Theory. I have also taken a few introductory Computer Science courses. Those are the only courses that I've taken that seem to be relevant to the problem but otherwise my math classes have been: the usually calculus sequence, real analysis, introductory topology, linear algebra.

A good answer to my question would do the following:

  • Either state one or more non-trivial theorems related to the Collatz conjecture, or reference sources that would contain this kind of information.
  • Would NOT state any proofs unless a proof or partial proof would be essential for someone with my requisites if they are to be able to provide a full proof.

Theorems that I have already proved:

If $L(n)$ is a function that counts the number of mappings in the Collatz function for $n$ to get to 1, then if $n = 8k+4$, $L(n) = L(n+1)$.

If $n = 128k+28$ then $L(n) = L(n+2)$.

share|cite|improve this question
Since your two results imply that for $n = 128k + 28$, $L(n) = L(n+1) = L(n+2)$, it would be interesting to know if you could push that farther for consecutive $n$ of a particular form. I am not familiar with all of the literature (I have read Lagarias' paper, but several years ago), so I am not sure if there are known results in this direction. If not, I think that would be a very interesting direction to take your research -- either finding such blocks of integers, or showing that block size is nontrivially limited. – Eric Tressler May 13 '13 at 5:21
Your two theorems can easily be generalized and lead to a full partitioning scheme of the natural numbers with equivalent mapping-statements. See a compilation in my treatize in which is amateurish but I think it fits your needs, considering the target and prerequisites that you mention... – Gottfried Helms May 13 '13 at 5:58
up vote 6 down vote accepted

The starting point for the literature is the survey by Jeff Lagarias ten years ago:

[math/0309224 The 3x+1 problem: An annotated bibliography (1963--1999) (sorted by author). Jeffrey C. Lagarias. math.NT (math.DS).

Other papers from an arxiv Front search for Collatz and 3x+1:

math/0608208 The 3x+1 Problem: An Annotated Bibliography, II (2000-2009). Jeffrey C. Lagarias. math.NT (math.DS)

arXiv:0910.1944 Stochastic Models for the 3x+1 and 5x+1 Problems. Alex V. Kontorovich, Jeffrey C. Lagarias. in: The Ultimate Challenge: The 3x+1 problem, Amer. Math. Soc.: Providence 2010, pp. 131--188. math.NT.

math/0509175 Benford's law for the $3x+1$ function. Jeffrey C. Lagarias, K. Soundararajan. J. London Math. Soc. 74 (2006), 289--303. math.NT (math.PR).

math/0412003 Benford's Law, Values of L-functions and the 3x+1 Problem. Alex V. Kontorovich, Steven J. Miller. Acta Arithmetica 120 (2005), no. 3, 269-297. math.NT (math.PR).


There are many un-serious papers on this subject at the same site, I selected the above from papers that I read or authors whose other papers I have seen.

There is also a celebrated theorem by John H Conway in which he shows that the natural generalization of the Collatz problem, where different linear functions are applied to $n$ in several arithmetic progressions (partitioning all integers), can simulate a computer. A consequence is that it is undecidable to determine if such an iteration loops when started from $1$.

share|cite|improve this answer

One important relation to other number theoretic problems is that of the distance of perfect powers of 2 and 3, for which a lot of material exists, even online accessible. The existence of the so-called "1-cycles" (which is a whole class of possible cycles of arbitrary length but a certain simple structure) is directly dependent on the question, whether $$ {k3^N-1 \over k2^N-1}=2^A $$ exists in natural numbers N,A and k (besides for "trivial" solution (N,A,k)=(1,1,1), which leads to the (unsolved) problem observed in the Waring-conjecture whether $$ (3/4)^N \lt \{ ( 3/2)^N \} \lt 1-(3/4)^N $$ $ \qquad \qquad $ where $ \{ \cdot \}$ means the fractional part (see for instance mathworld)

Here is also the concept of K.Mahler's "z-numbers" relevant, which also relates the "1-cycles" in a general view to the powers of 3/2 and is also not too difficult to understand for a treatize which focuses an undergraduate publicum.

share|cite|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.