The Simplest Math Problem No One Can Solve - Collatz Conjecture

添加 2021年07月30日
The Collatz Conjecture is the simplest math problem no one can solve - it is easy enough for almost anyone to understand but notoriously difficult to solve. This video is sponsored by Brilliant. The first 200 people to sign up via brilliant.org/veritasium get 20% off a yearly subscription.

Special thanks to Prof. Alex Kontorovich for introducing us to this topic, filming the interview, and consulting on the script and earlier drafts of this video.

▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
References:
Lagarias, J. C. (2006). The 3x+ 1 problem: An annotated bibliography, II (2000-2009). arXiv preprint math/0608208. - ve42.co/Lagarias2006

Lagarias, J. C. (2003). The 3x+ 1 problem: An annotated bibliography (1963-1999). The ultimate challenge: the 3x, 1, 267-341. - ve42.co/Lagarias2003

Tao, T (2020). The Notorious Collatz Conjecture - ve42.co/Tao2020

A. Kontorovich and Y. Sinai, Structure Theorem for (d,g,h)-Maps, Bulletin of the Brazilian Mathematical Society, New Series 33(2), 2002, pp. 213-224.

A. Kontorovich and S. Miller Benford's Law, values of L-functions and the 3x+1 Problem, Acta Arithmetica 120 (2005), 269-297.

A. Kontorovich and J. Lagarias Stochastic Models for the 3x + 1 and 5x + 1 Problems, in "The Ultimate Challenge: The 3x+1 Problem," AMS 2010.

Tao, T. (2019). Almost all orbits of the Collatz map attain almost bounded values. arXiv preprint arXiv:1909.03562. - ve42.co/Tao2019

Conway, J. H. (1987). Fractran: A simple universal programming language for arithmetic. In Open problems in Communication and Computation (pp. 4-26). Springer, New York, NY. - ve42.co/Conway1987

▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
Special thanks to Patreon supporters: Alvaro Naranjo, Burt Humburg, Blake Byers, Dumky, Mike Tung, Evgeny Skvortsov, Meekay, Ismail Öncü Usta, Paul Peijzel, Crated Comments, Anna, Mac Malkawi, Michael Schneider, Oleksii Leonov, Jim Osmun, Tyson McDowell, Ludovic Robillard, Jim buckmaster, fanime96, Juan Benet, Ruslan Khroma, Robert Blum, Richard Sundvall, Lee Redden, Vincent, Marinus Kuivenhoven, Alfred Wallace, Arjun Chakroborty, Joar Wandborg, Clayton Greenwell, Pindex, Michael Krugman, Cy 'kkm' K'Nelson, Sam Lutfi, Ron Neal

▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
Written by Derek Muller, Alex Kontorovich and Petr Lebedev
Animation by Iván Tello, Jonny Hyman, Jesús Enrique Rascón and Mike Radjabov
Filmed by Derek Muller and Emily Zhang
Edited by Derek Muller
SFX by Shaun Clifford
Additional video supplied by Getty Images
Produced by Derek Muller, Petr Lebedev and Emily Zhang

3d Coral by Vasilis Triantafyllou and Niklas Rosenstein - ve42.co/3DCoral
Coral visualisation by Algoritmarte - ve42.co/Coral

