Hacker News Reader

Comment by jjtheblunt | Hacker News Reader

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?

View on HN

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!

Agreed

For a^3 + b^3 + c^3 = 42,

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.

https://people.maths.bris.ac.uk/~maarb/papers/cubesv1.pdf

> 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."

https://phys.org/news/2019-09-sum-cubes-solvedusing-real-lif...

>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

Here: https://www.youtube.com/watch?v=ASoz_NuIvP0

I just came out watching the solution to how he actually solved it.

The problem is not to enumerate or find the set of numbers that are sums of cubes.

The conjecture is: every integer that is not of the form 9k+4 or 9k+5 can be expressed as the sum of 3 cubes (and, in infinitely many ways).

It is enumerable, but I think what you may have missed is that negative numbers are included. i.e.,

> 42 = (-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3

Strangely, typing this into Google does NOT result in 42

((-80538738812075974)^3)+(80435758145817515^3)+(12602123297335631^3)

DDG doesn't handle it correctly either (gives the same very-large answer as Google). I assume there's some sort of integer overflow going on somewhere. Wolfram Alpha does ok, though: https://www.wolframalpha.com/input/?i=%28%28-805387388120759...

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)

I’m actually surprised someone at Google hasn’t switched to BigInt yet in JS if the browser supports it? Googlers, front page OKR time! :)

WolframAlpha should handle it fine, with Mathematica behind the scenes.

python handles big int automatically:

sh-4.2$ python -c "print(-805387388120759743+804357581458175153+126021232973356313)" 42

nah, bigint is just another wall you may hit

bc/dc arbitrary precision calculators are usually installed by default on *nix platforms and they handle numbers with thousands of digits

$ time echo '12345^67890' |bc |wc -c

285941

real 0m2.137s

user 0m2.128s

sys 0m0.012s

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.

Hn seems to have stripped the asterisks from your message.

for big numbers you can use bc (infix) or dc (rpn) calculator:

echo '((-80538738812075974)^3)+(80435758145817515^3)+(12602123297335631^3)' | bc

echo '_80538738812075974 3 ^ 80435758145817515 3 ^ 12602123297335631 3 ^ + + p' | dc

Nice! My go to calc is dc. If you're like me at all, then you might like to know that we can avoid the pipe usng the -e switch

    $ dc -e '_80538738812075974 3^ 80435758145817515 3^+ 12602123297335631 3^+p'

Surprisingly, the calculator that shipped with my phone seems to handle it well.

If you're typing it into google on a desktop browser, open your JS console. As earlier comments pointed out, in JavaScript it's

  (-80538738812075974n)**3n + 80435758145817515n**3n + 12602123297335631n**3n

Ah, good old integer rounding...

With negative numbers, it's still enumerable, as if it were a six-tuple of natural numbers, I figured.

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.

You only need to enumerate pairs of integers, the 3rd is then forced (quickly check if it's a cube).

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.

Agreed, though enumeration of triples means you can enumerate sums of cubes of the triples...it just would take literally forever to enumerate them.

You can enumerate all syntactically valid proofs too, and just check each one to see if it proves whatever proposition you’re curious about.

Yep, and how tedious that would be!

So what you're saying is (with needlessly complicated terms) that we can brute force the search for sums of three cubes?

I'm misunderstanding "needlessly complicated"?

https://en.wikipedia.org/wiki/Recursively_enumerable_set

They mean "unsolved" in the sense that for eg we cant prove or disprove claims like "all integers are the sum of three cubes".

Oops:

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.

https://twitter.com/robinhouston/status/1169938974246342658?...

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.

Diagonal argument? (That's how you show something is uncountable.)

It's that finite Cartesian products of countable sets are countable https://proofwiki.org/wiki/Cartesian_Product_of_Countable_Se...

Oh, that's funny, thanks for pointing that out.

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.

Reply on news.ycombinator.com