The Collatz Conjecture

So, I think I figured out the Collatz Conjecture proof, but I'm not sure if there is anything wrong in my proof. Please tell me if you find it.. :D

First, we have to know what is Collatz Conjecture. Collatz Conjecture is a sequence conjecture that is defined as follows:

We start with a positive integer nn. If nn is even, then divide it by 2. If nn is odd, then multiply it by 3 and then add it with 1. Then we repeat this with the remaining term. The conjecture is for all positive integers, this sequence will reach 1.

For example, let's pick 3 for our first number, then the sequence is:

  • 3 is odd, so the next term is 3×33 \times 3 +1+1 = 1010
  • 10 is even, so the next term is 102 \frac{10}{2} = 55
  • 5 is odd, so the next term is 3×53 \times 5 +1+1 = 16
  • 16 is even and it is a power of 2 ( 24 2^{4} ), so all the next term is 8, 4, 2, and 1

Now here is my proof (please tell me if something's wrong).

Based on the definition of the conjecture, the domain is sets of all positive integers. We can divide the positive integers into two types, the odd positive integers ( like 1, 7, and 131 ), and the even positive integers ( like 2, 10, and 324 ). The even positive integers can be divided again into two types, the even positive integers that are powers of 2 ( like 8, 32, and 512 ), and the even positive integers that are not powers of 2 ( like 20, 98, and 1002 ).

First, we start at a positive integer nn. The first case is that nn is even, and the second case is that nn is odd.

  • Case 1 : nn is even (powers of 2)

Because powers of 2 has the term 2m 2^{m} , we can conclude that all powers of two will always reach 1.

If nn = 2m 2^{m} , then n2m \frac{n}{2^{m}} = 11

By dividing a power of two 2m2^{m} with two mm times, we will reach 1.

The even positive integers that is not powers of 2 means that the integers have at least 1 odd prime factor. For example, 20 is not a power of 2 because it has an odd prime factor (that is 5) , and 42 is not a power of 2 because it has 2 odd prime factor (that is 3 and 7). So, if we divide these type of positive integers by 2 repeatedly, we will eventually reach an odd number. That means if we can prove that all odd number will reach 1, then we simultaneously prove that all even integers that is not powers of 2 will also reach 1.

  • Case 2 : nn is odd

Let's see the function term of this conjecture.

f(n) f(n) = n2 \frac{n}{2} if nn is divisible by 2, and f(n) f(n) = 3n+1 3n + 1 if nn is not divisible by 2.

The term 3n+1 3n + 1 is always even for all odd integers, because for all odd integers nn, 3n3n is always odd. An odd number added with odd number will produce an even integer. So, 3n+1 3n + 1 is always even for all odd positive integers. This means there's no even-odd-odd pattern in a Collatz sequence. Now consider these terms when nn is odd.

nn -- 3n+13n + 1 -- 3n+12 \frac{3n + 1}{2}

Note that there will always be 3n+12 \frac{3n + 1}{2} after 3n+1 3n + 1 because 3n+1 3n + 1 is always even. Now we are going to use the term loop to define whether a sequence will have a number that appears more than 1 time.

For instance, on a Collatz conjecture, the sequence

4, 2, 1, 4, 2, 1

has a loop. If there's a loop on a Collatz sequence before we reach 1, then this conjecture is false.

So, where do we start? Well, we can look at the odd-even-odd term above. We can check if there is a positive integer nn that satisfies the third term is equal to the first term.

nn = 3n+12 \frac{3n + 1}{2}

2n2n = 3n+1 3n + 1

nn = 1-1

But here, nn can't be negative. Note that two consecutive numbers on a sequence can't be the same, since there is no even integer that is also odd integer (don't try to use infinity either). So, let's continue the terms above.

nn -- 3n+1 3n + 1 -- 3n+12 \frac{3n+1}{2} -- 9n+52 \frac{9n+5}{2} -- 9n+54 \frac{9n+5}{4}

(this time, we use the odd-even-odd-even-odd pattern).

Now let's check if there is a positive integer nn that satisfies the fifth term is equal to the first term.

nn = 9n+54 \frac{9n+5}{4}

4n4n = 9n+5 9n+5

nn = 1-1

We get the answer nn = 1-1 again. Actually, if you continue the terms and then check if there's a number that satisfies the (2n - 1)th term is equal to the first term, you will always get the answer nn = 1-1.

Why? Well, let's set the odd terms of the terms above into a sequence.

U[1]U[1] = 3n+12 \frac{3n + 1}{2}

U[2]U[2] = 9n+54 \frac{9n + 5}{4}

U[3]U[3] = 27n+198 \frac{27n + 19}{8} (you can check it for yourself)

From this, we can conclude that

U[a]U[a] = 3an+3a2a2a \frac{ 3^{a}n + 3^{a} - 2^{a}}{2^{a}}

From this, we can set the term U[0]U[0] = nn

Now we can check if there is a positive integer nn that satisfies the a-th term is equal to the first term.

U[a]U[a] = U[0]U[0]

3an+3a2a2a \frac{ 3^{a}n + 3^{a} - 2^{a}}{2^{a}} = nn

3an+3a2a 3^{a}n + 3^{a} - 2^{a} = 2an 2^{a}n

3an+3a 3^{a}n + 3^{a} = 2an+2a 2^{a}n + 2^{a}

3a×(n+1) 3^{a} \times (n + 1) = 2a×(n+1) 2^{a} \times (n + 1)

We cancel out the (n+1) (n + 1) term.

3a 3^{a} = 2a2^{a}

The number aa that satisfies this equation is aa = 00.

So, U[0]U[0] = U[0]U[0] , but this is always true. This means there is no positive integer aa such that U[a]U[a] = nn. In other words, there will be no numbers that will appear more than 1 time, or there will be no loop in all Collatz sequences.

So, all odd positive integers will always reach 1.

Now that we have prove that all odd positive integers will always reach 1, we simultaneously prove that all even positive integers that are not powers of 2 will also always reach 1.

Thus, all positive integers (odd integers, even integers that are powers of 2, and even integers that are not powers of 2) will always reach 1 ( Proven ).

So that's my proof of Collatz Conjecture. If there's something wrong, please tell me. Thanks :D

Note by David Saing
1 month, 1 week ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Just for some notation, you're using a modified version of the function; let's define g(n)={n2n even3n+12n oddg(n)=\begin{cases} \frac{n}{2} & n \text{ even} \\ \frac{3n+1}{2} & n \text{ odd} \end{cases}

You're looking at the sequence U[i]U[i] where U[0]=nU[0]=n and U[i+1]=g(U[i]U[i+1]=g(U[i], starting with an odd value of nn,

Where this goes wrong is the assumption that applying the function twice to an odd number will always give you an odd number. (You make this assumption where you say U[2]=9n+54U[2]=\frac{9n+5}{4})

This works for some odd numbers; for example, starting with n=7n=7 we get the sequence 711177 \to 11 \to 17, which is fine.

But it doesn't work for all odd numbers; for instance, starting with n=9n=9, we get 91479 \to 14 \to 7, whereas your formula suggests we should get 864\frac{86}{4} (which isn't actually an integer).

Don't be discouraged, though, it's worth exploring further. I'd suggest trying to answer the following questions:

  • which odd numbers disagree with the assumption that U[2]=9n+54U[2]=\frac{9n+5}{4}? What pattern can you find in these?

  • can you find a way to neatly write g(g(n))g(g(n)) in terms of nn? Using this, can you show that n=g(g(n))n=g(g(n)) has no solutions apart from n=1n=1?

  • could you continue with g(g(g(n)))g(g(g(n))) etc?

These functions will get complicated. One way to make sure you're not making any mistakes is to keep checking numerically.

Chris Lewis - 1 month, 1 week ago

Log in to reply

We have similar opinions.

Edward Christian - 1 month, 1 week ago

Log in to reply

Thanks for your opinion. If you get some ideas for the Collatz Conjecture, please tell me. I'd like to read some. :D

David Saing - 1 month, 1 week ago

Log in to reply

For the correction, actually 9-14-7 doesn't have a pattern odd-even-odd (the complete sequence's beginning is 9-28-14-7). Instead, it has the pattern odd-even-even-odd. The U[a] form only works on odd-even-odd-even pattern. Sorry, i didn't explain for other patterns other than odd-even-odd patterns.

David Saing - 1 month, 1 week ago

Log in to reply

I think there is a problem at this proof. Why will all the U[a]=3an+3a2a2aU[a]=\frac{3^a n+3^a-2^a}{2^a} work? According to your note, “Another pattern like odd-even-odd-even-even-odd or a sequence that doesn't have a specific pattern will work too, but odd-even-odd-even-odd is the easiest one to prove”, can you make sure all these loop will work? May you’re correct, but could you please explain this sentence more exactly? I think it’s a bit ambiguous.

When you proving U[a]=U[0]U[a]=U[0], there is a mistake about LaTeX. And for n=9n+54n=\frac{9n+5}{4}, n=1n=1? But I confess, your method is wonderful.

Edward Christian - 1 month, 1 week ago

Log in to reply

@ Edward Christian As in my note, patterns other than odd-even-odd-even-odd will also work. Actually what I meant is that no matter what pattern you find in a sequence, all the odd numbers in that sequence are all different, and all the even numbers on that sequence are all different. For instance, the pattern odd-even-odd-even-even-odd-even-odd will have all the odds different, and all the evens different too. Sorry for the ambiguousity.

And I think the patterns other than odd-even-odd will have a different property. Thanks for the correction.

I think the hard problem here is that sequences have different patterns each.

David Saing - 1 month, 1 week ago

Log in to reply

Yes, you’re right. There are lots of patterns. It’s impossible for us to prove every sequence. For most hard problem, we can’t use basic mathematics (in sometimes it can be true, but much more difficult than normal explanations). Perhaps we should correct the mistakes, or start over.

I’ve paid attention that you’re as old as me-just 14. As for us, the most important thing is to improve our abilities. And now, our abilities aren’t enough. So enjoy learning and improving by challenging ourselves!

Edward Christian - 1 month, 1 week ago

Log in to reply

Yes, I think I should learn mathematics more. With my math now, I think I could make some mistakes on working on some hard problems like this Collatz Conjecture.

David Saing - 1 month, 1 week ago

Log in to reply

Good try on trying to prove the Collatz Conjecture!

Yajat Shamji - 1 month, 1 week ago

Log in to reply

@Yajat Shamji Thanks! :D

David Saing - 1 month ago

Log in to reply

There's a great survey of results on Collatz by Terry Tao here. It also includes a mention of the 3n13n-1 variant.

Chris Lewis - 1 month, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...