# 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 $n$. If $n$ is even, then divide it by 2. If $n$ 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 \times 3$ $+1$ = $10$
• 10 is even, so the next term is $\frac{10}{2}$ = $5$
• 5 is odd, so the next term is $3 \times 5$ $+1$ = 16
• 16 is even and it is a power of 2 ( $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 $n$. The first case is that $n$ is even, and the second case is that $n$ is odd.

• Case 1 : $n$ is even (powers of 2)

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

If $n$ = $2^{m}$, then $\frac{n}{2^{m}}$ = $1$

By dividing a power of two $2^{m}$ with two $m$ 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 : $n$ is odd

Let's see the function term of this conjecture.

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

The term $3n + 1$ is always even for all odd integers, because for all odd integers $n$, $3n$ is always odd. An odd number added with odd number will produce an even integer. So, $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 $n$ is odd.

$n$ -- $3n + 1$ -- $\frac{3n + 1}{2}$

Note that there will always be $\frac{3n + 1}{2}$ after $3n + 1$ because $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 $n$ that satisfies the third term is equal to the first term.

$n$ = $\frac{3n + 1}{2}$

$2n$ = $3n + 1$

$n$ = $-1$

But here, $n$ 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.

$n$ -- $3n + 1$ -- $\frac{3n+1}{2}$ -- $\frac{9n+5}{2}$ -- $\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 $n$ that satisfies the fifth term is equal to the first term.

$n$ = $\frac{9n+5}{4}$

$4n$ = $9n+5$

$n$ = $-1$

We get the answer $n$ = $-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 $n$ = $-1$.

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

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

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

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

From this, we can conclude that

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

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

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

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

$\frac{ 3^{a}n + 3^{a} - 2^{a}}{2^{a}}$ = $n$

$3^{a}n + 3^{a} - 2^{a}$ = $2^{a}n$

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

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

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

$3^{a}$ = $2^{a}$

The number $a$ that satisfies this equation is $a$ = $0$.

So, $U[0]$ = $U[0]$, but this is always true. This means there is no positive integer $a$ such that $U[a]$ = $n$. 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
11 months, 2 weeks ago

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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Just for some notation, you're using a modified version of the function; let's define $g(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]$ where $U[0]=n$ and $U[i+1]=g(U[i]$, starting with an odd value of $n$,

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]=\frac{9n+5}{4}$)

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

But it doesn't work for all odd numbers; for instance, starting with $n=9$, we get $9 \to 14 \to 7$, whereas your formula suggests we should get $\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]=\frac{9n+5}{4}$? What pattern can you find in these?

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

• could you continue with $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.

- 11 months, 2 weeks ago

We have similar opinions.

- 11 months, 2 weeks ago

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

- 11 months, 2 weeks ago

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.

- 11 months, 2 weeks ago

I think there is a problem at this proof. Why will all the $U[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]$, there is a mistake about LaTeX. And for $n=\frac{9n+5}{4}$, $n=1$? But I confess, your method is wonderful.

- 11 months, 2 weeks ago

@ 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.

- 11 months, 2 weeks ago

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!

- 11 months, 2 weeks ago

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.

- 11 months, 2 weeks ago

Good try on trying to prove the Collatz Conjecture!

- 11 months, 2 weeks ago

@Yajat Shamji Thanks! :D

- 11 months, 2 weeks ago

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

- 11 months, 2 weeks ago