Is every natural number representable as $\sum\limits_{k=1}^{n} \pm k^3$?

A well known identity is: $$(n+3)^2 - (n+2)^2-(n+1)^2 + n^2 = 4$$

and using this identity we prove that the set $\displaystyle \{\pm 1^2, \pm 1^2 \pm 2^2,\pm 1^2\pm 2^2\pm 3^2, \cdots\}$ contains every natural number greater than or equal to $1$.But for establishing this result we need to verify representation of the numbers $1,2,3,4$ in the form $\displaystyle \sum\limits_{k=1}^{n} \pm k^2$.

My question is can we say the same about the set of numbers $\displaystyle \sum\limits_{k=1}^{n} \pm k^3$, that is if every natural number greater than or equal to $1$ is representable in this form.

What about the general case $\displaystyle \sum\limits_{k=1}^{n} \pm k^s$ ?

This post shows how to compute the constant, $\displaystyle C_s = \sum\limits_{k=1}^{2^s} \pm k^{s} = \large{2^{\frac{s(s-1)}{2}}s!}$ where, the signs $\pm$ are chosen as explained here.

• Exponent 4 was asked here There is a paper cited that is supposed to solve the exponent 3 problem as well, but I am not able to view Postscript so far. Dec 23 '14 at 22:27
• @RossMillikan, see citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.79.5129 for a PDF (see cached).
– lhf
Dec 24 '14 at 1:14
• @lhf Thanks ! :-)
– r9m
Dec 24 '14 at 1:19
• @RossMillikan: There is an identity, $$\sum\limits_{k=1}^{7112}\pm(x+k)^5 = 480$$ so all that remains is to test all integers $1<N<240$. Kindly see this post. Dec 29 '14 at 10:10

You will have to look a bit farther. A similar identity to the one you cite: $$(n+7)^3-(n+6)^3-(n+5)^3+(n+4)^3-(n+3)^3+(n+2)^3+(n+1)^3-n^3=48$$ means we just need to solve the problem for $[-23,24]$ and because the exponent is odd we can consider opposite signs equivalent. Because the cubes are spaced further than the squares it will probably take a bunch of searching to fill in all of $[1,24]$. Of course, $1,7,9,18,20$ are easy.

• It did not take too much searching to fill in $\{1, \dotsc, 24\}$; see my post below. Exponent 3 is solved!
– Unit
Dec 24 '14 at 0:11
• (+1) Similar identities for higher values of $s$ can be derived using the Thue-Morse sequence for choosing the signs. So the problem is virtually solved for any value of $s$. Dec 24 '14 at 0:30
• @JackD'Aurizio I guess will need $2^s$ terms to eliminate all but the constant terms in the identity I think. Is there a particular algo for doing it for each case $s$ ? :-) How do we use the Thue-Morse sequence to construct the same ?
– r9m
Dec 24 '14 at 1:16
• @RossMillikan Is there a way to avoid the brute-code-attack on the verification problem ? :)
– r9m
Dec 24 '14 at 1:23
• @r9m: I don't know of one. To use Thue-Morse, given the signs for $s$, the signs for $s+1$ start with the same series, then you append the same series with the signs flipped $+ \leftrightarrow -$. You can see that operation when I went from $s=2$ to $s=3$ Dec 24 '14 at 1:43

Consider this an addendum to Ross's answer. Found by a Python script which ran while I dined.

$1 = 1^3$ (at least 7 other ways)

$2 = 1^3 - 2^3 + 3^3 - 4^3 + 5^3 + 6^3 + 7^3 - 8^3 - 9^3 + 10^3 + 11^3 - 12^3$ (at least 12 other ways)

$3 = 1^3 - 2^3 + 3^3 + 4^3 + 5^3 + 6^3 - 7^3 + 8^3 - 9^3 + 10^3 - 11^3 - 12^3 + 13^3$ (at least 6 other ways)

$4 = -1^3 - 2^3 + 3^3 + 4^3 - 5^3 + 6^3 + 7^3 - 8^3$ (at least 18 other ways)

$5 = -1^3 + 2^3 + 3^3 - 4^3 + 5^3 - 6^3 + 7^3 + 8^3 - 9^3$ (at least 6 other ways)

$6 = 1^3 - 2^3 + 3^3 + 4^3 - 5^3 + 6^3 + 7^3 - 8^3$ (at least 14 other ways)

$7 = -1^3 + 2^3$ (at least 12 other ways)

