25
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 23 '14 at 22:27
  • 1
    $\begingroup$ @RossMillikan, see citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.79.5129 for a PDF (see cached). $\endgroup$
    – lhf
    Dec 24 '14 at 1:14
  • $\begingroup$ @lhf Thanks ! :-) $\endgroup$
    – r9m
    Dec 24 '14 at 1:19
  • $\begingroup$ @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. $\endgroup$ Dec 29 '14 at 10:10
15
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ It did not take too much searching to fill in $\{1, \dotsc, 24\}$; see my post below. Exponent 3 is solved! $\endgroup$
    – Unit
    Dec 24 '14 at 0:11
  • 1
    $\begingroup$ (+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$. $\endgroup$ Dec 24 '14 at 0:30
  • $\begingroup$ @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 ? $\endgroup$
    – r9m
    Dec 24 '14 at 1:16
  • $\begingroup$ @RossMillikan Is there a way to avoid the brute-code-attack on the verification problem ? :) $\endgroup$
    – r9m
    Dec 24 '14 at 1:23
  • 1
    $\begingroup$ @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$ $\endgroup$ Dec 24 '14 at 1:43
15
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Nice work ! :D Thank's !!! $\endgroup$
    – r9m
    Dec 24 '14 at 1:11
  • $\begingroup$ @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. $\endgroup$ Dec 29 '14 at 3:54
  • $\begingroup$ @TitoPiezasIII: Ahh, I just read this message. I will try, though it seems alexwlchan is almost there. $\endgroup$
    – Unit
    Dec 29 '14 at 22:55
  • $\begingroup$ @Unit: And it seems Zander even managed $0\leq N<10000$. The ingenuity of some people never ceases to amaze. $\endgroup$ Dec 29 '14 at 23:44
5
$\begingroup$

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$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.