The "Half Or Triple Plus One" process goes as follows:

  1. start with $x=n$ for some value of $n$
  2. if ($x$ is odd)

    $x = 3x+1$

    else

    $x = \frac{x}{2}$

  3. if ($x$ > 1) goto (2)

Define $f(n) = $

total stopping time of $n$, i.e. The number of steps required for the procedure to halt.

The Collatz conjecture suggests that the process stops for every value of $n$, hence if the conjecture holds, $f$ is well defined.


The question is:

What is the asymptotic time complexity of calculating $f(n)$?

  • How is $f(n) = \Theta(n)$ not obvious? – Sasho Nikolov Aug 3 '14 at 8:17
  • 7
    There is no known explicit bound on the complexity of f, and proving one would go a long way towards solving the conjecture. – Emil Jeřábek Aug 3 '14 at 10:45
  • 1
    Just to make clear, my first comment was for a completely different $f(n)$ (or at least the way I understood it). – Sasho Nikolov Aug 3 '14 at 15:08
  • 1
    BTW there are results of the type $\Omega(n^c)$ of the numbers in $\{1, \ldots, n\}$ have finite stopping time, for $c < 1$ a fixed constant. If that's of interest I can find the citation. – Sasho Nikolov Aug 4 '14 at 15:45
  • 1
    @SashoNikolov I'd love to see some of these results! – Alexis Petrounias Aug 5 '14 at 13:01
up vote 7 down vote accepted

First, as the conjecture is still open, we can't say if $f$ is even defined for every $n$.

Let's assume that if $f(n)=\infty$, then the algorithm is required to output $-1$.

In 1972 Conway showed that a generalization of the problem of determining whether $f(n)= \infty$ is undecidable. In particular, no algorithm can always determine, on input $n$ and sequences $(a_i)_{i=0}^{p-1}$, $(b_i)_{i=0}^{p-1}$, whether the process that starts with $x = n$ and iteratively maps $x$ to $a_ix + b_i$ whenever $x \equiv i \pmod{p}$ terminates at 1 in finite time. Here the $a_i$ and $b_i$ are assumed to be chosen so that the results are always integers. This result isn't necessarily applicable for the Collatz function, which presents only one fixed choice of $a_i$ and $b_i$ and leaves only $n$ as a variable.


Side note: The A006877 series in http://oeis.org/ contains the values of $n$ for which $\forall m<n:f(m)<f(n)$.

  • Does Conway's result imply we cannot provide a complexity measure of f(n)? Could we provide a probabilistic measure for ranges of n? – Alexis Petrounias Aug 3 '14 at 10:17
  • 3
    If the finiteness of $f(n)$ is undecidable, then $f(n)$ is not bounded by any recursive function. However, Conway's result does not apply to this particular f, but to a more general class of similar functions. – Emil Jeřábek Aug 3 '14 at 10:41
  • 8
    RB, can you edit your answer to make clear the Conway has not shown undecidablity for the Collatz function, but for a related more general class of functions. – Sasho Nikolov Aug 3 '14 at 15:11
  • 1
    any proof/evidence that the Collatz problem itself has some aspect of undecidability embedded in it would be a theoretical breakthrough... – vzn Aug 4 '14 at 21:46

By request, two facts that are known and seem somewhat related to your question.

  • As a lower bound: infinitely many integers $n$ take time $\Omega(\log n)$. Applegate and Lagarias.

  • As a sort of an upper bound: $\Omega(N^c)$ positive integers bounded by $N$ reach $1$ in finite time, where $c \approx 0.84$. Krasikov and Lagarias.

Hopefully you have read Lagarias's survey before asking the question.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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