There is a faster algorithm to check if a given integer is a sum (or difference) of two cubes $n=a^3+b^3$
I don´t know if this algorithm is already known (probably yes, but I can´t find it on books or internet). I discovered and use it to compute integers to $n < 10^18$
This process uses a single trick
$4(a^3+b^3)/(a+b) = (a+b)^2 + 3(a-b)^2$
We don´t know in advance what would be "a" and "b" and so what also would be "(a+b)", but we know that "(a+b)" should certainly divide $(a^3+b^3)$ , so if you have a fast primes factorizing routine, you can quickly compute each one of divisors of $(a^3+b^3)$ and then check if
$(4(a^3+b^3)/divisor - divisor^2)/3 = square$
When (and if) found a square, you have $divisor=(a+b)$ and $sqrt(square)=(a-b)$ , so you have a and b.
If not square found, the number is not sum of two cubes.
We know $divisor < (4(a^3+b^3)^(1/3)$ and this limit improves the task, because when you are assembling divisors of $(a^3+b^3)$ immediately discard those greater than limit.
Now some comparisons with other algorithms - for n = 10^18, by using brute force you should test all numbers below 10^6 to know the answer. On the other hand, to build all divisors of 10^18 you need primes until 10^9.
The max quantity of different primes you could fit into 10^9 is 10 $(2*3*5*7*11*13*17*19*23*29 = 5*10^9)$ so we have 2^10-1 different combinations of primes (which assemble the divisors) to check in worst case, many of them discarded because limit.
To compute prime factors I use a table with first 60.000.000 primes which works very well on this range.
---------- reply to Tito -------
Hi Tito, I think my poor notebook and FreeBasic language can´t manage these monster numbers.
I made this algorithm to try solve $a^3+b^3 = n*c^3$ (all integers), and it works very fast even in my notebook, but I can´t manage numbers greatert than 10^18 because 64 bits limitation of language.
I also have Ubasic program which have no limits for digits, but on the other hand it has no resources to manage tables with 60 million primes.
Take this example: I searched now all solucions for $a^3+b^3 = 1729*c^3$ with c<10^6 and program found these solutions in some 10 (ten) minuts.
$12^3 + 1^3 = 1729 * 1^3$ ,
$10^3 + 9^3 = 1729 * 1^3$ ,
$46^3 + -37^3 = 1729 * 3^3$ ,
$453^3 + -397^3 = 1729 * 26^3$ ,
$24580^3 + -24561^3 = 1729 * 271^3$ ,
$20760^3 + -3457^3 = 1729 * 1727^3$ ,
$25503^3 + -18503^3 = 1729 * 1810^3$ ,
$30151^3 + -1479^3 = 1729 * 2512^3$ ,
$2472830^3 + -1538423^3 = 1729 * 187953^3$ ,
$2879081^3 + 622072^3 = 1729 * 240681^3$ ,
$5328703^3 + -182620^3 = 1729 * 443967^3$
Miguel