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..
I find Professor Eisenbud to be one of the more underrated professors in Brady's videos.
Just made a basic version of the code in python. Here it is:
#defines the collatz function
def collatz():
collatz()
Bit late, but one interesting tidbit: the "general" Collatz problem is undecidable (paper about it). I.e., instead of 3x + 1, there are versions of the form mx + b (where m and b are integers) where it is impossible for us to know if the pattern always returns to 1.
I really liked trying to tackle this problem.
From my calculations the iterative n = 3n/2+1/2, n/2 has the solution (1 + n*3x + Sum(3k)[k = 0, x-1]) / 2x+y
Regarding the loop: For a loop to occur we get that (1 + n*3x + Sum(3k)[k = 0, x-1]) / 2x+y = n where x is the number of odd steps (with the extra even step added in) and y is the number of proper even steps.
This means that loops can only occur for numbers n of the form n = (1 + Sum(3k)[k = 0, x-1]) / (2x+y - 3x) which is true for n = 1, x=1 and y=1 (the number 1 loop)
The number must also be in the sequence of x odd and y even fitting to the actual odd and even numbers that is possible by the x and y values.
Interestingly enough the limit of the equation when y -> infinity is (-3-x/2)*(3x2 - 3x + 2) which has an asymptote towards negative infinity at -7 (which is a loop) but has no positive solutions.
Regarding the infinity series: I think if you could prove that the density of even numbers that is divisible by at least 22 (or some bigger power of 2) is denser than at least every 3 or so even numbers then you could prove that the series wouldn't go to infinity since the value would eventually go towards 1 or get stuck in a loop on the way. It would then sooner or later be less than what the starting number was and this proves that it would go to one since we have tested all lower numbers to also go to one.
EDIT: formatting