max length of list s.t sum of the powers list equals n

Question

I am trying to find out what is the best upper bound on the size of a list such that

1. All its values are integers between $1$ and $n$
2. Its values are all different from each other
3. The sum of the $k^\text{th}$ powers of its entries equals $n$.

I quickly found an 'ok upper bound' that is the $\sqrt[k]n$, since any number bigger than this one will be larger the n after we power it by k (and all the numbers in the list must be different)

but I couldn't a smaller upper bound on the size of the list :( do you have any ideas?

I really appreciate any help you can provide.

Answer 1

Suppose the list has length $\ell$. In order for the list to be as long as possible, the entries should be as small as possible, meaning the entries are $1,2,\dots,\ell$. Therefore, $$ n=1^k+\dots+\ell^k\ge \int_0^\ell x^k\,\mathrm dx=\frac{\ell^{k+1}}{k+1} $$ We conclude that $$\ell\le \Big(n(k+1)\Big)^{1/(k+1)}.$$

Answer 2

Not an answer, but too long for a comment.

For each value of $k \ge 2$, there are several values of $n$ for which there is no such list. But there is an $N_k$ such, that every $n > N_k$, there is at least one such list (better called an integer partition of distinct $k$th powers). There are several entries in the Online Encyclopedia of Integer Sequences related to this, described below.

For $k = 2$, we're talking about possible sums of squares, a classical number theory topic. A003995 gives the $n$ values for which there is at least one sum of distinct squares equal to $n$; the largest $n$ not in the list is 128, so $N_2 = 128$. The smallest $n$ for which there are two sums of distinct squares is $n = 25$ from the Pythagorean triple $(3,4,5)$.

For $k = 3$, the analogous sequences are A003997 with the comment that $N_3 = 12{,}758$ and A003998 showing that $n = 216$ is the smallest that can be written as the sum of cubes in more than one way. (This list includes Hardy's "taxicab number" 1729.)

There are also OEIS entries for $n$ values with distinct $k$th power partitions for $k = 4, 5, 6$: respectively, A003999, A194768, and A194769.