46
$\begingroup$

Edit

I've highlighted the area in the proof where the mistake was made, for the benefit of anyone stumbling upon this in the future. It's the same mistake, made in two places:

This has proven the Collatz Conjecture for all even numbers

The Collatz Conjecture was shown to hold for $N+1$ when $N+1$ is even -- it was never shown to hold for all even numbers -- just that one, lone even number.

[The Collatz Conjecture holds for] all odd numbers for which $N-1$ is a multiple of $4$

The same as above: it was shown that the Collatz Conjecture holds for $N+1$ if $N+1$ is of the form $4k+1$. It was never shown to hold for all numbers of this form -- just that one, lone number.

In order for my proof to be valid, I would need to prove that the Collatz Conjecture holds for $N+1+4j = 4k+1$ (every fourth number after $N+1$) for, at a minimum, $N+1+4j < 1.5N+2$

Original Post

I spent about an hour thinking about the Collatz Conjecture and stumbled upon what feels like a proof... but I came to it all too easily to have done everything right.

  1. the obvious that everyone has already figured out:

Assume the Collatz Conjecture holds for all numbers $1...N$

We can trivially prove the Collatz Conjecture for some base cases of $1,$ $2,$ $3,$ and $4$. This is sufficient to go forward.

  1. Yet more obvious:
  1. If $N$ is odd, $N+1$ is even
  2. $(N+1)/2 < N$ for $N > 3$
  3. By the induction hypothesis, the Collatz Conjecture holds for $N+1$ when $N+1 = 2k$
  1. Now the last obvious bit:
  1. If $N$ is even, $N+1$ is odd
  2. If $N+1$ is odd, the next number in the series is 3(N+1)+1
  3. Since $(N+1)$ is odd, $3(N+1)+1$ is even
  4. The next next number in the series is $(3(N+1)+1)/2$
  5. This simplifies to: $(3N + 4)/2 = 1.5N + 2$
  1. Now the first tricky bit:
  1. If $N$ is a multiple of $4$:
  2. $1.5N$ is a multiple of $6$, and therefore even. $1.5N + 2$ is therefore even
  3. The next next next number in the series is therefore $(1.5N+2)/2$
  4. This simplifies to $0.75N + 1$
  5. This is less than $N$ for $N > 4$
  6. By the induction hypothesis, the Collatz Conjecture holds for $N+1$ when $N+1 = 4k + 1$

