Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
The "Half Or Triple Plus One" process goes as follows:
- start with $x=n$ for some value of $n$
if ($x$ is odd)
$x = 3x+1$
else
$x = \frac{x}{2}$
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)$?
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)$.
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.