评论

  • Binfords law can detect irregularities in ballots, except in the 2020 election that is………..

  • 0

  • Awesome

  • Where's the "="?

  • There's nothing random about the stock market. It is highly manipulated by central banks, governments, corporations and financial whales.

  • I'm sorry I can't get over this... how the hell do most numbers start with 1? This is breaking my brain and I feel like it shouldn't work, because there's always just another number and it's not like the number of potential options is changing. There's only 9 options so shouldn't it be 1/9th for each option with a slight exception in zero?

  • If from 1 every other number is odd, and from 2 every other is even, 0 is nether even or odd and both even and odd. 0÷2=0 is infinite, 0×3+1=1 falls into 4,2,1 cycle

  • 10

  • X = 1

  • There is no problem.

  • Extrapolating from the end - the 4-2-1 result - if the conjecture is correct, we only need to prove that at some point the iterations of 3x+1 eventually hit a power of 2, at which point it reduces to 1 no matter what. Since powers of 2 are as infinite as counting, this is possible. We can ignore all even numbers as an initial seed because a divide by 2 often enough will lead to either an odd number eventually or 1, if the even number is a power of 2. So we can focus our initial seed as an odd number. (Conversely, any even number that would disprove this theory first reduces down to a smaller odd number before taking off, hence using even numbers as an initial seed to try to disprove this is a waste of time. For example, let's say the number 102 would disprove it. First step, divide by 2, we get 51. So, if that were true, we would have discovered at an initial seed of 51 that it disproved the conjecture, and would not have reached 102 ever - there would have been no need to.) My question now becomes, is there a mathematical way to prove that, for any given odd number, the function (3x+1)/2 has a maximum application iteration before it reaches a power of 2 and is then forced down to 1? Note: given that powers of 2 geometrically increase with each step up, it wouldn't surprise me if the number of times the function has to be applied to reach a power of 2 also increases geometrically as the numbers go up. If this is so, logically the solution would involve a power of 2 calculation to extrapolate the maximum iteration for this to happen. At this point I would want to generate samples to observe and see if there's a pattern that can be extrapolated and translated into a formula to demonstrate this. If supercomputers have already computed that all numbers up to 2^68 resolve down to 1, we have plenty of samples to work with. Side note: I was that kid that extrapolated the quadratic formula in Algebra class in 8th grade several days before it was taught to me, in an effort to "solve for x" more efficiently than using "completing the square" and such. I just chose to go into engineering instead of mathematics as a career. I may come back to this when I have more time. Back to work for me...

  • I feel like it can't be proven because it's not a truth, it's a tendency, and a proof would disprove outliers. Try to prove a tendency, you're in tough water. Demonstrate one, sure.

    • I meant to add the equation itself is naturally reductive so eventually it reduces itself into the smallest amount it can realize.

  • I don't know if you read these, but I have a theory and I'm curious as to whether you think it would work, and if not, why? Begin with a very very large number, and allow a computer to make these calculations, and save every number it ran into. Now have this computer restart at 1 higher, and any time it strikes a saved number it terminates, knowing that outcome will be the same from where it landed, and restart one higher. At the same time have a second computer begin making calculations from the bottom, filling in any holes the first computer does not. These two computers can share a database of numbers, and repeat this process until almost any smaller number is already accounted for. This would allow for a shortcut to calculation, allowing a computer to calculate significantly more numbers in a given time frame, and also significantly lower the "playing field" of possible numbers over time.

  • I have found the solution. I will release it for 100 bitcoins.

    • lmao

  • This is how we go back in time

  • First of all they're looking at it backwards, they should pay attention to 1,2,4 not 4,2,1, and another hint is 1,2,4,8,7,5. Good luck

    • Again, this is not a "problem" and does not have a "solution". The visible patterns and Fibonacci distribution should tell anyone with understanding this is not something you can break or introduce chaos into.

    • In the tree graph, you may notice, it begins with 1,2,4,8,16 (1+6 = 7) and then to either side of 16 you have 32 (3+2=5) and 5. You will after notice two different types of branches. One type of branch will follow this infinite pattern of 1,2,4,8,7,5. The other type of branch will repeat the alternating pattern of 3,6,3,6,3,6....... There is no problem to be solved here, only things to be realized. Anyone who truly wishes to understand what is going on here may start by researching Nikola Tesla and 3,6,9

  • Tony Stark and Shuri probably solved this as children for funsies

  • I’m pretty sure the answer is 1*1=2.

  • Did they test one Gazillion? I have a feeling about this one.

  • Interesting but seems useless. Math is full of such weird looking phenomena but most of these phenomena are form due to the very nature of math.

  • I still don't get why is that a problem

  • 3 + 1 = 4. 3 x +1 = ?. The x is what's messing people up. x is the 24th letter of the alphabet. 3 + 24 = 27. 27 + 1 = 28. Answer: 28. (Please take this comment as a joke)

  • I solved it! No, because of 0. If you divide 0 by 0, you get undefined and even if you still got 0, you would be stuck at 0 forever.

  • lol, I still don't understand what they are trying to solve.

  • Lucky I have my calculator 😁

  • 3x(+1).

  • rule Even/2 represent At present, the double number of 2^68 is not exhaustive... The double number of 2^68X2 is not... 2^68X2X2 is not twice the number... Infinite loop 規則 偶數/2 代表 目前窮舉2^68的兩倍數都不是... 2^68X2的兩倍數也都不是... 2^68X2X2的兩倍數也都不是... 無限循環

    • 3x+1 1 Why is it so special? 1 cannot be reversed In this rule, 1 is 0 1 is an odd number, presumably some N*3+1 N*3+1=1,N*3=1-1 N*3=0,N=0*3,N=0 So 1=0 1 is produced by 2 even numbers~ 2/2=1, 1*2=2 1

  • Did any math hero tried to find a function / rule for the negative case that leads to a similiar loop developement as in the positive numbers ?

  • What if we include decimal numbers ? Like 1.85 or like 18.092 ? Thanks.

  • This video is a gem 💎 , although the problem is mind boggling but to express us in this way it's really a gem.

  • What would happen if you reversed it, so you half odd numbers while apply 3x+1 to even numbers? My guess is that the graph will just get inverted.

  • 4 2 1? did Jupiter copy pasted this for it's moons orbital resonance?😁

  • Well, infinity is not a number so you have to specify what infinity means to any given problem. If you say that after 10000 is infinity then the 3x+1,/2 number if of 21 is close to infinity.

    • In this case infinity means that for any number you chose in a Collatz sequence, a higher number will follow.

  • This seems to be a problem for an algorythm, isn't it?

  • think of this, not as the question, but the answer ;)

  • Humans creates numbers to understamd stuff and then doesnt understand it. Some problems might be small but are actually really hard.

  • what about imaginar number?

  • 3x+1 1x3 3

  • 1/2 the time you can divide by 2 to get to the next odd number, 1/4 of the time divide 4 times... What about infinity times? Infinite times to get to an odd number?

  • Is the a way to prove it cannot be decided as Gödel defines ? I imagine, non, as it would be done ? For me, it seems like a halting problem. What is seducing people is what I finally understood of NP problems, the asymmetric behabior: for NP, hard to solve, easy to check. For 3x+1, easy to state, hard to check.

    • Possibly, but it doesn't "feel" unprovable to me.

  • 4x

  • This reminds me of a sloka from Upanishads: पूर्णस्य पूर्णमादाय पूर्णमेवावशिष्यते |

  • Who came here from meme.

  • its 4 right?

  • Solved this in 3 minutes and bought a fake Noble prize for myself.

  • The speed of light may be the serlusion

  • Can you please make a video on 3, 6 and 9? Cheers

  • WTF Did i wake up to?

  • I have a slightly above average IQ but somehow, math always gives me a headache even just looking at complicated questions

  • It always go back to "one".

  • Probably being a idiot, but could a algorithim follow these rules and cross check with numbers on the chart to see what is or isn't there

  • 3X +1 just an equation with any input numbers… which through x3 and +1, then come with an extra rule applied on the output (odd/even).. what’s going on here maybe is the probability generating the output, and how you treat the output with extra rule on group. Question is why the extra rule needs to be /2 ?

  • Can't you just do aleph null square root aleph null?

  • The reason why the problem has three loops when x is negative is because the problem works differently. When x is positive and an odd number, it’s absolute value is multiplied by 3 and then added by one. When x is negative and an odd number though, it’s absolute value is multiplied by 3 and then subtracted by 1. To get the proper results you would be looking for is to do 3x-1 when x is negative and 3x+1 when x is positive.

    • Of course. But the questions remains of why 3x-1 behaves so differently from 3x+1, even though that 1 quickly becomes negligible in comparison to the 3x. A lot of attempts at on-the-fly justifications for 3x+1 always going back to 1 are so imprecise that they almost always apply just as well to 3x-1, except the latter doesn't always go back to 1 making their reasoning invalid.

  • Since its 3x+1, 1 is the starting point of the y axis. If we go the other way, in the negative x, we have a tiny portion that has the x as negative but y as positive. It goes to only -0.33333333..., then both y and x are negative and don't obey the same rules. But -0.33333333... is infinite. we never quite get back to our 1 y axis. So the only way that there would be another loop or wouldn't end in the 4-2-1 loop would be with fractions, decimals, or any number that doesn't in some way have a positive 1 in it. Any number has a +1 in it..... except 0.... and the negatives... so that is my answer... idk if what i had in mind could be properly said through this message.

  • I guess 96 pecent of the viewers including me dont even know what mathematic proof means exactly lol

    • I once graded a computational theory course. 60% of those CS Master's degree students did not seem to know what mathematic proof means.

  • Mathematicians may say it's a problem, but I'm fine with it

  • Ever hear of a twentieth-century Austrian-American logician-mathematician-philosopher named Kurt Gödel?

  • Why is this really necessary

  • Is this a joke? Are real mathematicians really work on this? "Multiply by 3 and add 1 to odd numbers" this eliminates every prime number higher than 3. "Divide even numbers by 2" 2 is the only even prime number and reduces all sums by half including even results. This seems more like a children's math riddle than a serious mathematical equation.

    • @Motor Head Right. It's not hard to see that any sequence heads to one once it hits a power of 2. However, the "fuss" is actually proving that a sequence always hits a power of 2 eventually, and that's not exactly easy, and also you have done no attempt at even trying to justify it.

    • I worded it wrong. The solution is 2 to the nth power. Its in the x3+1 until you reach a number that is equal to 2 to the nth power. All this does is manipulate numbers until you reach a numer that equals 2 to the nth power. 2,4,8,16,32,64,128,256,512,1024, 2048.............n. once there it a mater of division until you reach 1 than it back to 4 and repeat. Simple. Not sure what the fuss is.

    • "This eliminates every prime number higher than 3" what do you mean by eliminate? It really just sounds like you haven't understood the difficulty of the problem yet. It sounds simple but it really isn't. And if it were simple enoguh for someone like you to solve, this video wouldn't exist.

  • The largest peak I found was the number 60342610919632 and the seed number 6631675

  • Is this only for whole numbers? Like what if you plug in 86.5?

    • Evenness and odness only make sense for whole numbers, yes.

  • start a loop of 0 you will never get 1

  • Okay but whats the problem? Theres nothing to work on tbh

  • What if you take 1 as an even number and then divide it by 2 and carry on with the same algorithm

    • Could you elaborate more !

    • @jaydev acharya That's even worse, because evenness and oddness only make sense for integers. If you ever want to apply them to non integer you have to change their definition, and from that point on whatever happens only depends on you.

    • We can always go in to decimal!

    • If you take odd numbers as even numbers you shouldn't be surprized if everything stops making sense.

  • 3x + 1 is literally 3x + 1 because we can’t simplify it unless we know what the variable is

    • ​@NotNormal But you are correct because we can't simplify 3x + 1. Just watch the video on double speed so it can save 2x of time.

    • @Mi Feke no lol also this is a joke comment

    • The whole point of the video is about the variable, did you even watch it?

  • I think it's because at the root of everything (at the end of counting parts) is an indivisible 3 dimensional object that the counter cannot divide. So the numbers 1,2,3 stand for the three dimensions of every countable object. And the 4th number represents the Counter, the person doing the counting. The reason why the numbers go up and then down is because 3x+1 and the instruction of what to do in the case of an even number (1/2 it) have different odds of producing an even number. 3x+1 produces an even number every time. 1/2 step down action occurs on even numbers and 50% of the time produces an even or odd number. So if it goes down because of landing on an even, it will afterwards go up 50% of the time because of landing on an odd and go down one step later, because odd numbers produce even numbers one step later. So the odd values in the numeric scale produce upward steps and then downward steps. And the even numbers produce downward steps with a higher than 50% chance to go down afterwards, looking at a 2 step process. Looking at a 3 step process, essentially, a number that's odd, goes (odd*3+1, and then the next number goes 1/2, inevitably, then it has a 50% chance based on the numeric scale of going up or down again.) and a number that's even goes (even/2, and then the next number is either odd or even, which means it goes 3x+1 (odd) or 1/2 (even) and in the former case (when it's odd), in the case of 3x+1 it inevitably will go down the next turn because it will land on even). So odd numbers are fewer steps predictive to go up (they're 1 step predictive). And even numbers are more predictive to go down than 1.5 steps even . So the pattern goes up and down inevitably by chance but ends up approaching the 1-4 loop because no number can be counted less than a one part three dimensional object by an external entity that considers himself a counter. Ie 1-2-3 dimensions and 4 the counter.

  • Easy answer. All things die.

  • What about 0

  • you cant solve this? subtract 1 from both sides then divide by 3 x = -1/3

  • Hi Derek, I'm probably not the first one to notice this but if there were to be a number that shoots off to infinity, that would mean that some number would indefinitely alternate between odd and even or any odd number in the sequence that shoots off to infinity multiplied by 1.5 + 0.5 is always an odd number. If you'd encounter any occasion where you divide an odd number twice or more, you just exclude it from the series as well as any number before it. So if you could prove that no such sequence is possible, then there is only one way where the collatz conjecture is false. I also think that you don't need to check every number. Only the odd ones, as the even ones, they always go down and will no matter what always eventually get to an odd one. Hope this comment helps anyone that is working on it

  • It has been revealed. All is One

  • Just start with 0

  • Me who knows 3x+1 is just a kinda steep line that passes through (0,1)

  • Meanwhile the rest of us are having sex with each other.

  • Math won't be around for long. Blacks hate it and you know what that means.

  • What is the point of this though? Not even trying to be funny but I don’t even understand what the point of this question is lol. I have pretty limited math experience sorry if that’s a dumb question.

  • notice how at 2 minutes when the graph shows the different paths the numbers take it stops at 27 which is the number that goes above 9000

  • 0.123156 I think I did it right with the math and in 2 steps ended up with 0.

  • Didn’t understand anything but enjoyed watching it. Thanks

  • 1 is the only eligible number.

  • This just proves that some people are dumb timewasters to the infinity.

  • What is the question here actually?

  • I solved it in 3 miliseconds

  • I don't understand yet why it is a problem. Is it because no one can explain why it becomes one?

    • It's because we don't know if it always does become one.

  • Why is the title of the video the simplest math problem noeoen can solve it?

  • Russians: Now, try 2x + 1

    • @Релёкс84 ackchyually lol

    • That one is trivial. You can accurately describe the sequence for any number no matter how large.

  • Just curious, why does this even matter? What purpose does it serve?

  • If no one can solve it, then it's not "simple!"

    • @luke france Did you watch the video? Apparently, many mathematicians have wasted their lives on this problem. I don’t even understand what they’re talking about! Lol

    • How is 3x+1 not simple it’s so small. Only two numbers

  • What this tells me is that we, as humans, probably lack the intelligence to have a conceptual model of mathematics which is sufficient to prove or disprove the conjecture. We could be thinking about numbers completely the wrong way (but the only we can as the sentient beings we are), which could have implications for many other problems about how we model and describe reality which we can't solve. Questions like whether interstellar travel could be possible, time travel, the elusive theory of everything. I think there are answers to these things and I think they can be represented in mathematical models, but not our mathematical models, because of the limits of our own capacity.

  • Numbers of old said the wise man who uses them not. 😶

  • I'm not understanding why we can't just keep checking every number sequence (well beyond 2 to the 68) by running a program on a quantum computer until we find the exception. Am I overestimating quantum computing?? On another note, the discovery of mathematical equations in nature is so fascinating, and opens up beautiful possibilities to designing urban (and other) environments in a way that looks more "natural", thereby creating cognitive ease and reduced mental stress to humans.

    • I dont even see why we would need some novel computers for it, as the task is *COMPLETELY* fit for parallelization. A computer X gets assigned the range 2^69, computer Y the range 2^70, and so on and so on. And sure, some ranges will need more time then others... but who cares? let them.... and run further/other/next in list ranges on the computers that finished tthe prior range. One even could code a simple browser addon that uses private citizens computers to calcultae single numbers(instead of the whopping 2^xx ranges) and report the outcomes back to a central db. The math(the pure calculation of it) is SO simple, that this addon could even stop mid calculation AND outsource it to the next computer that is online(and has the browser with add on running) OR pause it until the next time the initial computer comes back on(has limits and flaws that all can be fixed). For it, the addon would have to transmit 1. The starting number. 2. The calculations up to the current point(whcih has to be recorded anyway, since one obv wants the solution AND its place in the overall tree AND it uses up barely any bandwith). 3. One does NOT need to transmit the calculation up to the current point even. 3.2 Transmit the Starting Number + the current number. 3.3 IF the starting number ends up beeing interesting(somethin else then the usual 4 2 1 loop, THEN you can come back to it to do/record the full calculation).

  • people trying to solve 3x+1 for decades : me trynna play tetris to fit everything inside my fridge :

  • what about -1

  • 3x+1 is quiet usefull for mountain generators i suppose (for games)

  • Once it gets to 4, it's in the loop. So real question is why does it always go to 4. The way to 4 is either 8 (8 divided by 2) or 1 (3x+ 1=4). Whatever.

  • answer : don't look in 2 dimensions

  • Programmers know how to handle recursion 😉

  • I am more amazed that the narrator of this video knew I chose 7…