Every Math Problem We Can Solve is a Miracle
November 11, 2022 10:13 PM Subscribe
Oh no, not again.
posted by loquacious at 11:34 PM on November 11, 2022 [9 favorites]
posted by loquacious at 11:34 PM on November 11, 2022 [9 favorites]
For some of us, pretty much every math problem is unsolvable. So, like, 3n+1? I’m totally zen about it. Just another Friday.
But, seriously, neato video!
posted by Don.Kinsayder at 11:42 PM on November 11, 2022 [1 favorite]
But, seriously, neato video!
posted by Don.Kinsayder at 11:42 PM on November 11, 2022 [1 favorite]
I delved into this a couple of months ago. I have a NAS with terabytes to spare, and thought about putting it to use with that. The Wikipedia page on the Collatz conjecture has lots of info to spare, especially the Optimizations section. Note, it's been computed and verified up to 2^68, roughly 3e+20.
posted by Pronoiac at 12:27 AM on November 12, 2022 [2 favorites]
posted by Pronoiac at 12:27 AM on November 12, 2022 [2 favorites]
I have a proof, sadly MetaFilter's comments are too small to contain it.
posted by zengargoyle at 12:33 AM on November 12, 2022 [36 favorites]
posted by zengargoyle at 12:33 AM on November 12, 2022 [36 favorites]
We fell for that trick once, zengargoyle alias Fermat. Don’t try it again.
posted by wittgenstein at 3:29 AM on November 12, 2022 [7 favorites]
posted by wittgenstein at 3:29 AM on November 12, 2022 [7 favorites]
I would not mention your proof to anyone. Someone from The Laundry might take an interest.
posted by JustSayNoDawg at 4:00 AM on November 12, 2022 [9 favorites]
posted by JustSayNoDawg at 4:00 AM on November 12, 2022 [9 favorites]
It seems dumb to not streamline the odd case, since it is always followed by the even case which divides by 2, so just make the odd case 1.5x+0.5 or, without floating point, x+((x+1) rsh 1)
posted by seanmpuckett at 7:16 AM on November 12, 2022 [1 favorite]
posted by seanmpuckett at 7:16 AM on November 12, 2022 [1 favorite]
Vi Hart cracked the code for me years back: I don't love math, I love listening to people talk about math.
posted by TheCoug at 7:52 AM on November 12, 2022 [1 favorite]
posted by TheCoug at 7:52 AM on November 12, 2022 [1 favorite]
Seanmpuckett illustrates the core enticement of the Collatz Conjecture, which is that it looks so easily solvable that it lures you into thinking that maybe the entire field of mathematics has simply overlooked a simple insight. They haven’t.
posted by argybarg at 8:00 AM on November 12, 2022 [7 favorites]
posted by argybarg at 8:00 AM on November 12, 2022 [7 favorites]
mathematicians have come so far... but they still can't add together me + you 😔
posted by bracems at 8:02 AM on November 12, 2022 [4 favorites]
posted by bracems at 8:02 AM on November 12, 2022 [4 favorites]
Hmmph. I am merely looking at it from an algorithmic perspective. I'm no mathematician, I have no insight other than looking at the state machine and thinking, this state transition could be simplified. Nothing more.
posted by seanmpuckett at 8:09 AM on November 12, 2022
posted by seanmpuckett at 8:09 AM on November 12, 2022
This is math’s version of the journey is more important than the destination.
posted by interogative mood at 8:17 AM on November 12, 2022
posted by interogative mood at 8:17 AM on November 12, 2022
Leaving town for a week, will try and knock out the obvious solution everyone else has missed on the flight out
posted by cortex at 8:18 AM on November 12, 2022 [8 favorites]
posted by cortex at 8:18 AM on November 12, 2022 [8 favorites]
Yitang Zhang now says he has solved an analogue of the celebrated Riemann hypothesis :P
"Number theorist Yitang Zhang, who is based at the University of California, Santa Barbara, posted his proposed solution — a 111-page preprint — on the arXiv preprint server on 4 November1."
posted by kliuless at 8:35 AM on November 12, 2022 [1 favorite]
"Number theorist Yitang Zhang, who is based at the University of California, Santa Barbara, posted his proposed solution — a 111-page preprint — on the arXiv preprint server on 4 November1."
posted by kliuless at 8:35 AM on November 12, 2022 [1 favorite]
As long as everything adds up to slightly less than nothing, -1/12 to be precise we’re going to be alright.
posted by interogative mood at 8:50 AM on November 12, 2022 [3 favorites]
posted by interogative mood at 8:50 AM on November 12, 2022 [3 favorites]
But seriously, it's such a lovely little mindfuck of a problem. There is something really really beautiful about being able to pack so much chaos and frustration into such as simple formulation; the comparison to FLT is apt and I'd say 3n+1 wins easily for symbolic concision. I have a similar love for the Recamán Sequence with it's similar up and down, back and forth chaotic behavior form a simple definition and its similar unproven conjecture about the number line.
I was considering doing a week-long bit of updating the thread daily to say "okay, a small set back, but this time I'm pretty sure I got it" over and over, but I am genuinely gonna have a little fun dorking around with the very basics on the plane because I love being a curious toddler underfoot in old hard problems and rediscovering a few little things on my own.
posted by cortex at 9:19 AM on November 12, 2022 [6 favorites]
I was considering doing a week-long bit of updating the thread daily to say "okay, a small set back, but this time I'm pretty sure I got it" over and over, but I am genuinely gonna have a little fun dorking around with the very basics on the plane because I love being a curious toddler underfoot in old hard problems and rediscovering a few little things on my own.
posted by cortex at 9:19 AM on November 12, 2022 [6 favorites]
If your response to this is “apparently I like people talking about math,” I’ll give you the same advice I gave my kids when they hated math in elementary school. That was around the time I first read the excellent Lockhart’s Lament (which may have since been expanded into a book). If you haven’t read the Lockhart piece, treat yourself to just the first page, in which a musician wakes up from a terrible dream.
My kids didn’t hate math. My kids hated arithmetic. But arithmetic is to math what the alphabet is to literature. We tell small children that the alphabet is important, we decorate their classrooms and bedrooms with alphabets, we sing songs about the alphabet. Until about the third grade, when all of the alphabet garbage disappears. That is because the alphabet is mostly stupid and boring. We learn the alphabet so that we can forget completely that it exists, while we use it to read and write about outer space and about falling in love and about processing fear and grief and loss and about dinosaurs and about quantum physics and about rose petals.
The Collatz conjecture is an interesting puzzle hiding in arithmetic. Compare to taking your stupid, boring alphabet, discovering that other languages use different stupid, boring alphabets, and asking whether you can reconstruct the history of human migration using their similarities and differences. (Example: ours is an “abjad” alphabet, from the family which start alpha, beta, gamma, delta. Arabic also uses an abjad alphabet, but Arabic isn’t an Indo-European language.)
It worked, by the way. My kids think algebra and geometry are pretty nifty.
posted by fantabulous timewaster at 9:40 AM on November 12, 2022 [3 favorites]
My kids didn’t hate math. My kids hated arithmetic. But arithmetic is to math what the alphabet is to literature. We tell small children that the alphabet is important, we decorate their classrooms and bedrooms with alphabets, we sing songs about the alphabet. Until about the third grade, when all of the alphabet garbage disappears. That is because the alphabet is mostly stupid and boring. We learn the alphabet so that we can forget completely that it exists, while we use it to read and write about outer space and about falling in love and about processing fear and grief and loss and about dinosaurs and about quantum physics and about rose petals.
The Collatz conjecture is an interesting puzzle hiding in arithmetic. Compare to taking your stupid, boring alphabet, discovering that other languages use different stupid, boring alphabets, and asking whether you can reconstruct the history of human migration using their similarities and differences. (Example: ours is an “abjad” alphabet, from the family which start alpha, beta, gamma, delta. Arabic also uses an abjad alphabet, but Arabic isn’t an Indo-European language.)
It worked, by the way. My kids think algebra and geometry are pretty nifty.
posted by fantabulous timewaster at 9:40 AM on November 12, 2022 [3 favorites]
I don't know if there's already a term for this but let's say that in general an operator bN means "divided by N until you can't stay in the integers anymore" - a sort of inside-out modulus, I guess? - so 6b2 is 3, 45b3 is 5, etc.
With that in mind, I took a run at this a while ago from a prime-factors angle; If you express numbers as ordered sets of prime exponents (like, 144 is [2,4] meaning 3^2 * 2^4 ) - the "divide by two" or b2 process becomes "set the twos exponent in that set to zero"; one neat thing is that for every step in that sequence, those sets are completely disjoint. x and (3x+1) - and consequently (3x+1)b2, obvs - have no intersection, they are trivially shown to have no prime factors. So the question becomes equivalent to "demonstrate that this permutation process always eventually produces duplicate sequences", which ... I think is provable? I haven't managed to chase that attack far enough to make it work, even though some interesting... not antipatterns, but a-pattern structures start to pop out of it.
posted by mhoye at 10:38 AM on November 12, 2022 [2 favorites]
With that in mind, I took a run at this a while ago from a prime-factors angle; If you express numbers as ordered sets of prime exponents (like, 144 is [2,4] meaning 3^2 * 2^4 ) - the "divide by two" or b2 process becomes "set the twos exponent in that set to zero"; one neat thing is that for every step in that sequence, those sets are completely disjoint. x and (3x+1) - and consequently (3x+1)b2, obvs - have no intersection, they are trivially shown to have no prime factors. So the question becomes equivalent to "demonstrate that this permutation process always eventually produces duplicate sequences", which ... I think is provable? I haven't managed to chase that attack far enough to make it work, even though some interesting... not antipatterns, but a-pattern structures start to pop out of it.
posted by mhoye at 10:38 AM on November 12, 2022 [2 favorites]
fantabulous timewaster:
ours is an “abjad” alphabet, from the family which start alpha, beta, gamma, delta
I think you meant to say "abugida". An abjad is something else, "a writing system in which only consonants are represented, leaving vowel sounds to be inferred by the reader." Note that Arabic is an abjad but not an abugida.
posted by crazy_yeti at 11:31 AM on November 12, 2022 [1 favorite]
ours is an “abjad” alphabet, from the family which start alpha, beta, gamma, delta
I think you meant to say "abugida". An abjad is something else, "a writing system in which only consonants are represented, leaving vowel sounds to be inferred by the reader." Note that Arabic is an abjad but not an abugida.
posted by crazy_yeti at 11:31 AM on November 12, 2022 [1 favorite]
fantabulous timewaster, Lockhart has written two books: Measurement starts with simple geometry and works up to calculus and differential equations. It is completely self-contained and there are pictures on almost every page. It is one of the best math books I have ever read.
The other book is Arithmetic, which is mostly a history of number systems and simple calculating devices.
posted by JonJacky at 12:54 PM on November 12, 2022 [3 favorites]
The other book is Arithmetic, which is mostly a history of number systems and simple calculating devices.
posted by JonJacky at 12:54 PM on November 12, 2022 [3 favorites]
My mind drops to thinking about this problem when it probably shouldn't. I know I don't have the language to address any of it in a useful way. But I do have a means of helping myself stop thinking about it: it's kind of a statistical game of infinite snakes and ladders (aka chutes and ladders, I'm told).
So let's say you've investigated all of the odd numbers up to and including N and they've all been reduced to the 4 2 1 4 2 1-forever burble, like those blinkers in Conway's Life. So your next number — 3 (N + 2) + 1 — is going to be even, but if it's divisible by 4, you're out: you'll end up on an odd number less than N, which you've already investigated and discarded. Worst of all is if you land on a power of two: it'll snake you right back to 1 at the start. Thinking in binary, you can right-shift all the least-significant zeroes away of any even number you visit; if your result is less than where you started, that number's a loser (iff you've already discarded all odd numbers up to where you started).
So you're going along thinking you've got a 1 in 2 chance of not immediately being out next throw: some gamblers would take those odds. But you're forgetting: there's already a constellation of flak numbers above you (wait: snakes, ladders and anti-aircraft fire? Bluebottle voice: “I don't like this game!”) that you've already visited, and those numbers will take you out. So at best, you've got a somewhat less than 1 in 2 chance of not being instantly deaded, and you've got to find a number that will keep those odds up forever to disprove the conjecture. Do you feel lucky, punk?
At this point, my brain manages to disengage itself from the fatal siren song of maths problems with no conceivable solution and returns to regular programming, that of imagining Sisyphus happy.
posted by scruss at 1:26 PM on November 12, 2022 [4 favorites]
So let's say you've investigated all of the odd numbers up to and including N and they've all been reduced to the 4 2 1 4 2 1-forever burble, like those blinkers in Conway's Life. So your next number — 3 (N + 2) + 1 — is going to be even, but if it's divisible by 4, you're out: you'll end up on an odd number less than N, which you've already investigated and discarded. Worst of all is if you land on a power of two: it'll snake you right back to 1 at the start. Thinking in binary, you can right-shift all the least-significant zeroes away of any even number you visit; if your result is less than where you started, that number's a loser (iff you've already discarded all odd numbers up to where you started).
So you're going along thinking you've got a 1 in 2 chance of not immediately being out next throw: some gamblers would take those odds. But you're forgetting: there's already a constellation of flak numbers above you (wait: snakes, ladders and anti-aircraft fire? Bluebottle voice: “I don't like this game!”) that you've already visited, and those numbers will take you out. So at best, you've got a somewhat less than 1 in 2 chance of not being instantly deaded, and you've got to find a number that will keep those odds up forever to disprove the conjecture. Do you feel lucky, punk?
At this point, my brain manages to disengage itself from the fatal siren song of maths problems with no conceivable solution and returns to regular programming, that of imagining Sisyphus happy.
posted by scruss at 1:26 PM on November 12, 2022 [4 favorites]
Conway's FRACTRAN (mentioned 18m-19m30s), Busy beavers, etc. would be more fun than 3x+1 if you're primarily a programmer.
In particular, one asks what can Turning machines with few states and symbols do? There is a 3x+1 line at TM(2,8), TM(3,5), TM(4,4), TM(5,3) and TM (10,2), but below this line you might find papers that describe strategies amenable to large scale computations, and likely some discussion of how much of TM(4,2) is already known to be decidable.
posted by jeffburdges at 4:20 PM on November 12, 2022 [1 favorite]
In particular, one asks what can Turning machines with few states and symbols do? There is a 3x+1 line at TM(2,8), TM(3,5), TM(4,4), TM(5,3) and TM (10,2), but below this line you might find papers that describe strategies amenable to large scale computations, and likely some discussion of how much of TM(4,2) is already known to be decidable.
posted by jeffburdges at 4:20 PM on November 12, 2022 [1 favorite]
→
Actually, I thought about this a little more, and all it means is you have to skip every second odd number because it'll always return a number divisible by 4. So while we've halved the size of the candidate set, half of infinity is still infinity. The power of two thing and the flak constellation still apply, though
posted by scruss at 5:53 PM on November 12, 2022
if it's divisible by 4…
Actually, I thought about this a little more, and all it means is you have to skip every second odd number because it'll always return a number divisible by 4. So while we've halved the size of the candidate set, half of infinity is still infinity. The power of two thing and the flak constellation still apply, though
posted by scruss at 5:53 PM on November 12, 2022
I took a grad school math course where the preeminent expert on the Collatz Conjecture was a frequent guest lecturer, being a friend of the professor. Not going to name him because I feel like I just barely squeeked through that class and anyway what he lectured on wasn’t related to the conjecture but instead foundational topics in computational complexity. Anyway, fond memories Jeff and Anne. I did my best.
posted by sjswitzer at 7:12 PM on November 12, 2022
posted by sjswitzer at 7:12 PM on November 12, 2022
They were both concerned with the question of whether there were consistent models of the lambda calculus (inherent cardinality issues) AND they both certainly knew D. Scott. I never asked, but maybe I should have. Or not. I would not have been able to follow their responses anyway.
posted by sjswitzer at 8:08 PM on November 12, 2022
posted by sjswitzer at 8:08 PM on November 12, 2022
Number theorist Yitang Zhang
And that's ... numberzhang!
posted by chavenet at 6:53 AM on November 13, 2022 [5 favorites]
And that's ... numberzhang!
posted by chavenet at 6:53 AM on November 13, 2022 [5 favorites]
xkcd made a very nice Tshirt of this, but I can’t find it currently for sale.
posted by clew at 4:01 PM on November 13, 2022
posted by clew at 4:01 PM on November 13, 2022
Can we solve 3n+1 for just prime numbers?
Asking for a friend.
posted by Ignorantsavage at 4:14 PM on November 13, 2022
Asking for a friend.
posted by Ignorantsavage at 4:14 PM on November 13, 2022
> sjswitzer: "I took a grad school math course where the preeminent expert on the Collatz Conjecture was a frequent guest lecturer"
If you're talking about who I'm thinking of, he's also the one who assembled perhaps the definitive bibliographies of his problem: the original covering developments up to 1999 and the follow-up covering 2000-2009. Anyone who's at all serious about tackling the Collatz Conjecture must eventually pass through these bibliographies. I don't know if he's still interested in extending his bibliographic coverage of this problem, but I hope he does if only to include Terence Tao's blockbuster 2019 result, which doesn't solve the Collatz Conjecture completely but provides (I think) the strongest partial result known to date.
posted by mhum at 12:36 PM on November 14, 2022 [2 favorites]
If you're talking about who I'm thinking of, he's also the one who assembled perhaps the definitive bibliographies of his problem: the original covering developments up to 1999 and the follow-up covering 2000-2009. Anyone who's at all serious about tackling the Collatz Conjecture must eventually pass through these bibliographies. I don't know if he's still interested in extending his bibliographic coverage of this problem, but I hope he does if only to include Terence Tao's blockbuster 2019 result, which doesn't solve the Collatz Conjecture completely but provides (I think) the strongest partial result known to date.
posted by mhum at 12:36 PM on November 14, 2022 [2 favorites]
« Older Bubbles | Origins and Originations Newer »
This thread has been archived and is closed to new comments
As a non-mathematician, here is my "why don't they just" that leaves all the hard work for someone who wants to ruin their career by spending decades studying 3n+1:
So, about that coral-looking structure. How do coral (and/or whatever else looks like that) reproduce? I mean, if they've reproduced something that looks like coral, why not figure out how to get the math to look like the way(s) a coral like it reproduces and see what that says about the problem they're trying to solve?
posted by aniola at 11:09 PM on November 11, 2022