Some time ago, while putting my nose in the Sloane's Online Encyclopedia of Integer Sequences, I came over the sequence A019568 defined as follows:

$a(n):=$ the smallest positive integer $k$ such that the set $\{1^n, 2^n, 3^n,\dots k^n\}$ can be partitioned into two sets with equal sum.

In other words, $a(n)$ is the smallest $k$ such that there is a choice of signs **+** or **-** in the expression $$1^n\pm2^n\pm\dots\pm k^n \qquad\qquad(1) $$ that makes it vanish. In order to show that this $a(n)$ is a well-defined integer (that is: that at least one such $k$ does exist), a simple observation gives in fact a bound $$a(n)<2^{n+1}.$$ Reason: $(1-x)^{n+1}$ divides the polynomial
$$Q(x):=(1-x)(1-x^2)(1-x^4)\dots(1-x^{2^n})=+1-x-x^2+x^3-\dots +(-1)^n x^{2^{n+1}-1},$$
therefore, if $S$ is the shift operator on sequences, the operator $Q(S)$ has the $(n+1)$-th discrete difference $(I-S)^{n+1}$ as factor, hence annihilates any sequence that is polynomial of degree not greater than $n$. In particular, the algebraic sum (1) with the signs of the coefficients of $Q(x)$ vanishes (incidentally, the sequence of signs is the so called Thue-Morse sequence A106400, $+--+-++--++-+--+\dots$.

However, looking at the reported values of $a(n)$ for $n$ from $0$ to $12:$

$$2,\ 3,\ 7,\ 12,\ 16,\ 24, \ 31,\ 39,\ 47,\ 44,\ 60,\ 71,\ 79,$$

it looks like the growth of $a(n)$ is much below $2^{n+1}$ (I have a weakness for sequences that grow slowly, here's possibly the main motivation of this question).

Question: Does anybody have a reference for the above sequence? Can you see how to prove an asymptotics, or a more realistic bound than $a(n)<2^{n+1}$?