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

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

<p>In 1972 <a href="http://www.ams.org/mathscinet/pdf/392904.pdf?pg1=MR&amp;r=1&amp;s1=392904" rel="nofollow">Conway showed</a> 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.</p>

<hr>

<p>Side note: The <a href="http://oeis.org/A006877" rel="nofollow">A006877</a> series in <a href="http://oeis.org/" rel="nofollow">http://oeis.org/</a> contains the values of $n$ for which $\forall m&lt;n:f(m)&lt;f(n)$.</p>

CC BY-SA 3.0
2014-08-03T10:17:19.940Z
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
CC BY-SA 3.0
2014-08-03T10:41:36.863Z
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
CC BY-SA 3.0
2014-08-03T15:11:29.060Z
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
CC BY-SA 3.0
2014-08-04T21:46:38.937Z
any proof/evidence that the Collatz problem itself has some aspect of undecidability embedded in it would be a theoretical breakthrough...
vzn
CC BY-SA 3.0
2014-08-03T09:44:53.333Z
2014-08-08T06:37:52.210Z
2014-08-08T06:37:52.210Z
R B
<p>By request, two facts that are known and seem somewhat related to your question.</p>

<ul>
<li><p>As a lower bound: infinitely many integers $n$ take time $\Omega(\log n)$. <a href="http://www.ams.org/journals/mcom/2003-72-242/S0025-5718-02-01425-4/home.html">Applegate and Lagarias</a>.</p></li>
<li><p>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$. <a href="http://journals.impan.pl/cgi-bin/doi?aa109-3-4">Krasikov and Lagarias</a>.</p></li>
</ul>

<p>Hopefully you have read <a href="http://www.ams.org/bookstore/pspdf/mbk-78-prev.pdf">Lagarias's survey</a> before asking the question. </p>

CC BY-SA 3.0
2014-08-05T22:45:54.387Z
2014-08-05T22:45:54.387Z
Sasho Nikolov
<p>The "Half Or Triple Plus One" process goes as follows:</p>

<blockquote>
  <ol>
  <li>start with $x=n$ for some value of $n$</li>
  <li><p>if ($x$ is odd)</p>
  
  <p>$x = 3x+1$</p>
  
  <p>else</p>
  
  <p>$x = \frac{x}{2}$</p></li>
  <li><p>if ($x$ > 1) goto (2)</p></li>
  </ol>
</blockquote>

<p>Define $f(n) = $ </p>

<pre><code>total stopping time of $n$, i.e. The number of steps required for the procedure to halt.
</code></pre>

<hr>

<p>The <a href="http://en.wikipedia.org/wiki/Collatz_conjecture" rel="nofollow">Collatz conjecture</a> suggests that the process stops for every value of $n$, hence if the conjecture holds, $f$ is well defined.</p>

<hr>

<p>The question is:</p>

<blockquote>
  <p><strong>What is the asymptotic time complexity of calculating $f(n)$?</strong></p>
</blockquote>

CC BY-SA 3.0
2014-08-03T08:17:12.743Z
How is $f(n) = \Theta(n)$ not obvious?
Sasho Nikolov
CC BY-SA 3.0
2014-08-03T08:38:08.527Z
I was under the impression that because the number of steps before any given n converges to 1 can vary significantly between successive values of n, it was not as simple as saying its proportional to n. For instance, the sequence for n == 4 is shorter than for n == 3.
Alexis Petrounias
CC BY-SA 3.0
2014-08-03T10:45:23.403Z
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
CC BY-SA 3.0
2014-08-03T15:08:01.837Z
Just to make clear, my first comment was for a completely different $f(n)$ (or at least the way I understood it).
Sasho Nikolov
CC BY-SA 3.0
2014-08-04T03:25:02.703Z
to go further than EJ's point, basically any time complexity bounds on the problem would be _equivalent_ to a proof. at heart the conjecture is about the upper bound time complexity of the computation/ trajectories. in line with this, there seems some possibility that CS or complexity theoretic approaches have not been tried on the problem & might go further than prior analysis which tends to be more number-theoretic or mathematical. it is easy to conjecture various simple function bounds that "seem" sufficient for "most" finite values that can be verified computationally.
vzn
CC BY-SA 3.0
2014-08-04T15:45:17.613Z
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
CC BY-SA 3.0
2014-08-05T13:01:39.073Z
@SashoNikolov I'd love to see some of these results!
Alexis Petrounias
<time-complexity><open-problem>
What is the asymptotic time complexity of the number of steps of "Half Or Triple Plus One" ( HOTPO)?
Alexis Petrounias
# What is the asymptotic time complexity of the number of steps of "Half Or Triple Plus One" ( HOTPO)?

(Asked by: username_0 on 2014-08-03)

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

**Tags:** time-complexity, open-problem
> **Comments:**
> **username_1**: How is $f(n) = \Theta(n)$ not obvious?  
> **username_0**: I was under the impression that because the number of steps before any given n converges to 1 can vary significantly between successive values of n, it was not as simple as saying its proportional to n. For instance, the sequence for n == 4 is shorter than for n == 3.  
> **username_2**: There is no known explicit bound on the complexity of f, and proving one would go a long way towards solving the conjecture.  
> **username_1**: Just to make clear, my first comment was for a completely different $f(n)$ (or at least the way I understood it).  
> **username_3**: to go further than EJ's point, basically any time complexity bounds on the problem would be _equivalent_ to a proof. at heart the conjecture is about the upper bound time complexity of the computation/ trajectories. in line with this, there seems some possibility that CS or complexity theoretic approaches have not been tried on the problem & might go further than prior analysis which tends to be more number-theoretic or mathematical. it is easy to conjecture various simple function bounds that "seem" sufficient for "most" finite values that can be verified computationally.  
> **username_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.  
> **username_0**: @SashoNikolov I'd love to see some of these results!  

---

## 2 answers

### Answer by username_4 on 2014-08-03. Score: 7 | Accepted answer

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](http://www.ams.org/mathscinet/pdf/392904.pdf?pg1=MR&r=1&s1=392904) 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](http://oeis.org/A006877) series in <http://oeis.org/> contains the values of $n$ for which $\forall m

> **Comments:**
> **username_0**: Does Conway's result imply we cannot provide a complexity measure of f(n)? Could we provide a probabilistic measure for ranges of n?  
> **username_2**: 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.  
> **username_1**: 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.  
> **username_3**: any proof/evidence that the Collatz problem itself has some aspect of undecidability embedded in it would be a theoretical breakthrough...  

---

### Answer by username_1 on 2014-08-05. Score: 9

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](http://www.ams.org/journals/mcom/2003-72-242/S0025-5718-02-01425-4/home.html).
* 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](http://journals.impan.pl/cgi-bin/doi?aa109-3-4).

Hopefully you have read [Lagarias's survey](http://www.ams.org/bookstore/pspdf/mbk-78-prev.pdf) before asking the question.


---

