HN Explorer

Write all solutions for a^3 + b^3 = c^3 + d^3

2 points by saltcookie ↗ HN
this runs the fastest without memory overhead

int Search(){ int MAX = 10000000; for(int a = 0; a < MAX; a++){ int a3 = a * a * a; if(a3 > MAX) break; for(int b = a; b < MAX; b ++){ int b3 = b * b * b; if(a3 + b3 > MAX)break; for(int c = 0; c < a; c++){ int c3 = ccc; int m = a3 - c3; int d = b+1; while(true){ int d3 = d * d * d; if(d3-b3 <= m){ if((d3 - b3) == m){ count++; PUSH_SOLUTION(a3, b3, c3, b3, a, b, c, d); } d++; continue; } else break; } } } } return 0; }

2 comments

[ 2.9 ms ] story [ 14.5 ms ] thread
dalke
As one of the comments points out, these are the so-called "taxicab numbers", based on a story about Hardy trying to make small talk with Ramanujan. Hardy's taxicab's number was 1729, which he found boring. Ramanujan pointed out it was the first number which was the sum of two different cubes in two different ways.

There are six known taxicab numbers; see http://en.wikipedia.org/wiki/Taxicab_number for a list and their decompositions. The solutions at http://math.stackexchange.com/questions/2815/find-taxicab-nu... are much more knowledgeable about math than the ones at StackOverflow, as one might expect.

Note that in your/saltcookie's proposed answer there is mistranslation of the problem. The posed question says "a, b, c, d lie between [0, 10^5]" but does not restrict their cubes, while you have a test for "if(a3 > MAX)" and "if(a3 + b3 > MAX)".

Even if those checks are removed, there is still a likely overflow error because most systems use 32 bit integers for 'int'. a * a * a as an int may be a number <= 10000000, including a negative number.

That is, your output should include 48988659276962496 = 38787^3 + 365757^3 as an answer because 38787 < 365757 < 10000000 so fits the input constraints; note that 48988659276962496 cannot be represented as a 32 bit integer.