# What are some reasonable things to prove about the Collatz Conjecture?

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)$.

-
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 go.helms-net.de/math/collatz/Collatz061102.pdf 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

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). http://front.math.ucdavis.edu/0309.5224

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) http://front.math.ucdavis.edu/0608.5208

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. http://front.math.ucdavis.edu/0412.5003

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). http://front.math.ucdavis.edu/0509.5175 http://front.math.ucdavis.edu/0910.1944

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). http://front.math.ucdavis.edu/0412.5003

and

http://front.math.ucdavis.edu/0411.5140

http://front.math.ucdavis.edu/0205.5002

http://front.math.ucdavis.edu/0201.5102

http://front.math.ucdavis.edu/0204.5170

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$.

-

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.

-