2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ How is $f(n) = \Theta(n)$ not obvious? $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented Aug 4, 2014 at 15:45
  • 1
    $\begingroup$ @SashoNikolov I'd love to see some of these results! $\endgroup$ Commented Aug 5, 2014 at 13:01

2 Answers 2

7
$\begingroup$

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

$\endgroup$
4
  • $\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$ Commented 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$ Commented 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$ Commented 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
    Commented Aug 4, 2014 at 21:46
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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