# Why does the expression $3n+1$ appear in Collatz conjecture?

Why is it important the role of $3n+1$ in Collatz conjecture? I mean, if we replace $3n+1$ by $5n+1$ it seems (numerically) that the modified statement of Collatz conjecture does not hold in this case.

So I assume that putting $3n+1$ is special in some sense, but which is the idea behind it? Are there any informal ideas that can make us think that the long time behaviour with $3n+1$ should be distinct than with $5n+1$, $7n+1$,...

Does anybody know what happens when we change $3$ by another odd number (proof or at least some kind of intuition)?

Replacing $$3$$ with a larger odd number makes numbers grow, on average. To see this, consider the $$qx+1$$ function, where $$q$$ is odd. An odd number grows by a factor of about $$q$$, after which it divides by $$2$$ some number of times. Half of the time, you get $$1$$ division step, one fourth of the time, you get $$2$$, one eighth of the time, you get $$3$$, etc.

Thus, the average size change from one odd number to the next one in its trajectory is:

$$\frac12\left(\frac{q}2\right)+\frac14\left(\frac{q}4\right)+\frac18\left(\frac{q}8\right)+\cdots,$$

which simplifies as a geometric series sum to $$\dfrac{q}3$$. If $$q>3$$, this quantity is larger than $$1$$, which means that odd numbers will, on average, grow as a result of the action of this function. When $$q=3$$, the forces of growth and shrinking are basically balanced, on average, so you get interesting dynamics in their tug-of-war.

• Have you seen this? Commented Apr 25, 2020 at 11:18
• @DaBler - I had not. Thank you; that's very interesting indeed! Commented Apr 25, 2020 at 11:27

This question "Why does(...)" can only be answered by Collatz himself or by research in his mathematical notes.
Let's see what Lagaraias (in his overview)$$\;^{(1)}$$ has to say:

## 2. History and Background

The 3x+1 problem circulated by word of mouth for many years. It is generally attributed to Lothar Collatz. He has stated ([14]) that he took lecture courses in 1929 with Edmund Landau and Fritz von Lettenmeyer in G¨ottingen, and courses in 1930 with Oskar Perron in Munich and with Issai Schur in Berlin, the latter course including some graph theory. He was interested in graphical representations of iteration of functions. In his notebooks in the 1930’s he formulated questions on iteration of arithmetic functions of a similar kind (cf. [58, p.3]). Collatz is said by others to have circulated the problem orally at the International Congress of Mathematicians in Cambridge, Mass. in 1950. Several people whose names were subsequently associated with the problem gave invited talks at this International Congress, including H. S. M. Coxeter, S. Kakutani, and S. Ulam.(...)

(Enhancing by me) It means, Collatz worked with various problems of this type, and specifically the version $$3x+1$$ he disseminated to collegues as being a difficult one.

This is just a short peeking into one reliable source, but by his references "[14]", "[58]" there should be answers with more detailed reasons possible here (I don'thave the book myself) ... P.s. such an information should surely be made available in the wikipedia-entry, if it is not yet there (didn't check it)

update Here is a screenshot from Lagarias' 1985 survey which gives again a bit more background, but I'd say your question "why..." needs even more specific details in its answer...

(from $$\;^{(2)}$$ )

$$\;^{(1)}$$ Lagarias, Jeffrey C., The (3x+1) problem: an overview, Lagarias, Jeffrey C. (ed.), The ultimate challenge. The (3x+1) problem. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4940-8/hbk). 3-29 (2010). ZBL1253.11036.

$$\;^{(2)}$$ Lagarias, Jeffrey C., The (3x+1) problem and its generalizations, Am. Math. Mon. 92, 3-23 (1985). ZBL0566.10007.