$8 = 1^3 + 2^3 - 3^3 + 4^3 - 5^3 + 6^3 + 7^3 - 8^3 - 9^3 + 10^3 - 11^3 - 12^3 + 13^3 - 14^3 + 15^3$ (at least 12 other ways)

$9 = 1^3 + 2^3$ (at least 13 other ways)

$10 = 1^3 + 2^3 + 3^3 - 4^3 + 5^3 - 6^3 - 7^3 + 8^3 + 9^3 - 10^3 + 11^3 + 12^3 - 13^3 + 14^3 - 15^3$ (at least 16 other ways)

$11 = 1^3 + 2^3 - 3^3 + 4^3 - 5^3 + 6^3 - 7^3 - 8^3 + 9^3$ (at least 5 other ways)

$12 = -1^3 - 2^3 - 3^3 - 4^3 + 5^3 + 6^3 - 7^3 + 8^3 - 9^3 - 10^3 + 11^3$ (at least 15 other ways)

$13 = -1^3 + 2^3 + 3^3 - 4^3 - 5^3 + 6^3 + 7^3 - 8^3 - 9^3 + 10^3 - 11^3 + 12^3 + 13^3 - 14^3$ (possibly other ways)

$14 = 1^3 - 2^3 - 3^3 - 4^3 + 5^3 + 6^3 - 7^3 + 8^3 - 9^3 - 10^3 + 11^3$ (at least 9 other ways)

$15 = -1^3 + 2^3 - 3^3 - 4^3 - 5^3 - 6^3 - 7^3 + 8^3 - 9^3 + 10^3$ (at least 1 other way)

$16 = 1^3 - 2^3 - 3^3 - 4^3 + 5^3 - 6^3 - 7^3 - 8^3 + 9^3 - 10^3 + 11^3$ (at least 10 other ways)

$17 = 1^3 + 2^3 - 3^3 - 4^3 - 5^3 - 6^3 - 7^3 + 8^3 - 9^3 + 10^3$ (at least 6 other ways)

$18 = -1^3 - 2^3 + 3^3$ (at least 17 other ways)

$19 = 1^3 - 2^3 - 3^3 + 4^3 - 5^3 + 6^3 - 7^3 + 8^3 + 9^3 - 10^3$ (at least 8 other ways)

$20 = 1^3 - 2^3 + 3^3$ (at least 19 other ways)

$21 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 - 6^3 - 7^3 - 8^3 + 9^3 + 10^3 - 11^3 - 12^3 + 13^3$ (at least 5 other ways)

$22 = 1^3 + 2^3 + 3^3 + 4^3 - 5^3 + 6^3 + 7^3 - 8^3$ (at least 10 other ways)

$23 = 1^3 + 2^3 + 3^3 + 4^3 - 5^3 - 6^3 + 7^3 + 8^3 - 9^3 + 10^3 - 11^3 - 12^3 + 13^3$ (at least 5 other ways)

$24 = 1^3 + 2^3 - 3^3 - 4^3 + 5^3 + 6^3 - 7^3 + 8^3 + 9^3 + 10^3 - 11^3 + 12^3 + 13^3 + 14^3 - 15^3 - 16^3$ (at least 7 other ways)

Each of the above representations is the shortest possible. The algorithm created a sequence of sets $S_n$ with $S_0 = \{0\}$ and $S_n = \{x+n^3, x-n^3 : x \in S_{n-1}\}$ for $n > 0$, so that $S_1 = \{1, -1\}$, $S_2 = \{9, -7, 7, -9\}$, etc. The algorithm also kept track of the sequence of signs used to arrive at each particular number.

• Nice work ! :D Thank's !!!
– r9m
Dec 24 '14 at 1:11
• @Unit: Do you suppose you can do the same for at least $1<N<100$ for $5$th powers? Kindly refer to my answer below. Dec 29 '14 at 3:54
• @TitoPiezasIII: Ahh, I just read this message. I will try, though it seems alexwlchan is almost there.
– Unit
Dec 29 '14 at 22:55
• @Unit: And it seems Zander even managed $0\leq N<10000$. The ingenuity of some people never ceases to amaze. Dec 29 '14 at 23:44

For 5th powers, there is an identity,

$$\sum\limits_{k=1}^{168}\pm(x+k)^5 = 480$$

analogous to the 3d powers mentioned by R. Millikan in his answer.

What remains to be shown is that all $0\leq N<240$ can be decomposed into sums of fifth powers. See this post.

(P.S. The number of addends can be reduced to just $m=168$.)