12 ms·
Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33
- amalcon 8y ago> With 33 out of the way, the only one left is 42. I know this is just a coincidence, but it's a rather poetic one.
- deleted 8y ago[deleted]
- nilskidoo 8y agoThe Masons will have a field day.
- giorgioz 8y agoI can't believe no-one has mentioned out loud the reference to The Hitchhiker's Guide to the Galaxy: "The Answer to the Ultimate Question of Life, the Universe, and Everything is 42" https://en.wikipedia.org/wiki/Phrases_from_The_Hitchhiker%27s_Guide_to_the_Galaxy#Answer_to_the_Ultimate_Question_of_Life,_the_Universe,_and_Everything_(42) https://en.wikipedia.org/wiki/Phrases_from_The_Hitchhiker%27...
- dewiz 8y agoThe solution for 42 is coming soon
- jamescostian 8y agoDo you have a source for that? It took 7.5 million years for Deep Thought to discover the significance of 42, and it didn't even break it up into a sum of three cubes :) https://hitchhikers.fandom.com/wiki/Deep_Thought https://hitchhikers.fandom.com/wiki/Deep_Thought
- deleted 8y ago[deleted]
- heinrichf 8y agoNumberphile video on the topic with Andrew Booker: https://www.youtube.com/watch?v=ASoz_NuIvP0 https://www.youtube.com/watch?v=ASoz_NuIvP0 which is a followup from the 2015 episode https://www.youtube.com/watch?v=wymmCdLdPvM https://www.youtube.com/watch?v=wymmCdLdPvM when the 33 problem was unsolved. The announcement elicited this Mathoverflow discussion about "mic drop" moments in mathematics: https://mathoverflow.net/questions/325105/what-are-some-noteworthy-mic-drop-moments-in-math https://mathoverflow.net/questions/325105/what-are-some-note...
- jhncls 8y agoSome additional links: Sander Huisman's 2016 paper about solving the three cubes problem for 74, using a supercomputer in Lyon [0]. The approach for 33 is quite similar, just augmenting the range searched (and some additional tricks to further reduce the search space). Andrew Booker's paper about 33 [1]. It's quite funny how Numberphile inspired these searches. [0] https://arxiv.org/abs/1604.07746 https://arxiv.org/abs/1604.07746 [1] https://people.maths.bris.ac.uk/~maarb/papers/cubesv1.pdf https://people.maths.bris.ac.uk/~maarb/papers/cubesv1.pdf
- vcavallo 8y agoI would have liked to see a bit more comment on the algorithm itself in the article. But I suppose I can find that elsewhere
- AdmiralAsshat 8y ago>Booker found this odd trio of 16-digit integers by devising a new search algorithm to sift them out of quadrillions of possibilities. The algorithm ran on a university supercomputer for three weeks straight. So...did he just brute force it? EDIT: Should've read further down. Looks like, yes: >But usually, solutions are “nontrivial.” In these cases, the trio of cubed integers — like (114,844,365)³ + (110,902,301)³ + (–142,254,840)³, which equals 26 — looks more like a lottery ticket than anything with predictable structure. For now, the only way for number theorists to discover such solutions is to play the mathematical “lottery” over and over, using the brute force of computer-assisted search to try different combinations of cubed integers, and hope for a “win.”
- MrMember 8y agoYes, but smartly. People have been brute forcing solutions to this problem using computers for decades now. The tricky part is reducing the search space.
- lmkg 8y agoI feel like we need a better name for this type of approach, because many people (myself included) take "brute force" to mean naively checking every solution candidate. If you're doing something clever like reducing the search space and/or lowering the big-O, that doesn't seem "brute." Even if you're throwing dozens of core-years at the problem, that seems like "force" but not "brute." I can't think of anything snappy, though. "Clever brute force" is the best I've got, and it's a mouthful. I tried looking for antonyms for "brute," the options aren't great. Well-bred? Polished? Humanitarian?
- empath75 8y agoAnybody have an idea of how much it would cost to have done this search on AWS?
- amelius 8y agoHow many solutions are there?
- MrMember 8y agoThe conjecture (that hasn't been proven) is that every integer that does not equal 4 or 5 mod 9 has infinitely many solutions (integers that = 4 or 5 mod 9 are proven to have no solutions). Parametric equations for 1 and 2 have been found that generate infinitely many solutions for those values but it is otherwise an open question.
- kevinventullo 8y agoDoes anyone know if there is a conjectural characterization of those numbers which can be expressed as the sum of three cubes? The article mentions not being congruent to 4 or 5 mod 9 is a necessary condition. Is it (conjecturally) sufficient?
- deleted 8y ago[deleted]
- jhncls 8y agoIn the Numberphile video it is conjectured that there are infinitely many solutions for all those numbers, but that solutions are very sparse. The smallest solution for 42 might involve very high numbers.
- kevinventullo 8y agoThanks! It seems they mentioned this in the article as well: "A major result would be to prove the conjecture that k = x³ + y³ + z³ has infinitely many solutions for every whole number k, except those k that have a remainder of 4 or 5 after being divided by 9."
- mikepurvis 8y agoCan someone ELI5 what the issue is with numbers that have a remainder of 4 or 5 after being divided by 9? I'm assuming it's something simple that I'm just not seeing, and having trouble googling for it.
- kens 8y agoThe issue is that each term n^3 equals +1, 0 or -1 mod 9. (Test the numbers 0-9). When you add three of these values, you can't get 4 or 5 (mod 9). Thus, you can't get a result that equals 4 or 5 mod 9.
- OscarCunningham 8y agoThe only possible values of a cube mod 9 are 0, 1 and 8. (If you expand (9n+r)^3 you'll see that all the terms divide by 9 except r^3. So the value of a cube mod 9 depends only on its own mod 9 value. So we only need to check that 0, 1 and 8 are the only values achieved by the first 9 cubes.) If you add three of these values the only possible answers are 0, 1, 2, 3, 6, 7 and 8 mod 9.
- yitchelle 8y agoDoes anyone know of a useful application for this fact? Serious question.
- low_key 8y agoApparently not. It more or less says so in the article.
- Invictus0 8y agoPerhaps the algorithm used to discover the solution may be of application. As is often the case in pure math, the methods used to find solutions to otherwise inconsequential problems later find use years down the line.
- mjcohen 8y agoThe mathematician Edmund Landau said (translation from German): Number theory is useful, since one can graduate with it. (from his Foreword to Vorlesungen über Zahlentheorie (Lectures on Number Theory) (1927).) This from https://en.wikiquote.org/wiki/Edmund_Landau https://en.wikiquote.org/wiki/Edmund_Landau
- kingaillas 8y agoNot right now... but maybe in the future, who knows. There was a time number theory was viewed as pointless: "The theory of Numbers has always been regarded as one of the most obviously useless branches of Pure Mathematics." - G.H.Hardy. He might be very disappointed that number theory underpins modern cryptography.
- AlexCoventry 8y agoIf the solutions are that hard to find, you could probably make a commit/ reveal scheme out of it.
- nodesocket 8y ago> other times, a solution is known not to exist, as with all whole numbers that leave behind a remainder of 4 or 5 when divided by 9 Curious how we are able to prove that and with certainty say this is a rule?
- mjcohen 8y agoOff the top of my head: the cubes of 0,1,2,3,4,5,6,7,8 mod 9 are 0,1,-1,0,1,-1,1,-1. The sums of three of these, mod 9, are 0, 1, 2, 3, -1, -2, -3 or 0, 1, 2, 3, 6, 7, 8, so the sum of 3 cubes can not be 4 or 5 mod 9.
- latchkey 8y ago(8866128975287528)^3 + (-8778405442862239)^3 + (-2736111468807040)^3 If I command-space on OSX and put this into the search bar (which accepts math), I get exactly 30,000,000,000,000.
- saalweachter 8y agoecho '(8866128975287528)^3 + (-8778405442862239)^3 + (-2736111468807040)^3' | bc
- waynecochran 8y agoInteresting that the second number is prime and the others have very large prime factors (only 5 and 4 distinct prime numbers for 1st and 3rd numbers respectively): (8,866,128,975,287,528)³ + (–8,778,405,442,862,239)³ + (–2,736,111,468,807,040)³ = 33 696950821015779435648178972565490929714876221952 - 676467453392982277424361019810585360331722557919 - 20483367622797158223817952754905569383153664000 = 33
- skunkworker 8y agoSo simple to check, yet so hard to find. I love these kind of mathematical problems. In irb or python interpreter copy and paste 8866128975287528**3+(-8778405442862239)**3+(-2736111468807040)**3 Though another question, are there an infinite number of possible solutions to this problem? Or just 1 solution with numbers in this length?
- archgoon 8y ago> are there an infinite number of possible solutions to this problem? Unknown. From the article: 'A major result would be to prove the conjecture that k = x³ + y³ + z³ has infinitely many solutions for every whole number k, except those k that have a remainder of 4 or 5 after being divided by 9.'
- ldd 8y agoIt works in your browser with javascript if it supports bigInt[0] 8866128975287528n**3n+(-8778405442862239n)**3n+(-2736111468807040n)**3n [0]:https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- WMCRUN 8y agoThe last unsolved integer under 100 is 42...
- lurcio 8y agoSpooky.
- stebann 8y agoHaha Nice!
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- AlexCoventry 8y agoPerhaps its cubic summands will have a more transparent encoding.
- sohkamyung 8y agoIndeed. I suspect somewhere out there, Douglas Adams must be smiling. :-) [1] Interesting that Lewis Carroll also makes references to 42. [1] https://en.wikipedia.org/wiki/42_(number)#The_Hitchhiker's_Guide_to_the_Galaxy https://en.wikipedia.org/wiki/42_(number)#The_Hitchhiker's_G...
- thaumasiotes 8y ago> That problem, stated as k = x³ + y³ + z³, is what number theorists call a Diophantine equation — a kind of algebraic structure whose properties have fascinated mathematicians for millennia. “They’re rich enough to encode [other mathematical] statements that have nothing to do with Diophantine equations,” said Browning. “They’re rich enough to simulate computers.” You would certainly hope so, since every value a computer works with is integral.
- FartyMcFarter 8y agoIt says they can simulate computers, not that computers can calculate them.
- thaumasiotes 8y agoYes, and I'm saying since they can represent every value a computer can represent, this doesn't come as a surprise.
- svat 8y agoA computer does more than store values: it also performs computation. And “they’re rich enough to simulate computers” refers to the celebrated (and surely surprising!) theorem of Julia Robinson, Martin Davis, Hilary Putnam, and Yuri Matiyasevich, showing that (to state the result in a couple of ways): * given a computer program that prints integers, there is a Diophantine equation whose integer solutions are precisely the set of integers printed by that program, * given any computer program, one can represent it by a Diophantine problem: one can write down a polynomial equation such that it has integer solutions if and only if the program halts. For example, because we can write down a computer program to print the prime numbers, there exists a certain (explicitly known) polynomial whose integer values are precisely the prime numbers. And as we can write down a program which halts only if (say) the Riemann hypothesis is true, we can write down a Diophantine equation which has integer solutions only if the Riemann hypothesis is true. (What you're saying about being able to represent every value a computer can represent would be true for say linear or quadratic equations too, but those are not rich enough to simulate all of computation.) Essentially, you can build a computer out of diophantine equations. You can read more at https://en.wikipedia.org/w/index.php?title=Hilbert%27s_tenth_problem&oldid=886276765 https://en.wikipedia.org/w/index.php?title=Hilbert%27s_tenth... and good expositions by Poonen at http://www-math.mit.edu/~poonen/papers/sample_beamer.pdf http://www-math.mit.edu/~poonen/papers/sample_beamer.pdf (talk slides) or http://www.ams.org/notices/200803/tx080300344p.pdf http://www.ams.org/notices/200803/tx080300344p.pdf (article).
- joemag 8y agoI had to pause for a second to think about what’s so hard about this? And then it hit me - negative numbers.