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, ..., 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}$?

3 typo fixed

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, ..., 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.$$ <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},$$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$ 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$?<2^{n+1}$?

2 added 33 characters in body; edited body

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, ..., 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.$$ 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},$$ 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 the any sequence that is polynomial of degree not greater than $n$-th powers. 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$13:$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$ (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