Reading 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#Optimizatio...
The 3x+1 Problem [video]
51–60 of 102 posts
Re: The 3x+1 Problem [video]
#52After 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.
the video addresses this: you are very unlikely of finding a case that does not converge by chance.
[deleted]
Re: The 3x+1 Problem [video]
#53It 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?
The conjectures where the condition is very simple (Collatz, Goldbach, Fermat) but the proof is very elusive are not as common as you think.
I 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.
Re: The 3x+1 Problem [video]
#54After 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.
I know so little about programming but this video absolutely left me up late trying to follow along: $count = 1 do { $count++ $i = $count [string]$array = "$i" $range = $i - 1 do { if ($i % 2 -eq 0) {$i = $i / 2} else {$i = (3 \* $i) + 1} $array = "$array" + ",$i" if ($i - $count -gt $range) {$range = $i - $count} if ($i -eq 2) {$i = "Break"} } while ($i -ne "Break") $array = "$array" + ",1" $hits = (($array -split "…
I found in Wikipedia that Somebody Else™ checked that there are no counterexamples up until 2^68.
So my attempt to find a counterexample is to start at (2^68)+1, and perform the 3x+1 or halving until I get to a number that's lower than the one I'm testing - then I know it's not a counterexample.
Since even numbers start by halving (ie, getting lower), I only test odd numbers.
295147905503560000001 and counting. No counter-examples found yet.
Re: The 3x+1 Problem [video]
#55I watched this the other day. I was left wondering one big question. Why does this need to be solved? Would that even change anything?
You would suck as a mathematician (probably good at engineering though)
Re: The 3x+1 Problem [video]
#56Re: The 3x+1 Problem [video]
#57I watched this the other day. I was left wondering one big question. Why does this need to be solved? Would that even change anything?
This is a simple bottle universe.
What hope do we have to make sense of our own universe if we can't solve this simple case.
In the video, Derek shows that you can see the problem as a turing machine. But if you view it as operation on strings in basis 6, you observe that the carry doesn't propagate which means that you can compute using a 1d cellular automaton (with local rules).
https://demonstrations.wolfram.com/CollatzProblemAsACellular...
This way of viewing the Collatz conjecture as a cellular automaton mean that the Collatz conjecture is like a simpler version of Conway's game of life. You can then use some memoization tricks like hashlife to compute it more efficiently.
In the game of life, some interesting patterns emerge, whereas in Collatz it is conjectured that they all end in the same pattern of desolation.
Are the Collatz cells doomed ? Is the Collatz automaton turing-complete ? Can life emerge in the Collatz universe ? Would this change anything for these small little cells ?
Re: The 3x+1 Problem [video]
#58I 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.
Absolutely. 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
But this is the one I think people on HN need to watch most https://www.youtube.com/watch?v=3LopI4YeC4I
Re: The 3x+1 Problem [video]
#59My 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…
If 3x+1 is a programming language, the Collatz conjecture must be false as otherwise it would always halt.
I suspect 3x+1 is not Turing complete.
Re: The 3x+1 Problem [video]
#60I 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.