9 ms·
The 3x+1 Problem [video]
- TexanFeller 5y agoThis seems like a GREAT problem to suck kids into math and computer science. It’s simple enough to explain to an average 12yo, but has enough depth to still be vexing them after they complete their maths PhD. And it’s natural motivation for them wanting to learn basic programming so they can test billions of examples.
- mathnerdconj 5y agoI was at the beginning of my highschool years and being a poker nerd I heard about Andrew Beal, an amateur mathematician and poker player. He offered a prize for a proof of Beal's conjecture, I was learning Pascal and decided to write a program to find a counterexample. Searching different optimization techniques I found a blog where a guy was trying to win the prize for his little girl. After some years, in college (CS) I learned that the guy was Peter Norvig. Great rabbithole.
- jraph 5y agoI recommend Veritasium, his videos are quite good. This one probably has good and useful visualizations but I was doing the cleaning while listening to it so I missed that. Still possible to follow without watching though.
- cgrealy 5y agoAbsolutely. His "gravity is not a force" video led me through a whole range of emotions from "this is ridiculous" to "actually..." to "holy crap, I've been wrong about this my entire life". In terms of sheer brain-breaking... this is my favourite: https://www.youtube.com/watch?v=ovJcsL7vyrk https://www.youtube.com/watch?v=ovJcsL7vyrk But this is the one I think people on HN need to watch most https://www.youtube.com/watch?v=3LopI4YeC4I https://www.youtube.com/watch?v=3LopI4YeC4I
- aphroz 5y agoFeigenbaum constant was definitely hardcoded
- StephenAmar 5y agoThe gravity video was instrumental in me finally understanding years of physics classes. And the YouTube algorithm was actually really useful and made discover this series of video on special relativity: https://youtube.com/playlist?list=PLoaVOjvkzQtyjhV55wZcdicAz5KexgKvm https://youtube.com/playlist?list=PLoaVOjvkzQtyjhV55wZcdicAz...
- elcomet 5y agoForces are just models to predict interactions between particles. It's only a model (a very accurate one though) so nothing is "really" a force. They are not material objects. But for gravity, something even more accurate was found to model it.
- quux 5y agoIn his earlier days I used to dislike Veritasium because I felt he relied too much on the "go out and ask random strangers about science" format too much. But over the last few years he's really upped his game and evolved the format to the point where I'm subscribed to his channel and get excited when I see a new video from him.
- hashmash 5y agoAfter watching this video, how many of us wrote a program to see if we could just randomly find a case which didn't converge? I wrote one, but of course, the program didn't prove the 3x+1 problem wrong.
- malux85 5y agoHahahaha I came here to see if anyone else did this! I didn’t think that a bit of coding was going to outpace hundreds of years of genius mathematicians - but a few minutes coding was a cheap price to pay to satisfy that ceaseless curiosity
- WJW 5y agoI wrote one many years ago as part of going through (I think) the project Euler series. No hope of actually solving it ofc. It's a fascinating problem because it just seems so simple. I wouldn't be surprised if it turns out in the end that it's connected to some other seemingly unrelated (lack of) order in mathematics like prime numbers or whatnot.
- monopoledance 5y agoTwin primes come to mind. Feels very similar in nature. Overall, there might be a connection to complex systems and ontogenesis. Maybe our struggling with this is all down to some original sin in our perception. Some false axiom we all carry. Pathogenic, hereditary logic, which prevents us from seeing beyond the chaos. 3x+1 seems to capture the pleasing ordered imperfection of real living things, not artificial "organic" structures made by humans. Unrelated: https://www.bigbiology.org/season-2#episode39 https://www.bigbiology.org/season-2#episode39
- Twirrim 5y agoLikewise, but more as a way to experiment with a big integer crate for rust.
- lapetitejort 5y agoI wrote one years ago, and whenever I got bored I'd revisit it and tweak certain things. Weird thing is, I felt like I found a reproduceable pattern in how numbers converged. Unfortunately I haven't been able to effectively communicate the pattern and I don't have the mathematical know-how to google for it.
- dominicjj 5y agoI first came across this problem in Gödel, Escher, Bach in the 80s sometime when I first read it. Hofstadter does warn the reader to bring lots of paper when trying 27. Did I listen? Of course not.
- sillypuddy 5y agoPresumably it's impossible to state what the big-o of a checking algorithm is since it's not proven to halt?
- deleted 5y ago[deleted]
- mcphage 5y agoIt’s O(log n) … probably :-)
- AnotherGoodName 5y agoThe video stated that on average the number is multiplied by 3/4 on each step. Solve initial_value * (3/4)^x = 1 for x to get the number of steps. That'll give a logarithm. So yes it's O(logn) on average
- hprotagonist 5y agohttps://www.quantamagazine.org/mathematician-terence-tao-and-the-collatz-conjecture-20191211/ https://www.quantamagazine.org/mathematician-terence-tao-and... Terence Tao has actually gotten a little traction on this in the last few years.
- jstx1 5y agoThat's also mentioned at 12:34 in the video.
- Crazyontap 5y agoThis video severely disrupted my sleep yesterday. Whole night I was thinking and dreaming about this darned thing, even though I knew it was pretty pointless to do so, considering I'm not even a mathematician and have always found maths hard. Still a brilliant video and now I get why people could spend 20+ years of their precious lives trying to solve these things.
- saltmeister 5y agoand why do they do that?
- kilroy123 5y agoI watched this the other day. I was left wondering one big question. Why does this need to be solved? Would that even change anything?
- spoonjim 5y agoThat's not what number theory is about. You might as well ask the same question of any art.
- choult 5y agoWhy does one climb a mountain?
- jraph 5y agoTo get to the other side. (great answer though, thanks, I'll use it later)
- TheRealNGenius 5y agoI thought you just congratulated yourself on a good answer to why climb a mountain. But seriously though, the answer was a question itself, albeit rhetorical. But then you answered it lol...
- drdrey 5y agoBecause it’s there
- utopcell 5y agoYep, that about sums it up nicely!
- yes_man 5y agoKey is early on in the video with the ”mathematics isn’t ripe enough yet”. Since brute forcing the problem seems unlikely, could be that a solution to this problem takes mathematics a step to a new direction. Many useful things like modern cryptography are ultimately based on mathematical research eons ago that were once ridiculed to be useless and unnecessary by some
- soheil 5y agoIt sometimes amazes me how utterly random problems like this end up being their own fields in mathematics. This ended up being a pretty fascinating problem, but coming up with an arbitrary equation like this and then checking to see if it satisfies yet another arbitrary requirement doesn't seem very difficult to do. Am I completely missing something here?
- yupper32 5y ago> doesn't seem very difficult to do. What makes you think this? You just had area experts tell you otherwise. Do you think that mathematicians are lying to you?
- spoonjim 5y agoMathematicians don't really claim that creating Collatz-like conjectures is difficult... they claim that proving Collatz is hard.
- yupper32 5y agoI read "checking to see if it satisfies" as "proving", but I could be wrong.
- soheil 5y agoI think you misunderstood the answer with the problem. Coming with the answer to this problem is clearly difficult. But what makes 3x+1 as a problem so hard to come up with?
- spoonjim 5y agoThe conjectures where the condition is very simple (Collatz, Goldbach, Fermat) but the proof is very elusive are not as common as you think.
- soheil 5y agoI guess even if they're not common, clearly the person who first came up with 3x+1 didn't know it was going to be so hard to solve. So it was a random simple problem to formulate that ended up being very difficult to solve.
- ab7675226 5y agoThe unsolved (i.e., we don't know if they stop or not) potential Busy Beaver machines for N=5 look like versions of the Collatz algorithms.
- romwell 5y agoMy biggest take-away from this was FRACTRAN[1], The Bestest Ever™ programming language designed by the (sadly, late) John Conway. To run a FRACTRAN program, you lookup its catalogue number, and repeatedly evaluate a certain simple function on it (which has the same spirit as the 3x + 1 one in the video). As in 3x+1, all operations are integer operations. FRACTRAN is Turing-complete, of course, so you can rewrite any program in FRACTRAN, and the paper provides quite a few examples! Written as a sales pitch, this is both the most hilarious paper I've read in a long time - and one of the most mind-blowing ones. It's pretty accessible (as far as math/CS papers go), too! [1]http://www.cs.cmu.edu/~15455/resources/Conway87.pdf http://www.cs.cmu.edu/~15455/resources/Conway87.pdf PS: The real mind-blowing part is thinking about whether 3x+1 is, too, a programming language. We simply don't know, and possibly never will.
- teruakohatu 5y ago> 3x+1 is, too, a programming language What does this mean? Isn't having a catalog essentially precomputing a function for every possible input?
- jay_kyburz 5y ago3x+1 produces binary, up or down, so perhaps the integers are shortcuts or an index to any binary sequence. The termination of the sequence is 4,2,1
- romwell 5y ago>What does this mean? A 3x + 1 program is a positive integer N. "Running" this program would be iterating 3x + 1 until it gets stuck in a loop (this would be the "halting condition"). The "output" would be a fixed function of the numbers in the loop (e.g. the loop itself; like 4, 2, 1). As far as we know, all "programs" in 3x + 1 output 4, 2, 1. This makes for a very boring language (essentially, one you can only make "Hello World!" in). But we don't have a proof that that's all there is to it. >Isn't having a catalog essentially precomputing a function for every possible input? Specifically, that means that given a Turing machine T and input X, we can compute a number N = N(T, X) such that the "output" of running our "language" on N is the same as the output of T on X. Which is what they do in FRACTRAN: they show how to encode an arbitrary program and its input as a number N, and how to read the output from the iteration.
- guskel 5y agoOn the wikipedia page for the Collatz conjecture, there is a statement of the Collatz conjecture "in reverse" by growing a graph where R(n) = {2n, (n-1)/3} for n ≡ 4 mod 6, and R(n) = 2n for n ≡ 0,1,2,3,5 mod 6. I wonder how many attempted proofs attempt to solve through this bottom up approach rather than top-down.
- mynegation 5y agoAbout a week ago, I spent several hours after midnight in this ultimate nerd trap. I started with powers of 2 that obviously reduce to the cycle and tried to apply these transitions inferring larger and larger sets of numbers whose binary representation satisfies specific regular expressions on 0 and 1s, but got lost pretty quickly. My intuition is that, given that several generalizations of Collatz Conjecture are undecidable (equivalent to a halting problem), this process is in the territory of being not yet Turing-complete but already undecidable. But I am pretty sure many people way smarter than me tried this approach as well.
- gary17the 5y agoThis was a great video. But the one titled "Math Has a Fatal Flaw"[1] was even more interesting: the meta-mathematics, thus mathematics of entire mathematics (Gödel). [1] https://www.youtube.com/watch?v=HeQX2HjkcNo https://www.youtube.com/watch?v=HeQX2HjkcNo
- feoren 5y agoI can't get over the clickbaity, obviously incorrect title to that one. I refuse to watch it for that reason alone. If the flaw is fatal, then every mathematician is wasting their time.
- pgalvin 5y agoThe video is very interesting, I would highly recommend you still watch it. Derek has has actually made a video before about the YouTube algorithm and has polled the community several times about clickbait-ey titles. He doesn’t like them, but they’re unfortunately necessary.
- deleted 5y ago[deleted]
- wodenokoto 5y agoIt’s about the gödel incompleteness theorem. I think it’s fair to say that’s as big a flaw in math as flaw gets. It says there are things in math that are true but unprovable, and we can’t know if it’s unprovable.
- rcxdude 5y agowell, the theorem basically did show that a huge number of mathematicians were wasting their time on an impossible task.
- ericls 5y agoI'm not particularly into math, but I've lost about five nights of sleep on this...
- gblanchette 5y agoIs there something wrong with that proof? https://www.youtube.com/watch?v=O7SmNyte6nA https://www.youtube.com/watch?v=O7SmNyte6nA (in French) The 3x+1 Conjecture is false Text in English : https://arxiv.org/abs/2104.10681 https://arxiv.org/abs/2104.10681
- mcphage 5y agoIf they want to argue it’s false, it would really help to have a counterexample.
- morei 5y agoI had a quick read. The paper states in the conclusion "The more we increase the number of iterations k, the more proportion decreases, but the number of integers starting the different trajectories keeps increasing and tends towards infinity as k tends towards infinity." This statement is not proven, and is not supported by the previous theorems. Thus the following statement "We therefore conclude that the 3x+ 1 conjecture is false" remains an unproven assertion. Essentially the paper argues that the density F(k) of trajectories at least as long as 'k' gets ever smaller as k increases, without ever reaching zero, and thus there exists at least one value that has an infinity long trajectory. But that's as false assertion. Just because F(k) is non-zero for every finite value of k does NOT imply that the lim as k tends to infinity of F(k) is non-zero, and consequently does not prove the existence of an infinity long trajectory. TL;DR: paper applies intuition on finite sequences to infinite sequences and gets it wrong.
- shannifin 5y agoI've gone through several periods of obsession with this problem. One of its addictive qualities is that, even if you're getting no closer to a solution, it's easy to find a bunch of related patterns within patterns within patterns, a beautiful balance of order and chaos, a wonderful endless fractal of emerging patterns to play with and explore. For instance: arrange all integers with negatives between positives, as such: 1, -1, 2, -2, 3, -3, 4, -4, etc. Now choose any integer, positive or negative, and follow it to the next integer. For example, if you choose 3, go forward 3 spaces on the list, landing on -4. This is negative, so we go back 4 spaces, landing on -2, which leads to -1. Conjecture: All integers eventually lead back to the 1, -1 loop at the beginning. This can be shown to be a variation of the Collatz; that is, if Collatz is true, this must be true and vice versa. I also attempted to prove Collatz by focusing on the odds only, that's where the real action is... Failed of course as it's not quite rigorous enough to disprove potential looping (it does at least prove that it cannot diverge to infinity), but may be of interest to someone else obsessed with the problem: https://youtu.be/P0F4zbNdbTU https://youtu.be/P0F4zbNdbTU
- pronoiac 5y agoReading the Wikipedia page for the Collatz conjecture is interesting; the time-space tradeoff item specifically made me consider the benefit of using a couple of terabytes of disk space for it. (I think 2 to the 40th of space, for a factor of 40 speedup.) https://en.wikipedia.org/wiki/Collatz_conjecture#Optimizations https://en.wikipedia.org/wiki/Collatz_conjecture#Optimizatio...
- pronoiac 5y agoWow, the nerdsniping on this is something. Note, for my math, I failed to consider that entries wouldn't fit in one byte. Figuring out an encoding might help. Laying out a sequence in blocks might also help overcome the speed difference between memory and storage. I'm not even really trying to delve into this, but it's tempting.
- nullc 5y agoI assume the worst consequence of publishing anything on the collatz conjecture is that you will forever receive kookmail from people who think they've solved it.
- shric 5y agoDo also check out the Inigo Quilez video where he explores a generalisation of this to complex numbers: https://youtu.be/GJDz4kQqTV4 https://youtu.be/GJDz4kQqTV4
- deleted 5y ago[deleted]
- haspok 5y agoWhy 3x+1? Why not any other polynom (or at least generalize to ax+b)? Where does it come from?
- GrumpyNl 5y agoThe only pattern i see is at the end, 5,16 or 20,16 or 32,16, looks like 16 is the magic number.