Let $C$ : ${\mathbb N}\longrightarrow {\mathbb N}$ be Collatz's map defined by $C(n) = 3n+1$ if $n$ is odd, and $C(n)=n/2$ if $n$ is even. Then according to Collatz's conjecture, we should have $C^k (n)=1$, for all $n>0$ and $k$ large enough. Assume that the conjecture holds and for $n>0$ define the top of the orbit of $n$ by $$ t(n) = \text{max} \{ C^k (n), \ k\geq 0\} $$

Define $$ T(N) = \text{ Card}\{ n\ , \ t(n) \leq N\} /N $$

Had the assymptotic behaviour of T(N) been studied ?

  • 6
    $\begingroup$ Many elementary things like this have been considered so far, without much success -- do you see a reason to hope that studying this particular function may yield something interesting? $\endgroup$ – Stefan Kohl Feb 19 '15 at 16:47
  • 7
    $\begingroup$ I did some computations with SAGE which suggest that T(N) could maybe be convergent. $\endgroup$ – Paul Broussous Feb 19 '15 at 17:04
  • 2
    $\begingroup$ Could you show us a graph of $T(N)$? $\endgroup$ – Joseph O'Rourke Feb 19 '15 at 22:31
  • 4
    $\begingroup$ @JosephO'Rourke: For $k=1 \dots,20$ we get the following values of $T(2^k)$: 1, 0.75, 0.5, 0.625, 0.40625, 0.515625, 0.429688, 0.4375, 0.353516, 0.34375, 0.283203, 0.261719, 0.259644, 0.414551, 0.398773, 0.395294, 0.392509, 0.398922, 0.397013, 0.396653. $\endgroup$ – Stefan Kohl Feb 19 '15 at 23:47
  • 2
    $\begingroup$ @Stefan I also found T(2^21) =0.39725, T(2^22)=0.39609 and T(2^23)=0.39674. $\endgroup$ – Paul Broussous Feb 20 '15 at 11:45

If the sequence $(T(N))_{N \in \mathbb{N}}$ converges and the limit is not equal to $0$, this would imply either positive predecessor density for $1$, cf. e.g.

Günther J. Wirsching, On the problem of positive predecessor density in $3n+1$ dynamics, Discrete and Continuous Dynamical Systems - Series A (DCDS-A), Volume 9, Issue 3, 2003, Pages 771 - 787, doi:10.3934/dcds.2003.9.771,

or the existence of nontrivial cycles.

If the sequence converges, it therefore seems hopeless to prove this with elementary means.

  • $\begingroup$ Thank you Stefan for your answer and your nice graphics. I indeed found the same values for T(2^n). $\endgroup$ – Paul Broussous Feb 20 '15 at 6:59

As Stefan Kohl has pointed out it is not possible to give good lower bounds for $T(N)$ without making progress on the Collatz problem itself. However it is not difficult to understand what the truth is, and the argument below will yield a rigorous upper bound.

Instead of the map $C(n)$ as defined, it is better to consider $C_0(n) = n/2$ if $n$ is even, and $(3n+1)/2$ if $n$ is odd. For large $n$, this map multiplies by approximately $1/2$ or $3/2$ with probability $1/2$, and the first several iterations of the map behave independently. The crux of the Collatz problem is that this independent behavior roughly persists till the end making the iterates come down to zero -- that of course is hard, but it is easy to see that as many initial iterates as you like will behave independently just by looking at residue classes modulo a large power of $2$.

Now consider the random walk starting with a random real number $\alpha_0=\alpha$ chosen uniformly from $[0,1]$, and setting $\alpha_k = \alpha_{k-1} \times 3/2$ or $\times 1/2$ with equal probability. Then for each such realization take the max of $\alpha_k$ over all $k\ge 1$. In this setting you are asking for the probability that this maximum is at most $1/2$. (The half arises because of the difference between your $C(n)$ and the more natural $C_0(n)$.)

It is easy to upper bound the probability above by running the random walk for some number of steps. After $25$ steps, a computer calculation gave the upper bound $0.40641\ldots$, which agrees with Stefan Kohl's numerics.


(Without any intended answer:) Two further pictures.
First, a bit more detailed curve up to $N=100 000$. I supressed the datapoints $T(N)$ at $N$, where the frequencies are below $6$ here to have the curve a bit more sharpened/showing the peaks in the underlying frequencies-list:


And it seems to me, that the actual frequency of occurence of N as maximum of a trajectory gives some more intuition what's going on here. While the above cumulative curve tends to "iron out" any variability when going to the right, the systematic spikes of the frequencies-table here indicate, that such spikes do not wear out in the long run but (likely) even get higher counts (again I left out the datapoints of smaller frequencies in the picture):


  • $\begingroup$ Very revealing graphs, especially the second one. $\endgroup$ – Joseph O'Rourke Feb 21 '15 at 20:42

Here is a plot of Stefan Kohl's data (now supplemented by Paul Broussous), which they kindly provided in response to my query:

Added as per TMA's suggestion:

  • 2
    $\begingroup$ Much as I enjoy your explanatory graphics, I find this one misleading. I recommend either plotting T(N) for all N in the range ( and then using a log scale), or instead relabelling and plot integer k against T(2^k). A comparison of this graph with the first modification (T(N) vs log N for N not powers of 2) might serve as a good topic in data representation. $\endgroup$ – The Masked Avenger Feb 20 '15 at 1:31
  • 3
    $\begingroup$ Maybe it's just my software, but the numbers labelling the $N$-axis in the second diagram are running into each other. $\endgroup$ – Gerry Myerson Feb 20 '15 at 2:15
  • $\begingroup$ @GerryMyerson: Yes, sorry, fixed the problem. Also extended with Paul's 3 additional data points. $\endgroup$ – Joseph O'Rourke Feb 20 '15 at 13:00

protected by Lucia Dec 3 '15 at 18:06

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.