Some time ago, while putting my nose in the Sloane's Online Encyclopedia of Integer Sequences, I came over the sequence [A019568](http://oeis.org/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](http://oeis.org/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}$?
> 
> 
> 



Asymptotic growth of a certain integer sequence
Since there are about 2k possible sums, with typical order of magnitude about kn, it seems reasonable to guess that the first case when one of these sums is 0 will occur when these 2 numbers are about equal, which is when k is about n log(n)/log(2). This incredibly crude estimate is somewhat smaller than the numerical data, but maybe suggests about the right growth rate,


