UNCRACKABLE? The Collatz Conjecture – Numberphile

UNCRACKABLE? The Collatz Conjecture – Numberphile


Jeff Lagarias, a mathematician I admire a lot, thinks it’s one of the hardest problems around. Erdos actually said “this is a problem for which mathematics is perhaps not ready” Turns out that all this fuss is about a problem that any fourth-grader can understand. To show you how this all works I’m gonna give you an example: Brady, chose a number between one and ten. [Brady, off camera: I shall go for seven] Alright, let us start with seven. Now, I’m gonna apply two rules depending on what number I get I’m gonna do this in succession [..] then if n is even I’m gonna take n and divide it by two If n is odd then I’m gonna take n Can’t divide it by two and get a whole number so I’m gonna take n and multiply it by three and add one Those are my rules. and I’m interested in what happens to n. Does it grow to infinity? Does it get small? let’s see what happens with 7 7 seems to be an odd number, so I multiply by 3 and add 1. Three times seven is 21 check me on this, and add one is 22. I go to 22. 22 is certainly even so I’ll divide by two and get eleven. Eleven is odd, so I’ll multiply by 3, getting 33 and add one and get 34. 34 is even, I divide by 2 and I get 17 so far it’s going up and down. But 34 was the biggest yet, so maybe it’s headed off to infinity after all. 17… so 17 is odd, I multiply by 3 3 times 10 is 30, 3 times 7 is 21. 51 plus 1 is 52. Even. divide by 2 and get 26. still even. divide by 2 again and get 13. now it’s odd. multiply by 3 and add one. 40. 40 is even. I divide, I get 20. I divide again I get 10. I divide again, I get 5. Boy, we fell down a long way! Maybe we’re heading for a small number after all. multiply by 3 and add 1, I get 16. Whoa! 16. VERY even number! I get 8. I get 4. I get 2. And I get 1. If I do it again, something interesting happens. I go 3 times 1 plus one is four. whoops, I’m back to 4. But now I’m just going to cycle forever, going through 1 over and over again. So I got to one. Seven got to one. Now, people have tried lots of numbers beginning this way, and so far, all of them have gone to one. They’ve tried roughly two to the sixtieth numbers, that’s almost ten to the twentieth… So the famous Collatz conjecture says that every number, every whole number, will eventually get to one. And a huge amount of work has been done on this problem by combinatorialists, by number theorists. This is the problem that maybe mathematics is not ready for, but that any fourth grader could play with and try, right? Try some numbers. First of all, we’d like to understand what’s happening, in such a way that we can say for certainty that every number, all the numbers we haven’t ever tried, WILL get to one. You could just try this on your computer; it’s a good test for your personal computer too. How fast a program can you make? Here’s a little hint. Every time I take an odd number and multiply by three and add one, I get an even number. So why not take two steps at once? to three n plus one over two. Combine those two steps… when I get and odd number. that speeds things up a bit. And there are other tricks like that. So people make graphs like this, and they’re called “trees”. Right. So far, all the number go down to one, but we might start with another number.
If we started with five, we already see what the answer would be. Any number that appears here, we already know the answer. We don’t have to do it again. What’s the first number that doesn’t appear here? I think it’s six. Shall we try six? [Brady, off camera: Let’s do it!]. Let’s do it. okay, 6. And 6 goes, well, it’s even. Goes to 3. 3 goes to 10. And we got 10. Whoops, there’s 10 So, I should just draw the 3 going down to 10 instead. And now I know, I’m beginning to build up my tree. And now I’ve tried now all the numbers up through seven. Uh, 8 I got. 9 I thought I had somewhere. Didn’t I have a nine? [Brady: I can’t see a nine]. No, I don’t see a nine. Let’s try nine. So, nine. ok. Odd number. three times nine plus one: 28. 28, 14… whoops, seven. Where’s my seven? There it is. Goes to seven. So I can begin doing this and build up my tree. I don’t have to go all the way each time. I know what’s going to happen after I get to seven. If you look at the cover of this book that I showed you first, that’s a tree of just this kind. But people have built up HUGE trees of this kind. And there’s a wonderful article on Wikipedia which you can look at which shows some of the pictures of this. [Brady: there. there does seem to be a very striking feature of it, and this is this line down the middle here]. Yes, that’s right. This is like the third rail. Once you touch that line, you fall right away to 1. By the way, there’s another name for the this problem, which is the Hailstone problem. And the reason is, as you probably know, when hailstones form in the clouds, the way they form, the way they get bigger, is that they start low and they get blown up by the winds, and they get some ice on them. And they fall down a bit, and then they go up and down. They go up and down many times. and finally they fall to Earth. If they never get to Earth, then of course they’re not hailstones. And it’s just like numbers here. They go seemingly randomly up and down and up and down and then eventually they seem to fall to one. To the ground. What kind of things have people done with this funny funny problem? Well, they’ve compiled, for instance, records I, I got a long string with seven. What’s the next number after seven which gives a longer string? well, it’s not 8. 8 is down here. we found it already, it’s 9. Nine only goes through seven. What’s the next number after that? Well, you can look on the online encyclopedia of integer sequences, that great resource and you’ll find a table of the record holding numbers. You’ll also find a table of the numbers that hold the record for the longest time to get to one. Let’s get a couple of examples here. There’s some wonderful ones. For instance, the longest , the one, the record holder, for the numbers under a hundred million, people, people know all these things, is 63,728,127. and that takes nine hundred and forty nine steps to get to one. I bet the person who found it thought maybe (s)he was on to something Maybe finally had a counter example. But no. There are records and records and records. And people have tabulated this looking for patterns that might help them understand what’s really going on. So the randomness of this is what seems to make it hard. The fact that you don’t see a pattern and that no matter how hard you look, the patterns you see tend to be illusory somehow. They, they melt away when you look further, or you don’t understand them. Like the pattern of always going to one. That one holds sure, but we don’t understand why it’s there. [Brady: If you’d like to see even more of this interview about the Collatz Conjecture, I’ve posted it at Numberphile2]. Why 3n+1? Why not
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. 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…

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

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

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

  5. 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!

  6. 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?!

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

    …..comments??? no trolling please …..

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

  9. 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!

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

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

  12. "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.

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

  14. 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?

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

  16. 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….

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

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

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

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

  21. 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!!

  22. 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?

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

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

  25. 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?

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

  27. 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 … 🙁 )

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

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

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

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

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

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

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

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

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

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

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

  39. 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??

  40. 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?

  41. "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 😂

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

Leave a Reply

Your email address will not be published. Required fields are marked *