11
$\begingroup$

The set of all positive whole numbers is denoted by $\mathbb{N}_+$.

Let $f\colon\ \mathbb{N}_+\to\mathbb{N}_+:n\mapsto \begin{cases}\frac{n}{2}&\text{$n$ even}\\3n+1&\text{$n$ odd}\end{cases}$.

Conjecture (Collatz). $\forall n\in\mathbb{N}_+.\ \exists N\in\mathbb{N}.\ f^N(n)=1$.

Let $m,n\in\mathbb{N}_+$. We define: $m\sim n:\iff\exists N_1, N_2\in\mathbb{N}.\ f^{N_1}(m)=f^{N_2}(n)$.

It is easy to see that $\sim$ is an equivalence relation on $\mathbb{N}_+$. If we suppose the truth of the Collatz conjecture, then there is only one equivalence class.

  1. How to prove that there is only a finite number of equivalence classes of $\sim$? Has somebody ever proven this? Or is the question whether there is only a finite number of equivalence classes open?
  2. Is there an algorithm solving the following decision problem?

INSTANCE: A pair $(m, n)\in\mathbb{N}_+\times\mathbb{N}_+$

QUESTION: Does $m\sim n$ hold?

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ If the algorithm terminates for every pair $(m,1)$ (and there is a proof that it does so), then by looking at the set of all $m$ for which the algorithm outputs "no" one obtains a precise characterization of the set of all counterexamples to the Collatz conjecture. It's hard to imagine how such a characterization would not lead to either a proof or a counterexample for the conjecture itself. $\endgroup$
    – Paul Siegel
    Dec 13, 2015 at 12:43
  • 1
    $\begingroup$ Why does one definitely obtain a precise characterization if we had such an algorithm? The question "For which inputs does this algorithm halt" can be open, though. $\endgroup$
    – wijerajasdfa
    Dec 13, 2015 at 12:49
  • 4
    $\begingroup$ Well, here's an algorithm: Replace $(m, n)$ with $(f(m), f(n))$ and repeat, halting and outputting "yes" if both $f(m)$ and $f(n)$ are in the set $\{1,2,4\}$. This algorithm halts for all inputs if and only if the Collatz conjecture is true. $\endgroup$
    – Paul Siegel
    Dec 13, 2015 at 12:56
  • 3
    $\begingroup$ There is an algorithm for "Does m∼n hold?". Namely: Answer YES. That algorithm works! But (unfortunately) this comment box is too small to contain the proof. $\endgroup$
    – Gerald Edgar
    Dec 13, 2015 at 13:51
  • 2
    $\begingroup$ @Paul Siegel If a Collatz sequence cannot diverge to infinity, then the equivalence relation is decidable: Just keep computing the next element (and store all previous ones), until the cycle has been completed. Now one just has to check whether both starting points have reached the same or different cycles. In fact, it would suffice it there were at most one diverging sequence. This algorithm doesn't really tell us anything about how many different cycles there might be. $\endgroup$
    – Arno
    Dec 13, 2015 at 16:09

1 Answer 1

Reset to default
11
$\begingroup$

This problem is still open. See for example Sections 2.6 and 2.7 of Lagarias's survey.

Improve this answer
$\endgroup$
0

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.