11
$\begingroup$

I apologize if this question gets down-voted ahead of time.

I've been working on the Collatz Conjecture all day with Python, because that is the language I'm most familiar with (I'm not a CS student, just majoring in math). Below is the function I'm using for your reference during my comments:

\begin{align} T\left(n\right)&=\begin{cases}1 & \text{if}\;n=1\\ T\left(\frac{n}{2}\right) & \text{if}\;n\;\text{is even}\\ T\left(3n+1\right) & \text{if}\;n\;\text{is odd}\end{cases}\tag{1} \end{align}

I've created graphs of the number of iterations vs. the integers up to $10^7$, one of which I've shown below for integers up to $2\cdot 10^6$:

Collatz Conjecture

I've read on Wolfram's Mathworld that the conjecture has been tested via computers for numbers up to $\approx 5.48\cdot 10^{18}$, which is quite impressive, although I was thinking ahead of time it would have been tested by this time for incredibly large integers given we've had computers for >50 years now.

Now to my simple question: would it be true that, given such an integer actually does exist that does not satisfy the conjecture, the smallest such number must be odd because if it is even there must exist a smaller such integer that does not satisfy the conjecture?

Further, suppose we did find such an integer. In my writings I've noticed that all integers within the sequences generated by this function eventually break down to a repeat of an earlier sequence. For instance, the following two sequences:

$\color{red}{7}$-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1

14-$\color{red}{7}$

These are simple, but even more lengthy sequences of numbers I've found break down to prior sequences that have already been computed, and must if we are to end up at $1$ unless it is defining a new sequence to be called by a later one (I wonder what the frequency of this is). But if we find such a number and it is odd, then all other numbers contained within this sequence must also not satisfy the conjecture. But is this true? Or am I thinking of "not satisfying" the conjecture in the wrong way?

Thank you for your time,

$\endgroup$
  • 2
    $\begingroup$ You are exactly correct that the lowest such number must be odd, because if it were even, we would be able to halve it and get a smaller odd number which did not satisfy the conjecture. $\endgroup$ – baum Mar 23 '15 at 1:45
  • 3
    $\begingroup$ Indeed. Thinking of it from a graph theoretical standpoint with vertices the natural numbers and directed edges the effect of the recurrence relation, the question is if the graph is even connected in the first place. The conjecture is that it is weakly connected with 1 an absorbing point. While you are able to prove (and have rightly done so) that the smallest counterexample if it exists is odd, that is not to say that no even counterexamples exist. There may yet be a cycle or an unbounded sequence for all we know (not that anyone believes that, but it is afterall still a conjecture). $\endgroup$ – JMoravitz Mar 23 '15 at 1:49
  • $\begingroup$ @JMoravitz When I look at this graph I think of that created by the difference equations in Chaos Theory. Any relation at all or papers you might suggest? Thank you for your informational comment by the way, there's a lot of terms I didn't know we associated with this problem. $\endgroup$ – jm324354 Mar 23 '15 at 1:59
  • 3
    $\begingroup$ @jm324354 When I refer to a "graph", I mean a graph in the graph theory sense. I.e., a collection of vertices and edges (and nothing more). The graph I proposed is a common way of approaching the problem and has been named "The Collatz Graph." Here is a paper which discusses the use of De Bruijn graphs to look at what they call modular Collatz Graphs (the graph of the relations modulo a certain number) and generalizations to related sequences. $\endgroup$ – JMoravitz Mar 23 '15 at 2:11
8
$\begingroup$

Yes, you're right: If there are any counterexample, then the smallest counterexample must be odd. And all successors and predecessors of a counterexample are themselves counterexamples.

There are two conceivable kinds of counterexample.

The first is a finite cyclic sequence that differs from the trivial 1-4-2-1 cycle. Finding such a counterexample would immediately produce a disproof of the conjecture.

The second is a starting point from which the sequence continues indefinitely without ever hitting a cycle. Just coming across such a point would not directly yield a disproof of the conjecture, because one would need to prove that the sequence does indeed never join a cycle, and there's no known systematic way of findig such a proof.

$\endgroup$
7
$\begingroup$

You are correct, in both your points. Suppose that the conjecture is false.

If $N$ is a counterexample and $M$ is an element of the sequence generated by $N$, then $M$ is a counterexample as well, since if the sequence generated by $M$ ended to $1$, then also the sequence generated by $N$ ends at $1$.

For the same reason, the minimal counterexample has to be odd, because if $N$ is an even counterexample, then $N/2$ is a counterexample as well, as it is the first term generated by the sequence starting with $N$.

$\endgroup$

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.