This has proven the Collatz Conjecture for all even numbers and all odd numbers for which $N-1$ is a multiple of $4$... Now to blow your minds:

  1. Breaking out of formal equations into patterns and such since I didn't know how to formalize this bit with math symbols:
  1. We now know that a number $N+1$ can ONLY violate the Collatz Conjecture if $N$ is even and not a multiple of $4$. In other words, the only way a number could potentially violate the Collatz Conjecture is if it's of the form $N+1 = 4k - 1$
  2. This limits our numbers to test to 2+1, 6+1, 10+1, 14+1, 18+1, 22+1, etc. (note that I wrote these numbers in "$N+1$" format so it'd be simpler to apply the $1.5N+2$ shortcut)
  3. We'll apply our $1.5N + 2$ shortcut to a handful of these numbers:
2  -> 3+2  = 5  (4 +1) -- 4 is a multiple of 4 (duh)
6  -> 9+2  = 11 (10+1)
10 -> 15+2 = 17 (16+1) -- 16 is a multiple of 4
14 -> 21+2 = 23 (22+1)
18 -> 27+2 = 29 (28+1) -- 28 is a multiple of 4
22 -> 33+2 = 35 (34+1)
26 -> 39+2 = 41 (40+1) -- 40 is a multiple of 4
30 -> 45+2 = 47 (46+1)
34 -> 51+2 = 53 (52+1) -- 52 is a multiple of 4
38 -> 57+2 = 59 (58+1)
42 -> 63+2 = 65 (64+1) -- 64 is a multiple of 4
46 -> 69+2 = 71 (70+1)
  1. Every other line we automatically know the Collatz Conjecture will hold, because we've hit a number that can be expressed as $4k+1$
  2. Looking at the "kept" rows, we can see that all we need to test now are numbers of the form: N+1 = 8k - 1 (in other words, the rows where N = 8k - 2 -- 6, 14, 22, etc.)
  1. And finally, recurse on this solution by drawing a new table and instead of computing the "next next" value, compute the "next next next next" value:

"Next next next" value = 3(1.5N + 2) + 1 = 4.5N + 7

"next^4" value is half of this -- 2.25N + 3.5

6  -> 27 +7 = 34  -> 17  (16 +1) -- 16 is a multiple of 4
14 -> 63 +7 = 70  -> 35  (34 +1)
22 -> 99 +7 = 106 -> 53  (52 +1) -- 52 is a multiple of 4
30 -> 135+7 = 142 -> 71  (70 +1)
38 -> 171+7 = 178 -> 89  (88 +1) -- 88 is a multiple of 4
46 -> 207+7 = 214 -> 107 (106+1)
54 -> 243+7 = 250 -> 125 (124+1) -- 124 is a multiple of 4
62 -> 279+7 = 286 -> 143 (142+1)

Every other line we automatically know the Collatz Conjecture will hold, because we've hit a number that can be expressed as 4k+1

We now know a number can only violate the Collatz Conjecture if it's of the form: N+1 = 16k - 1... Recurse again:

"next^5" value is 3(2.25N + 3.5) + 1 = 6.75N + 11.5

"next^6" value is (6.75N + 11.5)/2 = 3.375N + 5.75

14   -> 53  = 52  + 1 -- 52 is a multiple of 4
30   -> 107 = 106 + 1
46   -> 161 = 160 + 1 -- 160 is a multiple of 4
62   -> 215 = 214 + 1
78   -> 269 = 268 + 1 -- 268 is a multiple of 4
94   -> 323 = 322 + 1
110  -> 377 = 376 + 1 -- 376 is a multiple of 4
126  -> 431 = 430 + 1

We now know a number can only violate the Collatz Conjecture if it's of the form N+1 = 32k - 1

At this point, a pattern is quickly emerging:

  1. First, a number could only violate the Collatz Conjecture if it was of the form N+1 = 4k - 1
  2. Next, a number was shown that it could only violate the Collatz Conjecture if it was of the form N+1 = 8k - 1
  3. Next, a number was shown that it could only violate the Collatz Conjecture if it is of the form N+1 = 16k - 1
  4. Now, a number has been shown that it can only violate the Collatz Conjecture if it is of the form N+1 = 32k - 1

I've continued this process (recursively building this table and removing rows that I know cannot violate the Collatz Conjecture since they can be expressed as 4k+1) all the way up until 512k - 1 by hand.

I do not know how to formalize this final process in mathematical notation, but I believe it demonstrates at least a viable method for proving the Collatz Conjecture. For every two steps we take into the Collatz series, we increase the power on our definition of "only numbers that could possibly violate the conjecture". Therefore for an arbitrarily large power we know that the conjecture will still hold.

For Fun

To help me in building these tables, I crafted the following Python script:

# Increment this variable to recurse one level deeper
test = 1

### No need to edit below here, but feel free to read it ###
depth = 2 * test
step = 2 ** (test + 1)
start = step - 1

for x in range(0, 20):
    num = start + x * step
    _num = num
    _depth = depth
    while _depth > 0:
        if _num % 2 == 0:
            _num = _num / 2
        else:
            _num = 3 * _num + 1
        _depth -= 1
    text = ""
    if (_num - 1) % 4 == 0:
        text = "-- multiple of 4"
    print "%s: %s = %s + 1 %s" % (num - 1, _num, _num - 1, text)
$\endgroup$
  • 5
    $\begingroup$ I didn't say I broke it. I said I proved it (ie - it's unbreakable). Although I'm extremely unwilling to believe I accidentally stumbled upon the proof, so I want some people smarter than I to check my work. $\endgroup$ – stevendesu Oct 31 '17 at 7:52
  • 4
    $\begingroup$ If you have a proof for all even numbers, then I give you a hint as how to prove it for all numbers: given k completely arbitrary, consider 2k which is even. Oh great we know it has to be true for 2k, but the next term is k, so we know it for k. $\endgroup$ – Jonathan Oct 31 '17 at 8:16
  • 13
    $\begingroup$ In step 2, you've proven it for the even number N+1. But you have not proved it for the even number N+3, because your argument relies on the inductive hypothesis for all numbers < N+3 (not just even numbers), and you have not proven it for the odd number N+2 yet and therefore you cannot draw any conclusion for N+3. So in the later parts of the argument, while you're still in the middle of the induction, you cannot assume you've proven it for all even numbers. $\endgroup$ – Ted Oct 31 '17 at 8:17
  • 3
    $\begingroup$ @Jonathan: so we only need to prove it for the elements of the set $2\mathbb N$ of even numbers? Then it is sufficient to prove it for the set $4\mathbb N$ of multiple of $4$! And, by induction, it is sufficient to prove the conjecture for the elements of $2^n\mathbb N$. But $\lim_{n\to\infty}2^n\mathbb N=\emptyset$, so the conjecture is proved :) What a great day! $\endgroup$ – Taladris Nov 1 '17 at 1:21
  • 1
    $\begingroup$ @Jonathan Having read user7530's response (and understanding it), I see the error with my "proof for even numbers". The smallest counter-example to the Collatz Conjecture cannot be even, but that's not to say that no counter-example can be even. The only limitation is that any even counter-example to the Collatz Conjecture is at least double the first counter-example. $\endgroup$ – stevendesu Nov 1 '17 at 15:06
