## UNCRACKABLE? The Collatz Conjecture – Numberphile

3n-1? Brady, let’s try a 3n-1.. [Brady: in case you don’t know, Professor Eisenbud is the director at MSRI which is a huge supporter of Numberphile] [Brady: You can see more videos with Professor Eisenbud or other videos filmed at MSRI by clicking the links on the screen or in the video description] You draw that line, and then draw this line..

## 100 thoughts on “UNCRACKABLE? The Collatz Conjecture – Numberphile”

1. Numberphile says:

Catch David on the Numberphile podcast: https://youtu.be/9y1BGvnTyQA

2. Sage the Phoenix says:

Ok, roll with me here.
"3n + 1" is only used when a number is odd
"n/2" is used when a number is even
An odd number put into "3n+1" will always produce an even number
But an even number can have both even and odd divisors
Therefore, even numbers show up more often than odd numbers
Therefore, you end up using "n/2" a disproportionately large amount of times compared to "3n+1"
The "n/2" function should converge to 0 when repeated
"3n+1" gives a value of 1 when n=0
Since you use "n/2" an infinite amount more times than "3n+1" by the end of the infinite series of numbers…
the "n/2" function dominates "3n+1", and "3n+1" only becomes relevant for the convergence of the "n/2" series, which is 0
Therefore, where they both will always converge to when combined, is 1

Proves it to me…

3. Eduard Potapov says:

Доказал гипотезу Колаттца. Кому интересно пишите.
The Collatz conjecture is proved. Who cares, write a personal message.

4. TheFamousArthur says:

2÷2=1

5. TheFamousArthur says:

3×3+1=10
10÷2=5
5×3+1=16
16÷2=8
8÷2=4
4÷2=2
2÷2=1

6. TheFamousArthur says:

4÷2=2
2÷2=1

7. TheFamousArthur says:

5×3+1=16
16÷2=8
8÷2=4
4÷2=2
2÷2=1

8. TheFamousArthur says:

6÷2=3
3×3+1=10
10÷2=5
5×3+1=16
16÷2=8
8÷2=4
4÷2=2
2÷2=1

9. TheFamousArthur says:

7×3+1=22
22÷2=11
11×3+1=34
34÷2=17
17×3+1=52
52÷2=26
26÷2=13
13×3+1=40
40÷2=20
20÷2=10
10÷2=5
5×3+1=16
16÷2=8
8÷2=4
4÷2=2
2÷2=1

10. TheFamousArthur says:

8÷2=4
4÷2=2
2÷2=1

11. TheFamousArthur says:

9×3+1=28
28÷2=14
14÷2=7
7×3+1=22
22÷2=11
11×3+1=34
34=2=17
17×3+1=52
52÷2=26
26÷2=13
13×3+1=40
40÷2=20
20÷2=10
10÷2=5
5×3+1=16
16÷2=8
8÷2=4
4÷2=2
2÷2=1

12. TheFamousArthur says:

10÷2=5
5×3+1=16
16÷2=8
8÷2=4
4÷2=2
2÷2=1

13. Hank Moody Gaming says:

Looking at the branch he referenced, did anyone else notice that the values contained within it are our usual memory jumps? 64, 32, 16, 8. Sounds like an Ipod price step to me!

14. Trung Tran says:

Terence Tao solved it. Oneday he told me that he did not still want to up on the internet

15. jsturm5hk8h says:

3(1)+1=4

10…4…..Good Buddy.

3N+1=3(14)+1=3(5)+1=36=9
351
153 FISH
John 21
Matthew 4:20 Mark 1:17 Luke 5:2

EXACT & REAL Pi = (14 – root2)/4 = 3.14644660941…

8 Pi Square – 56 Pi + 97 = 0

man… I can write you 3 lines of code, that will mess number in such a way, tham 1000 math professors will not understand there it is going to.. so what? does this make anyone special?!

18. goldenera7090 says:

here is my attempt to prove Collatz Conjecture by contradiction:
If this is not true, then it means we have a number N, which loops back to N instead of going down to 1.

obviously this number N can't be even so has to be odd.

which means

when we reach number N, we multiply by 3 and add 1 giving 3N + 1

