Compute the sum fast. How can I compute the following sum in the fastest way possible?
$y = 1 + x + ... + {x}^{{n}^{3}}=\sum_{i = 0}^{n}{x}^{{i}^{3}}$
I wrote that $n^3 - (n-1)^3 = 3n^2-3n+1$, but so far it does not help a lot.

This is a modified version of my answer here, which was the same question only with square exponents rather than cubed ones.
You have already calculated $x^{(n+1)^3} = x^{n^3}\cdot x^{3(n+1)^2-3(n+1)+1}$ (I shifted the indices by one to conform with my other answer). We also have $x^{3(n+1)^2-3(n+1)+1}=x^{3n^2-3n+1}\cdot x^{6n}$. You could then use the following recursion:


*

*Get $x^{n^3}, x^{3n^2 - 3n +1}$ and $x^{6n-6}$ from previous iteration

*Calculate $x^{6n} = x^{6n-6}\cdot x^6$

*Calculate $x^{3(n+1)^2 - 3(n+1) + 1} = x^{3n^2 - 3n +1}\cdot x^{6n}$

*Calculate $x^{(n+1)^3} = x^{n^3}\cdot x^{3(n+1)^2 - 3(n+1) + 1}$

*Add $x^{(n+1)^3}$ to your summation variable

*Send $x^{(n+1)^3}, x^{3(n+1)^2 - 3(n+1) + 1}$ and $x^{6n}$ to the next iteration