92
$\begingroup$

There is a subtle issue with your induction argument: you are assuming that the Collatz conjecture holds for all integers $\leq n$, and then want to prove it holds for $n+1$ (strong induction). So far, so good.

You then prove that for some cases ($n+1$ even, or of the form $4k+1$) that the Collatz conjecture holds by the inductive hypothesis. Fine.

You then try to argue that for some numbers of the form $4k+3$, you eventually hit a number of the form $4k+1$, so that the Collatz conjecture holds... not so fast. You haven't proven that the Collatz conjecture holds for all integers of the form $4k+1$. You've proven it's true for $n+1$, if $n+1$ happens to be of that form, and you've assumed it's true for all numbers of that form $\leq n$ (by the inductive hypothesis) but you haven't shown that Collatz holds for numbers of the form $4k+1$ that are larger than $n+1$.

$\endgroup$
  • 2
    $\begingroup$ Definitely stopped me in my tracks here. I attempted to prove that the conjecture holds for N+1+4j <= 1.5N + 2 by plugging in but only managed to prove that the conjecture holds for N+1+4j <= (4/3)N + 2. This one proof would have been sufficient to rely on my 1.5N + 2 shortcut for eliminating the first half of possible counterexamples. After that would have been an attempt at a similar recursive proof using 8 instead of 4. But without the full 1.5N I'm dead in the water. $\endgroup$ – stevendesu Oct 31 '17 at 9:13
  • 1
    $\begingroup$ Indeed...more simply, $4k+3$ (forward jump) will eventually (after one or several steps) land on a $4k+1$ (backward jump) which could land on a $4k+3$ which.... From here, all you need, to get a divergent serie, is to have larger forward jumps (on average) than backward jumps. And, as said bellow, it does not rule out cycles. $\endgroup$ – Collag3n Oct 31 '17 at 17:59
41
$\begingroup$

The error is:

We now know that a number $N+1$ can ONLY violate the Collatz Conjecture if $N$ is even and not a multiple of $4$.

We don't know that. What we know is that if there are numbers that violate the Collatz conjecture, then the smallest such number is $1$ more than something even and not a multiple of $4$. But there may be larger counterexamples which don't look like that.

This is how proof by induction works: if there's a counterexample, there must be a smallest counterexample, i.e. the conjecture is false for some number $n+1$ but true for all numbers $\leq n$. Then we can try to show that this can't happen. But if we can't deduce a contradiction from this, but only get some conditions which $n+1$ has to satisfy, then these conditions only hold for the smallest counterexample, not for every counterexample, since we had to assume that $n+1$ was the smallest counterexample in order to make the deduction.

$\endgroup$
8
$\begingroup$

In addition to the previous comments, there is another implicit assumption that needs to be addressed for this proof to work: The consideration for other loops.

The danger of this flaw is evident here: I used your method outlined in your proof, assuming $4k+1$ defines the numbers that converge to 1 and thus prove the Collatz Conjecture. I extended this formula to the modified Collatz rule $3x+5$, since the only difference is the $+5$ instead of $+1$. (I refrained from using $3x+3$ because its structure is completely different from that of $3x+1$ and $3x+5$.)

To achieve this, I used $4k+5$ for appropriateness, since the $n/2$ rule still applies for $3x+5$. I then look at the following sequence generated:

9,17,21,25,29,...

Immediately trouble unfolds. 9 goes to 32, which goes to 1, which completes the 8-4-2-1 loop.

13 goes to 11, which goes to 38, which then finds itself in the 19 loop. [19-62-31-98-49-152-76-38-19]

17 goes to 7, which goes to 13. 21 goes to 17 which goes to 7... maybe there is a pattern here?

25... ruins the entire new pattern. It goes to 80, which is a straight shot to the 5 loop [20-10-5-20].

And 29? Dead center of the 23 loop. [29-92-46-23-74-37-116-58-29].

Therefore, tuning this proof to prove that $3x+1$ will not wander to infinity is completely possible, however assuming every number reaches a power of 2 at some point may lead to further trouble. Especially since a sequence wandering to infinity for the Collatz Conjecture must never reach a power of 2 as $5x+1$ seems to demonstrate with its seemingly infinite 7 sequence.

$\endgroup$

protected by Community Feb 7 '18 at 17:08

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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