now this 3N + 1 has to be divided by 2 to reach N but we don't know how many times it has to be divided by 2.

let us assume this is a times.

this gives us an equation:

N = (3N + 1) / 2^a

or

2^a N = 3N + 1

(2^a -3) N = 1

so when a = 1 , N = -1

a = 2 , N = 1

a >=2 , N has to be a fraction.

this proves that for all other integer value of N the conjecture holds true…..

19. jnielsen20 says:

Ehm, how can this be a problem? The only way a starting n can inflate to infinity is if it all values of (2n+1) is primes, otherwise it will always collapse to 1. Unfortunately for us the average distance between primes must all ways increase. 1/2 of all integers are even, 1/3 is a multiple of 3, 1/5 is a multiple of 5, 1/7 is a multiple of 7 and so forth. Therefore we can never have a sequence of primes satisfying the distance requirement of 2n+1 to infinity as the average distance between the primes must increase ever faster the higher we go into the numbers.

20. JeaNFrancoiS Irisch-Mercier says:

Love it 😍 😍 😍 🔥

21. x Ludicrous x says:

All the odd numbers were prime. Is that helpful?

22. sam jones says:

The first number should be 2^n-1. Then you will get at least n odd numbers. The largest number
will be at least (2^n-1)* 1.5^n Imagine the results if n is a very large number!

23. Claudio Brogliato says:

The only pattern I see is that powers of two with even exponential, once you subtract one, become odd numbers that can be divided by 3.

24. Andrew Crowe says:

Dont draw it in a tree, use circles

25. Kem JM says:

It's not possible to not get to one because if you take any odd number ending in the digits 1,3,5,7,9 and multiply it by 3n + 1 it will always give you an even number and all even numbers are divisible by the number 2 and so they would eventually end up being the number 2 and as we know 2÷2 = 1

26. Rnishu _ says:

I chose 1

27. Rnishu _ says:

28. Tejas Pathak says:

But what's the problem here?

29. Max Rumplestiltskin says:

"Like the pattern of always going to one. That one holds sure but we don't understand why it's there." When you multiply a number by 3, add one, and divide by 2, the result tends to be 1.5 times bigger than the starting number. When a number is divided by 2, it is always 2 times bigger than the result. I think it is intuitive that you will always get to 1 because there half of numbers are odd and half are even. When you land on an odd number you grow less than landing on an even number takes you down.

30. Connor Arsenault says:

Could this problem just exist as one of those sets of problems that are impossible to solve given the set of axioms which it exists under? @Numberphile you should do more videos on what makes a problem able to be solved and what doesn't.

31. Nightfury Matthew says:

I really hate that guy's voice.

32. Arka Chanda says:

I choose zero

33. Xboxgamer12346 says:

Have we tried looking in the complex world instead of the real? The rules don't clarify if we have to just use real, whole numbers. So why not go through with the experiment of using an integer times the sqrt of -1 and proceding with the conjecture?

34. Seth Gilbertson says:

I use this pattern in my 4th grd math class! It’s awesome!

35. Huzaif Barkati says:

I have been trying to prove this from the past 2 years and I have a pattern on the behaviour of odd numbers belonging to type. These numbers can have (3n+1)/4 as the direct step instead of (3n+1)/2 and you will get another odd number. By type I mean if you take a finite amount of odd numbers then it will constitute 80 percentage of those numbers. These numbers have this common property and I am stuck in the rest 20 percentage.

36. manman ren says:

😂

37. Amumu Yordle says:

