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

• @Joppy, I updated the question. – trafalgarLaww Dec 5 '17 at 9:12
• Why do you believe it has a closed form? – Galc127 Dec 5 '17 at 9:24
• @Galc127, I hope for a good recurrence relation between addendums at least. – trafalgarLaww Dec 5 '17 at 9:38
• My answer to your previous, very similar question should adapt quite well, I think. There is a little more to keep track of, but that should be it. Have you tried that? – Arthur Dec 5 '17 at 9:52
• @Arthur, yes, but it did not help. – trafalgarLaww Dec 5 '17 at 10:11

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:

1. Get $x^{n^3}, x^{3n^2 - 3n +1}$ and $x^{6n-6}$ from previous iteration
2. Calculate $x^{6n} = x^{6n-6}\cdot x^6$
3. Calculate $x^{3(n+1)^2 - 3(n+1) + 1} = x^{3n^2 - 3n +1}\cdot x^{6n}$
4. Calculate $x^{(n+1)^3} = x^{n^3}\cdot x^{3(n+1)^2 - 3(n+1) + 1}$
5. Add $x^{(n+1)^3}$ to your summation variable
6. Send $x^{(n+1)^3}, x^{3(n+1)^2 - 3(n+1) + 1}$ and $x^{6n}$ to the next iteration
• The only problem which I can not put up with is that now I have to store a lot of data from previous steps. – trafalgarLaww Dec 5 '17 at 11:55
• Storing three numbers usually isn't that much, are you certain that that's a problem? Also, there will always be a tradeoff between memory and time. You could store no numbers between iterations if you just calculated each term from scratch, but you don't want to do that, because if you did you wouldn't come here asking for advice. I believe that this is a good tradeoff, as I don't think it's possible to do much faster, and I'm not using a lot of storage, given how abundant memory is these days in hardware and software. – Arthur Dec 5 '17 at 12:01
• Could you, please, comment what is wrong here? If I substitute n = 1 in $x^{3(n+1)^2 - 3(n+1) + 1} = x^{3n^2 - 3n +1}\cdot x^{6n+6}$ I won`t get an equality. – trafalgarLaww Dec 5 '17 at 12:19
• @trafalgarLaww You're right, I found a sign mistake in my notes. That ought to be correct now. – Arthur Dec 5 '17 at 12:22
• I got $x^{3(n+1)^2-3(n+1)+1}=x^{3n^2+3n+1}$ instead of $x^{3(n+1)^2-3(n+1)+1}=x^{3n^2-3n+1}\cdot x^{6n}$... Am I right? – trafalgarLaww Dec 5 '17 at 12:33