[HN Gopher] The 3x+1 Problem [video]
___________________________________________________________________
The 3x+1 Problem [video]
Author : tosh
Score : 105 points
Date : 2021-08-09 11:45 UTC (11 hours ago)
(HTM) web link (www.youtube.com)
(TXT) w3m dump (www.youtube.com)
| gblanchette wrote:
| Is there something wrong with that proof?
| https://www.youtube.com/watch?v=O7SmNyte6nA (in French)
|
| The 3x+1 Conjecture is false Text in English :
| https://arxiv.org/abs/2104.10681
| romwell wrote:
| My biggest take-away from this was FRACTRAN[1], The Bestest
| Ever(tm) 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
|
| 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 wrote:
| > 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 wrote:
| 3x+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
| kilroy123 wrote:
| I 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 wrote:
| That's not what number theory is about. You might as well ask
| the same question of any art.
| choult wrote:
| Why does one climb a mountain?
| jraph wrote:
| To get to the other side.
|
| (great answer though, thanks, I'll use it later)
| TheRealNGenius wrote:
| I 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 wrote:
| Because it's there
| yes_man wrote:
| Key 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
| squidlogic wrote:
| It's so someone can use it as a coding challenge in a technical
| interview, of course.
| tuatoru wrote:
| From reading other comments here, we need it because it
| inspires some people to become (better) programmers. :-)
| drexlspivey wrote:
| You would suck as a mathematician (probably good at engineering
| though)
| ericls wrote:
| I think the answer is we _want_ to solve it.
|
| Now the important question is why human beings want to solve
| this, and what exactly do human beings want.
| ajross wrote:
| > Why does this _need_ to be solved?
|
| Obviously it "doesn't". Equally obviously this is mathematics,
| and it's worth doing if it's interesting.
|
| But a somewhat more serious answer is this: the fact that we
| don't know the answer to this relatively simple question
| implies strongly that _we don 't know how numbers work_. And if
| there are obvious gaps in our understanding of number theory
| that show themselves in trivial ways like this, there are
| probably more serious questions that we _could_ answer if we
| had a better framework.
|
| And that's sort of how hard problems in mathematics work. They
| aren't solved by amazing insight within their own realm, they
| turn out to be evidence that a new branch of theory needs to be
| developed first.
| GistNoesis wrote:
| 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 ?
| jraph wrote:
| I 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 wrote:
| 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
| sillypuddy wrote:
| Presumably it's impossible to state what the big-o of a checking
| algorithm is since it's not proven to halt?
| AnotherGoodName wrote:
| The 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
| [deleted]
| mcphage wrote:
| It's O(log n) ... probably :-)
| hprotagonist wrote:
| https://www.quantamagazine.org/mathematician-terence-tao-and...
|
| Terence Tao has actually gotten a little traction on this in the
| last few years.
| jstx1 wrote:
| That's also mentioned at 12:34 in the video.
| hashmash wrote:
| After 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.
| lapetitejort wrote:
| I 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.
| mcphage wrote:
| There's a problem that's simple to state: find positive
| integers A, B, and C such that:
|
| A/(B+C) + B/(A+C) + C/(A+B) = 4
|
| It seems simple, like you could try a few examples and figure
| it out. And there is a solution. But for the smallest solution,
| A, B, and C each have 80 digits. Way too big to brute force.
| [deleted]
| Jyaif wrote:
| the video addresses this: you are _very_ unlikely of finding a
| case that does not converge by chance.
| [deleted]
| malux85 wrote:
| Hahahaha 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
| threatofrain wrote:
| People have been brute forcing the Collatz problem for awhile
| (up to values around 2.95x10^20); just like computing Pi to set
| glory records, you have to be prepared to rent Amazon hardware.
| I think there was a proof that demonstrated that if the Collatz
| conjecture were false, then the cycle has to be immensely
| large.
| imperialdrive wrote:
| 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 ",") | Measure-Object).count
| Set-Content -Path "${count}_${hits}Hits_${range}MaxRange.txt"
| -Value "$array" -NoNewline -Force } while ($count
| -lt 1000)
|
| Does anyone know how to make this work with big numbers? At a
| certain point the value gets returned with something like
| 2.05891132094649E+44 at which point I can no longer simply add
| 1 to it.
|
| Edit: Found it... $count = [bigint][math]::pow(10,44) Awesome!
| I love code!
| mgarciaisaia wrote:
| I found in Wikipedia that Somebody Else(tm) 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.
| WJW wrote:
| I 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.
| Twirrim wrote:
| Likewise, but more as a way to experiment with a big integer
| crate for rust.
| Crazyontap wrote:
| This 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 wrote:
| and why do they do that?
| guskel wrote:
| On 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 wrote:
| About 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.
| soheil wrote:
| It 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?
| demosito666 wrote:
| I don't get why this is being downvoted. For me math is pretty
| much a mystery, in a sense that it seems so arbitrary once you
| move from simple concepts that were initially grounded in a
| real world (like counting pebbles or splitting a circle). And
| it's not because I'm particularly badly educated, after all I
| believe we all can agree that Eugene Wigner [1] knew a bit of
| math and he still was wondering the same thing [2].
|
| So soheil's question doesn't seem ignorant of meaningless to
| me. One could probably reframe it to become something similar
| to philosophy of Godel's theorems, in lines of "there may (or
| may not) exist an infinite number of problems in number
| theories that are very simply formulated but are
| impossible/hard to prove or disprove". Consequence of that
| being that our abilities to have a definitive proof of
| statements are negligible and we're thus fundamentally trapped
| in an infinitely small space of outer mathematical universe.
|
| I'm sorry if I'm saying something stupid here (or on the
| contrary, some well-known fact), like I said, I know nothing
| about mathematics so the two are equally possible to me.
|
| [1] https://en.wikipedia.org/wiki/Eugene_Wigner [2]
| https://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness...
| yupper32 wrote:
| > 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 wrote:
| Mathematicians don't really claim that creating Collatz-like
| conjectures is difficult... they claim that proving Collatz
| is hard.
| yupper32 wrote:
| I read "checking to see if it satisfies" as "proving", but
| I could be wrong.
| soheil wrote:
| I 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 wrote:
| The conjectures where the condition is very simple (Collatz,
| Goldbach, Fermat) but the proof is very elusive are not as
| common as you think.
| soheil wrote:
| 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.
| TexanFeller wrote:
| This 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 wrote:
| I 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.
| dominicjj wrote:
| I first came across this problem in Godel, 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.
| shannifin wrote:
| I'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
| ab7675226 wrote:
| The 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.
| pronoiac wrote:
| 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...
| gary17the wrote:
| This 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 (Godel).
|
| [1] https://www.youtube.com/watch?v=HeQX2HjkcNo
| ericls wrote:
| I'm not particularly into math, but I've lost about five nights
| of sleep on this...
___________________________________________________________________
(page generated 2021-08-09 23:00 UTC)