For context, 42 was the only remaining number below 100 where it wasn’t known if this was possible. The general problem of exactly which numbers are the sum of three cubes is unsolved.
Isn't the set of all triples of integers be enumerable, because (inductively) the set of all pairs of integers is enumerable (thanks, Cantor)?
Then, if one could enumerate all triples of integers, one could, for each triple, calculate the sum of the cubes.
So, integers which are sums of cubes are enumerable. That doesn't mean they're a known recursive set, just recursively enumerable.
Am I missing something? Perhaps the statement "The general problem of exactly which numbers are the sum of three cubes is unsolved." is meant to imply "not known to be a recursive set", i.e., no known algorithm for finite time answering the question of whether a given integer is in the set?
Many questions about the integers are recursively enumerable (like: what are the counterexamples to Fermat's last theorem?), but this doesn't really reveal anything about any deeper structure. Part of the conjecture is, indeed, that the set of numbers that are a sum of three cubes is recursive, which is given by a simple condition on the residue modulo 9 (see a sibling comment). However, mathematicians don't usually think about recursiveness of sets when they think about whether a problem has been "solved." It's more about whether some structure has been satisfyingly illuminated (maybe, to make something completely up, triples of numbers whose cubes sum to a particular number are found to be in one-to-one correspondence with "tripolar Hopfian unital schemes," and if something is known about them this might be satisfying). Of course, knowing whether or not a set has a recursive description is nice, too.
Here's something I've wondered about. In knot theory, a "knot" is a closed loop of string in 3d space, and if you allow the string to pass through itself it can obviously be unknotted (put into a form where it is a closed loop flat on a table). An unknotting is a sequence of pass-throughs to unknot it, and the unknotting number is the minimal number of pass-throughs among all unknottings. Unknotting sequences are actually recursively enumerable, but it's unknown whether there is a finite-time algorithm to compute unknotting number!
You can enumerate a,b pairs and then you need to check whether the "locked in" value of c^3 is a cube.
However imagine it takes 1ns to validate a given pair [a,b].
The eventual solution was [-80538738812075974, 80435758145817515, 12602123297335631].
Since no combination of 3 positive (and therefore small) numbers has worked, we know that one of a,b,c are negative. Let's assume at least one of a,b are negative since it doesn't matter how we allocate them.
To reach the final pair of a = 80435758145817515 (the smaller positive integer) and b = -80538738812075974, you have to increment "a" (starting from 0) 80435758145817515 times and decrement "b" (starting from 0) 80538738812075974 times.
That is 80538738812075974*80435758145817515 possible combinations.
Let's assume each one takes 1 ns (which I believe is fairly optimistic at least for a single machine)
That results in a runtime of 6.5e+24 seconds, aka 2.1e+17 years. No matter how many machines you add, the brute force approach does not appear to be feasible.
I am interested to learn more about how they solved it if not brute force.
> I am interested to learn more about how they solved it if not brute force.
"Professors Booker and Sutherland's solution for 42 would be found by using Charity Engine; a 'worldwide computer' that harnesses idle, unused computing power from over 500,000 home PCs to create a crowd-sourced, super-green platform made entirely from otherwise wasted capacity."
>SUSTAINABLE, ULTRA-LOW CARBON - using PCs that already exist but are just underused
Wow, do they honestly believe their own marketing nonsense? There's no way the PUE and power efficiency of a bunch of old random desktop computers is going to come close to beating a modern Amazon, Google, or Microsoft datacenter. Cost wise, yeah sure, I'd bet it would be cheaper even with the lower efficiency and increased power usage but as far as "super-green" and low emissions this is just absurd. I think they might honestly not know that idle power usage is a small fraction of full load usage for any modern processor.
We don't need the datacenters at all. That's the difference.
No facilities. No hardware. No bricks, mortar, shipping, mining of metals or rare earths. No replacing of millions of obsolete machines every three years. We tread lighter than any datacenter owner can ever dream of
Google and Duckduckgo use floating point rather than arbitrary precision integers. Wolfram Alpha's solver is significantly more advanced (including arbitrary precision for integers and floating point numbers)
Python's default number implementation has full support for arbitrarily large numbers, and will allocate more memory as needed to do so, making the original claim correct.
Maybe I'm looking at this the wrong way, but I'd handle enumerating this just like enumerating a set of three numbers. For an integer i just do (1-2(i%2)) * (i/2) using integer division. If it's recursively enumerable with natural numbers then it has to be trivially extendable to all integers just by that method alone.
It is not computationally tractable to enumerate all triples of integers up to the size required to find the values for 42.
So certainly any integer N either is or is not the sum of three cubes. Deciding which is the case computationally can be intractable.
Each of the integers in the solution are ~53 bits in length. To enumerate all triples of integers (with plus and minus) requires testing around 2^(53+53+53+1+1+1) = 2^162 items. If you could test one per nanosecond, this is 10^32 years, vastly older than the universe. If you threw 1 trillion such computers at it, it's still 10^23 years, also vastly longer than the age of the universe.
Thus enumeration is simply not possible.
The point of this is they found a solution for 42 after great effort.
2^109 nanoseconds is still 150,000 times older than the universe. If you do manage to get a trillion computers, you can now solve the problem in twenty thousand years. It's still intractable.
You’re assuming a fixed target. I was enumerating which targets get hit to solve the problem for all cubes up to some fixed size.
If you’re assuming a fixed target, you don’t know how large you need to check to find an answer. That 53 bit numbers sufficed for 42 was not known in advance, and is not the bound for other targets.
I'm not an expert in this problem (nor do I ponder number theory that often), but here are my thoughts: Countable doesn't mean finite. It's possible that there is a sum of three cubes with "big" magnitudes that sum to a "small" integer (just see this solution for 42).
The tweet chain gives a type of integer that we've proven cannot be expressed as a sum of three cubes (9k+4 and 9k+5), but that only means we've proven anything for 2/9ths of the integers, and it's only conjectured that the rest can be expressed as such.
There are some trivial other things can we can prove, such as any number that is 3x a cube, or 2x a cube plus/minus another cube. But that doesn't get us to full coverage.
As of yet we haven't proven a result for enough patterns such that every integer belongs to one of those patterns. I suppose to answer your question is that no, we don't have enough small numbers proven and/or we don't have a recursion pattern that covers the integers with the known numbers we have yet.
That's just my layman's understanding though. As it stands now, we do know that there are infinite numbers that cannot be expressed as a sum of three cubes, but we do have a useful finite set of integers that can. So a full solution to the problem will be good to know, but we already know that an answer is "some can, some can't."
Edit: I realize that someone is going to take issue with my changing GP saying enumerable to me saying countable. There's a difference, and I guess it could matter, but I'm too honest to change my original wording. Sorry in advance for getting it wrong.
All integer sets of any length would be enumerable, but that doesn't necessarily mean that one of them can be cubed and added/subtracted to make a given integer.
Every cube is within one of a multiple of nine, which means every sum of three cubes is within three of a multiple of nine. So numbers of the form 9k+4 or 9k+5 cannot be expressed as the sum of three cubes.
It’s conjectured that every other whole number can be.
Yes, you can use Cantor's diagonal argument to enumerate all triples. No, it does not answer the question whether every integer can be written as the sum of three cubes; it only would if the set of integers was finite.
I had exactly this in mind (or the proof that the set of rational numbers are countable), but mistakenly thought it was called the 'diagonal argument' because you would get the bijection to the natural numbers by counting diagonally through the table.
Serious question, what is one of the immediate practical applications if this problem (sums of three cubes) is solved? Not a math person so question might sound stupid.
There aren't any, and the solution itself is uninteresting, but it's possible that techniques developed in the process of solving it will find application in solving other problems (In physics, chemistry, genetics, cryptography...)
Consider the most important function of calculus - the integral. In layman's terms, it measures the area under a graph. Okay - that's a little bit useful, if you care about the physics of moving objects (A bus is accelerating at 2 m/s^2 for 5 seconds, how far does it travel..?)
Yet, if you know how to integrate, a mountain of not-immediately obvious physics problems - say, anything that has to do with electromagnetism (Maxwell's equations) immediately become tractable.
Pretty much all of mathematics was founded on "fun things to do with numbers", and then later we came up with using prime numbers for cryptography and finding Fibonacci sequences in nature, etc.
I'm not sure I understand your question, but we've posted countless times about this and are happy to answer about specific cases. You can find a lot of information via https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... and similar searches.
That shows up as soon as the submission is created, and there's an 'edit' link if you need to change it. Just don't change it in ways that break the site guidelines: https://news.ycombinator.com/newsguidelines.html.
If it displays during the title entry process it is educating the users about the transformations that occur too. It's a positive-reinforcement loop that supplements the guidelines. It's the reason you don't have to document in the guidelines that the maximum title length is 80 characters.
The title processing logic is surprisingly complex, just as the whole issue of titles on HN is surprisingly complex. That means the code runs on the server, which would make it awkward to run during the data entry process, which of course is browser-side.
The best solution would of course be instantaneously with some javascript but if it's not CPU-taxing it would still be plenty fast to send the title to the server as the input value changes. It's not uncommon for forms to do this with username eligibility checks etc.
I think they're getting at transformations that happen after submission, such as dropping initial question words and the like, not just the length restriction (which does appear).
Yup, basically this. Another idea would be to add a "please review this title that Hacker News won't let me submit with" button that would get these kinds of things in front of you sooner.
why did you switch from the mit site to twitter ? (i'm currently blocked on twitter - they want a phone number and are blocking all content till i provide one)
given that they blocked me for "rules violations" (which i clearly didn't do, as it was a brand new account that had taken zero actions and my previous account was fine when i closed it) i didn't want to circumvent the block (which might have actually been against the rules) so i didn't use technical measures (which certainly would have worked). i ended up just giving them my phone number, but it's a sad reality that we've accepted all these walled gardens
The title is sanitized on first submission, but you can edit the title afterward and put it back in. This works with some punctuation that gets cleaned out too.
If the title begins with a number or number +
gratuitous adjective, we'd appreciate it if you'd crop
it. E.g. translate "10 Ways To Do X" to "How To Do X,"
and "14 Amazing Ys" to "Ys." Exception: when the number
is meaningful, e.g. "The 5 Platonic Solids."
Please don't criticize others for using features of the website you are visiting. If you bring a keyhole to view a landscape you won't get the full experience either.
Rendering pages is a matter that should be solved by the client.
I don't see what the issue is with reminding people to be considerate of those who are browsing on mobile. Unfortunately, the latter group is also usually the ones with the least ability to actual solve their rendering problems.
It seems to be readable on iOS Safari. Scrolling sideways works fine. Worse than a regular quote, but not actually that bad. It is a client issue if it’s more broken than that.
You thought of using an obscure Unicode character before you thought of spelling it out? Well the good news is that you really do belong here on Hacker News :-)
I spent a while trying to work out if 42 in-a-circle was some kind of operator like 42! (factorial) or the like, because those three large numbers, cubed, didn't seem to refer to anything two-digit.
The source says "At a mathematical meeting in New York in 1903, F. N. Cole walked on to the platform and, without saying a single word, wrote two large numbers on the blackboard. He multiplied them out in longhand, and equated the result to 2^67-1."
Sorry, looks like the link has been change to a tweet from http://math.mit.edu/~drew/ I meant the html source of Andrew's dept homepage titled "Life, the Universe, and Everything" at that moment.
There's a large gulf between the simplicity of the question and the difficulty of obtaining the answer. Whenever a simple question cannot be answered via any known simple method, it seems as if one has unexpectedly come up against something deeper and more fundamental.
It’s a problem that is easy to state, yet hard to fully solve, and doesn’t seem like it should be unsurmountable, as it is easy to make some progress on (the “integers that equal 4 or 5 modulo 9 can’t be written as the sum of 3 powers of integers” part handles 22% of cases, and interested kids can understand it)
That makes it interesting to most mathematicians (if it weren’t easy to state, it could still be interesting, but to a smaller audience)
Edit: it also is easy for non-mathematicians with a knack for computing to get a crack at. You need not know much about number theory to write a program that searches for solutions for the unknown cases (it will help, but knowing how to optimize programs may help more, and that’s not something all mathematicians are good in). That grows the set of people who might find this interesting.
In number theory you study properties/patterns of the numbers. This is an example of such a property.
These properties often seem like they don’t have any applications, and often they don’t, but not always. For example, cryptography is basically all based on number theory.
I watched a great series once on generating ~prime numbers which explained how to use number theory to check a randomly generated number for a probability of being prime. By using a bunch of weird rules, you can be ~99% sure it's prime without having to do huge computations.
It's possible that solving this problem in a satisfactory way would teach us something useful about number theory, that's useful in real world practical stuff.
Andrew Wiles' proof of Fermat's Last Theorem is based on the modularity of elliptic curves. I'm not sure to what extent Wiles' proof contributed to elliptic curve cryptography hitting the scene a decade later, but it probably didn't hurt.
Like a lot of these "cute" problems, finding a proof of the problem requires a new theorem or novel application of a technique which benefits mathematics overall.
As a prime example, Fermat's Last Theorem was not a particularly applicable mathematical theorem. But when Andrew Wiles found a proof, he ended up proving several other elliptic curve conjectures which were important to the field.
While I do agree with you, I wouldn't be so quick to cast out numerology as a thing of importance. Hippies are pretty decent at sniffing things out, even if they explain them in totally insane ways.
EDIT: If you're opposed to this comment, I request that you explain your reasoning. Making the assumption that happiness is of any value, there's actually quite a bit to dig into here.
Numerology is factually not a branch of mathematics.
As for "hippies are pretty decent at sniffing things out", just because someone was correct about something in the past (despite a lack of evidence) does not make them correct today if they still lack evidence.
The burden of proof is on numerologists to show that they are correct, not on everyone else to disprove it.
Not saying it's correct. But given a world of infinite choices, sometimes it's helpful to look around at what's rising in importance on it's own. Even if there's no good reason.
The comment further up the chain (with the wikipedia links) was referencing the "importance" of 33 and 42 because they show up in quite a few fields -- assigning importance to certain numerical values is a kind of watered-down numerology (the fact that 42 was interesting in this problem doesn't necessarily mean that its "interesting-ness" transfers to the number itself).
(But I didn't bring it up, someone else did -- I was just responding to the argument that "there might be something to it".)
/~drew is their personal page and they probably hid it all to put this little gimmick as their homepage. It's commented out for easy reversal once it sails its course.
Because the numbers cubed are way larger than the numbers that Excel can represent precisely. Excel uses 64-bit IEEE 754 floats for all arithmetic. They can be used to accurately describe integers smaller than 2^53, or ~10^16. The first number cubed is ~-5*10^50, so you are very clearly outside the range where excel is precise.
You should not use Excel to do any serious mathematics, or really anything else where numerical precision is important.
No need to downvote this comment. It is a legitimate numerical computation question and one that has interesting answers as evidenced by this sub-thread. Not everyone knows about how computers do floating point arithmetic, handles large ints, or otherwise.
What about zero? Can zero be the sum of three cubes? Actually, I read that somebody proved it can't be done, but the proof is too long to fit in this comment. ;-)
I don't think that's a restriction that's usually enforced in this case. It seems nicer to allow the cubes to be zero since then the conjecture that the achievable sums are everything not 4 or 5 mod 9 can be stated without special cases.
Ignoring the century in the year, I love the coincidence that this question was first asked in the year '54 and in "Hitchhiker's", it's said that 6x9 and 42 are the same. In fact they are if 6x9 is base 10 (6x9=54), and 42 is base 13 (4x13+2 = 54).
So, we get three coincidences: This question was asked in '54 ; "Hitchhiker's" said the answer to the meaning of life is 54 (6x9, 42 base 13); and best of all, 42 was the last number solved. And if you want to add one more coincidence, this was solved in the year '19 (connecting 19 and 54).
All irrelevant coincidences applied with hindsight, but fun.
(Douglas Adams claimed that 42 was a randomly chosen number, but I'd argue his subconscious had been processing the idea for a while and gave him a number with a meaning. We just don't know which is the correct meaning.)
If anyone else could use planetary-scale computing (potentially for free, if your project is really cool), then come and talk to us.
The CE grid has over 2 million CPU cores, 600k+ unique IP addresses, can run anything in a Docker container and has integration with Ethereum. Adding Kubernetes and GPU support as we speak.
You can fire it up with 8 clicks, easier than AWS. This is literally a fully-functional worldwide computer.
PS. It's not just ridiculously huge, it is also ridiculously cheap :)
Mathematicians are interested in which natural numbers k can be expressed as a sum of three cubes. Prior to this year, it had been established that this is possible for all k < 1000 except for the following thirteen values:
This isn’t quite right, it’s easy to show that if n is 4 or 5 (mod 9), then there are no integer solutions to a^3 + b^3 + c^3 = n. The conjecture is that the mod 9 obstruction is the only one and all other integers can be represented as the sum of 3 cubes.
Because of the deep existential meaning of 42, which transcends any known religion or ideology. Its significant is only comparable, though not eclipsed, by the utility of a good towel. Never leave home with one.
I only recently heard what I think is a pretty solid answer to this question [1] that put it this way: We've pretty much got addition nailed down. We're pretty solid on multiplication. However, we are surprisingly weak mathematically when we try to put the two together; you can write down some extremely small math statements that baffled mathematicians for centuries, and for such statements that we have solutions for, they often get into very, very complicated math.
So you have things like Fermat's Last Theorum, or if you prefer, the Question: For a^n + b^n = c^n, are there any solutions with n > 2 for integers? Note how it's just multiplication and addition on the integers. There are simpler questions, but they don't get much simpler. There's no real analysis, transcendental numbers, imaginaries or higher-dimensional numbers, infinities, and so on, at least not in the question itself; it's literally so simple you can reasonably explain it to a middle schooler. It took mathematicians centuries, and the simplest version of the current proof is still PhD-level work to understand. (I suspect even a Master's student in math would have to carefully craft their entire post-doc education for the purpose of understanding this exact proof to be able to say they fully understood it, with no lemmas taken on faith, and I'm still not sure they could make it without a lot of independent study.)
You have things like "Can all of the numbers of a certain form be created via 'a^3 + b^3 + c^3'?", which sounds like it really ought to be simple. It's not too hard to eliminate 4 or 5 mod 9, but proving that it can always be done for everything else is beyond all current known math.
There's a lot of these sorts of questions in math right now. This is a particular single example of a family of very vexing problems.
It's hard to know what the practical impact of mastery over this combination would be, but I expect there probably would be some. Mastery over addition and multiplication have practical consequences that would require a series of books to explore; you have to think that mastering them in combination couldn't help but be practically useful.
[1]: I think it was a somewhat recent Numberphile video, but it may also have been a Terence Tao lecture. References solicited if you've got 'em.
Addition and multiplication (i.e. arithmetic) over the integers are all that are necessary to express first order logic and allowed Gödel to express his incompleteness theorems at such a fundamental level. The logical power of arithmetic is likely why many seemingly simple questions about arithmetic can have very complicated answers or no definitive answers at all.
I see! I'm math-dumb and always struggle with that sort of research. I need to see practical applications for what seems TO ME like ridiculous questions (I'm not implying they are, I have a feeling PhD+ level people don't usually waste time on pointless stuff). Thanks for the elaborate answer!
Questions that are simple to understand and difficult to answer will naturally attract the attention of a lot of mathematicians, because they don’t require a lot of specialized knowledge to work on.
I think a lot of people are missing the Doug Adam’s reference. Was the The Hitchhiker's Guide to the Galaxy not the reading staple of young HN participants?
It pains me how its 2019 and the fricking Google calculator is less powerful than a solar powered credit-card sized one from the 90s. A single chip made on the earliest imaginable IC processes can effortlessly deal with larger numbers than the lazy ignorant Google implementation. Maybe they can make this an interview question.
Most calculators of that era had a maximum number
Of digits between 8 and 12. Perhaps the Hp48 could do this calculation but not any of the credit card calcs.
No. The key to RSA is that it is relatively easy to find two primes and multiply them together. With the sum of three primes, there is no easy problem to be solved which will be harder for someone else.
No, it's just that not mentioning it is has a cool factor of 0, neither cool nor uncool, and mentioning it has a cool factor of around negative infinity.
There are others in this thread who are curious too, e.g.:
> Could someone elaborate on why this is interesting? The linked page doesn't have much context.
Just compare your question's tone with that, for example, and maybe that will explain why you're being downvoted [I did not, but I get why others are -- you deleted your other comment "Thanks for the downvotes..."]
Just googling "42 sum of 3 cubes" would have yielded better answers with less fuss. In general, I always google before asking in a forum. It's like not littering.
> Why did we look for a solution in the first place?
They did. I do not believe that you were involved.
> How is it important that a number can be a sum of three cubes?
People like things for their own sake. How is it important to have sex or drink a beer? Same thing. Also math has this uncanny tendency to turn out to be useful where you least expect it. Consider the primes. For a long time people might have asked the same question you are asking here, and yet now they are central in encryption and thus the digital finance market. Could not find a more capitalistic and materialistic use if you tried.
Why are you so bitter? I asked this genuinely. I doubt PhD+ people do that type of research "just for fun", or do that like someone like me drinks a beer. Someone answered elaborately, and I'm glad they did. Thanks anyway.
If you can break up a reasonably-sized table (perhaps 120 or so) of numbers into their respective sums of cubes, breaking many types of encryption is arbitrary.
The math is complicated, but the TL;DR is that you should already be selling your Bitcoins. Dogecoin should last another six months, seven at the outside.
bc 1.07.1
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006, 2008, 2012-2017 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
Yes, the interesting thing is that prior to this it was suspected, but not proven that 42 was the sum of three squares. This was the last number under 100 to find a solution for (for the numbers where a solution is possible)
https://en.m.wikipedia.org/wiki/Sums_of_three_cubes