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$


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

  • $\begingroup$ How is $f(n) = \Theta(n)$ not obvious? $\endgroup$ Aug 3, 2014 at 8:17
  • 7
    $\begingroup$ There is no known explicit bound on the complexity of f, and proving one would go a long way towards solving the conjecture. $\endgroup$ Aug 3, 2014 at 10:45
  • 1
    $\begingroup$ Just to make clear, my first comment was for a completely different $f(n)$ (or at least the way I understood it). $\endgroup$ Aug 3, 2014 at 15:08
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 4, 2014 at 15:45
  • 1
    $\begingroup$ @SashoNikolov I'd love to see some of these results! $\endgroup$ Aug 5, 2014 at 13:01

2 Answers 2


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

  • $\begingroup$ Does Conway's result imply we cannot provide a complexity measure of f(n)? Could we provide a probabilistic measure for ranges of n? $\endgroup$ Aug 3, 2014 at 10:17
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 3, 2014 at 10:41
  • 8
    $\begingroup$ 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. $\endgroup$ Aug 3, 2014 at 15:11
  • 1
    $\begingroup$ any proof/evidence that the Collatz problem itself has some aspect of undecidability embedded in it would be a theoretical breakthrough... $\endgroup$
    – vzn
    Aug 4, 2014 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 agree to our terms of service, privacy policy and cookie policy

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