I found a truly marvelous solution to this problem. The conjecture is true but the proof is too long to fit into this comment box.
First observe that numbers generated by this procedure cannot be multiples of 3. Hence if the conjecture is true for non multiples of 3, then it must also be true for multiples of 3.
Next we split the non multiples of 3 into 4 sets A, B, C, D where A=4 (mod 6) B=2 (mod 6) C=1 (mod 6) and D=(5 mod 6), where the numbers are grouped based on their remainder when divided by 6. Observe that from A we can go to B or D, B goes to A or C, C goes to B or D and D goes to B or D depending on the parity of the number and that the numbers in each set form an arithmetic progression with common difference 6. Let u_n denote the nth term of each set. The trick is to work in terms of n, the indexing number instead of u_n, the numbers themselves.
More specifically, if k is the indexing number, then from A we apply (k+1)/2 and go to B if k is odd and k/2 and go to D if k is even. From B we apply (k+1)/2 and go to C if k is odd and k/2 and go to A if k is even. From C we apply (3k-1)/2 and go to B if k is odd and (3k-2)/2 and go to D if k is even. From D we apply (3k+1)/2 and go to B if k is odd and 3k/2 and go to D if k is even.
It suffices to show that any number from set D will eventually end up at 1. Starting from D, we can construct the following tree based on the remainder when k is divided by 2^n, where n is a natural number.
To illustrate, if k=0(mod 2) it stays in D. If k=1(mod 2) it goes to B. From B it further splits to 2 branches. If k=1(mod 4) it goes to A and if k=3(mod 4) it goes to C. The third layer: If k= 5(mod 8) it goes to D, if k=1(mod 8) it goes to B, if k= 7(mod 8) it goes to D, if k=3(mod 8) it goes to B. This tree continues splitting indefinitely.
This leads to the following lemma: Given any valid finite sequence of A, B, C and D, there exists infinitely many numbers in set D which follow this sequence down the tree.
The consequence of this lemma is that we can always find a number that becomes very large by choosing a string of D or BC or by going through the cycle DBC many times. However this process must eventually stop because the index of any number in set D has a finite binary representation and at the dth layer of the tree, where d is the number of digits in the binary representation, the index must follow an endless string of zeros down the tree.
It remains to show that the endless string of zeroes must lead to 1. We can construct the dth layer by observing that numbers in this layer are of the form (3^a*k+b)/2^d, where a takes values from 1 to d-1, k is the original index and b is chosen to ensure that the expression is an integer. Now, the distribution of the values of a follows that of the dth row of the Pascal triangle….

So what are mathematicians trying to prove with this problem?

It goes to one for all numbers. Trust me. QED

40. Kilian Bauer says:

Isn't this just due to the possibility of going down several times- all even numbers that double an even number (50%)- while it is never possible for an odd number to create another odd number? I mean it's not a proof of course but feels so obvious? This game is played without a limit so in the end the higher probability will always prevail.

41. Ronnie 6767 says:

So they are tryig to understand why this happens? All numbers will always go to 1? I came here from boinc, there is a distributed computing project for this.

42. Máté Tóth says:

When our computers will have enough memory, we might be able to get into a loop, that also starts and ends between two powers of 2.

43. Juan SAMUDIO says:

Do they have to be whole numbers?

44. Tanmay Pawar says:

What if we use an imaginary number like 7¡

45. Heart2HeartBooks says:

This should be called what it is…."Math Doodling." It is just a kids game…Nothing more.

46. Gastón Fernando Murillo Plúas says:

Why uncrackable when all odd numbers calculated with the 3n + 1 algorithm are grouped into ordered subsets?

how can a tree have a cycle?

48. basavaraj chintamani says:

6d-4a=c it is a new formula for find circumference. Without pi π

49. Lucky Singh says:

Look…. If we took i^2 = -1 then if we took 7i^2 as our no. We get -7 so…. It will be like this in short we took -ve integer then -7(3) +1 =-20 =-10=-5=-14=-7 look we come to exact same no. Where we have been… Before!!

50. Mal Harr says:

Why is this a problem

51. Dylan Lundberg says:

Doesn’t it make sense that it goes to the 16 8 4 2 1 loop because all odds become even if you multiply by 3+1. And evens can be divided by two to bring the number down? Evens divided by 2 can be equal to another even that can be divided by two unlike the odd number equation that always be even, meaning overall, all numbers that go through this process will tend towards smaller numbers, and those smaller number will tend to even smaller numbers until it reaches the 16 8 4 2 1 loop?

52. Claire Annette says:

I’m not an expert math person, but I am way more advanced than the average person. I wouldn’t know how to formally prove it, but it seems pretty obvious to me.

If you choose an even number for the first term, then the second term will be either odd or even.

If you choose an odd number then the second term will be an even number.

Of all the possible whole numbers as first terms, you could say there’s a 2/3 chance that the second term would result in an even number.

This is the same for the third, fourth, fifth, and so on. You will eventually reach a power of two which will ultimately lead you to 1. Then you’re stuck in the infinite 4, 2, 1 loop.

I say the proof is in probability and the powers of 2.

Someone prove it and give me credit.

53. Gabriel Axelsson says:

Me and my firend is about to crack it.

54. Gabriel Axelsson says:

a clue is to think in layors.

55. Dávid Palmer says:

How about try proving it always reaches a power of two (don't know how just an idea) and after because of the rules of how you go about it will come to one.

56. Dávid Palmer says:

What about x times n +1 or x times n -1 where x is a whole number? Does this lead to somewhere anyone looked it up?

57. Steven Katz says:

Seems to me that all we have to prove is that, playing the Collatz game, every odd number n results in a number smaller than n. Then we can use strong or weak induction to show that the conjecture is true for all numbers 1 to k.

58. fyfferguy says:

To the OP: What is the source of the graph I see in the "collage" at 2:45? It's the one in the bottom center of the screen with the red dots on white background. This is exactly the data set that I have been playing with since I first heard of this problem in my college days over 25 years ago. I'd never seen the data presented that way before, and then I saw "my" graph in your video! Thanks in advance! (and hopefully someone will see this … 🙁 )

59. Fujtajblus says:

I tried something different. I took 0,11 and it keeps going up. I think the problem talks about using whole numbers, right?
If you use any number between 0 and 1 and go trough this cycle will eventually go up.

60. James Billson says:

2

61. Eric Quinn says:

62. Rylac Zero says:

Seems kinda obvious. Collatz conjecture is entangled with Goldbach conjecture.

63. MySpeed says:

"Woah, 16. That's a very even number."
My favorite quote.

64. Deeann Mathews says:

I'm not a mathematician, but I do see a couple of patterns holding sure … No matter what number you start with, the iterations of 3n+1 for odds and then dividing by two for evens over time is essentially pushing out odds and adding evens, and even more specifically, pushing out all factors except those of 2.

Any odd number — including prime factors — are eliminated successively from the next result because the next result is either even, and so divided down to find a new odd number, or, that odd number is multiplied into something that is essentially going to be n-many threes with its last three made into a 4 by adding one to it. As the trees were being shown, I could see a growing preponderance of numbers that not only were even but had more and more factors of 2 until finally a power of two was hit somewhere.

We know that since there are infinitely many primes, there are also infinitely many prime factors that can show up in larger and larger numbers… but so long as any and all of them will get bumped to n-many threes plus a 4, and then divided down, the results will all get nudged toward the infinitely many powers of 2 that there are as well, no matter where you start.

The Numberphile video about prime squares, and its exposition of primes above 2 and 3 being of the form 6k plus or minus 1 also comes to mind… obviously every prime is one away from a numeral of 2 and a bunch of them one away from being a numeral of 4. Play a simplified game with just these primes and add one and then divide by two, and a similar shower of hailstones results.

So: it should only be necessary to prove the Collatz Conjecture for all primes, since all non-prime positive whole numbers except 1 are composites of prime number factors. If all primes but 2 and 3 are some 6k plus or minus 1, they all should yield and get nudged out of the iterations as they occur without any repeating patterns before hitting a power of two — and if that is true, then all the numbers made up of those factors must yield too.

65. Stephanie Rideout says:

Oh lord I remember this from my number theory class….. Ack

66. Steven Sutton says:

do you take question about youre podcast

67. Aswini Banerjee says:

Who is here from IYMC ?

68. Konata says:

Seems to me like if you were writing a computer program to check the numbers in sequence, you would never start with an even number, because dividing it by two would always result in a number you have already checked.

69. T. says:

Try Graham's Number

70. Till Aufgebauer says:

3*1+1=2 not 4

71. ATVthe King says:

0 never goes to 1????

72. ATVthe King says:

Also, has anyone proved it for x/2 for even and 3x-1 for odd

73. hfe18 says:

"every problem has solution…if there's no solution means its not a problem" , why mathematicians worrying too much for this???

74. vikingslayer34 says:

Who else wrote a program to test this?

Anyone else wondering how complicated variables would be for the Romans

76. narotam sharma says:

Does we getting same result if for odd number we take 9n+5

77. Asif Hossain says:

Isn't i obvious? If n is even n/2 and if n odd 3n+1, making it even again and meaning you are lessening factors and ending up with the least factor 2. Resulting 1.

78. Fish767 says:

For anyone that does want to try this on your computer, set it up so it only tries odd numbers because an even number will become a smaller odd number and if the number resulting from doing these rules becomes less than your starting number you will have already tried it and it will fail. Also if the number is divisible by 4 right after an initial (3n+1) it fails because that would be (3n+1)/4 and that is always smaller than your starting number. I am going to try to solve this later. I have a fun idea around seeing how many times you can multiply by 3 and add 1 before it becomes divisible by 4. I think primes will be the best to work with.

79. fit4ever says:

i didn't understand the problem very well ?if you keep pushing even numbers you will 100% reach to one of power of 2 numbers which will lead you to 1 by division of 2
n(even)/2-> even or odd

3(odd)n+1>even

IF you keep applying the rule you will eventually reach to one of power of 2 numbers
Then you will go down and down to 421 because 1 is odd number the loop will happen.
Same problem :
n(even)/2
3(odd)n+3
You will end up with
12 6 3 loop

80. prog rock says:

Spin a dime, a penny, a nickel, or a quarter: they'll have all fall flat and flat is one.

81. SAAR3KT says:

What if you put in zero

82. cringe boy says:

If we could prove that all numbers somehow reach a power of 2 within the rules stated, wouldn’t that be a proof in itself? Because if all numbers eventually reached a power of 2 the power of 2 would drop all the way to 4 then to 2 then to 1.

83. Magicianofwords says:

Every state in universe must return to its initial stage. Maybe this is what collatz conjecture suggests. 🙂

84. tommy karrick says:

I’ve watched this video so many times and this is so frustrating because it is so intuitive and clear that every number will obviously get to one and yet we can not prove it

85. Sharmin Akter says:

what about 0,0/2=0 so you repeat

86. Makozer says:

ive written this shortly in java and my system counts just 378 steps for "63728127" ( timestamp: 6:45 ) … ??? and what are these tables at 6:17 ? 8 always just needs 3 steps to reach 1, not 15 .. o.O

87. Nikunj Majithia says:

Hey sir how are you, what you did was awesome but
I did trail and error some thing
F plus 1 is the answer I dont think I any other way will work it's kind of the case complex problems have answers within them

88. Dfghdfgh Uytiu says:

Try n= 27 just for fun

David mentions Jeff Lugari at the beginning of the video. He says he's "a mathematician I admire a lot". Who is he? Does he have a website??

90. Alexander Townsend says:

I have a challenge for everyone in the comment section. This might spur a discussion. What are some interesting ways to rephrase this problem and or reframe it in a different context.

Here is what I came up with.
1. The original version.
2. Prove that natuarals collapse to a power of two.
3. Prove either that all even or odds reach a power of two. (A proof for the odd numbers proves it for the even numbers and vice versa).
4. (Someone propose something for the next step.) Where should I go from here?

What is the probability that at some point the number will not be a power of 2? Is the probability ever 0?

92. Aric Floyd says:

The problem so hard even the cover of the textbook can't get it right (5:09)

93. Ahmed _pro says:

S(2*(ODD)+1)>ODD
S MEANS THE STEPS TO REACH ZERO AND I HAVE A REAL PROVE FOR IT AND I AM Serious

94. Saatwik Katiha says:

"I bet the person who found it thought maybe he was on to something…"

I'm willing to bet the guy who found the tree for 63,728,127 wasn't sitting down and doing it 😂

95. S. E. says:

The sequence of Collatz will always hit a power of 2 after finite tries, so it will end up to 1.

96. kevin degn says:

Seems kinda built in to the equation to always get to one. Seeing as multiplying an odd number by 3 and adding one will always be even and you will always eventually hit a point with an even number that you can halve multiple times and it seems that’s why it will always lead to one. As far as some kind of equation that proves that? That’s way beyond my math skills.

97. sudha kumari says:

he said whole no. so take 0
btw was it whole or natural no.