4
$\begingroup$

This is the partition problem as applied to a special set, namely the first $n$ $k$th powers. Assume the notation,

$$[a_1,a_2,\dots,a_n]^k = a_1^k+a_2^k+\dots+a_n^k$$

I. Family 1

The following infinite family is quite well-known,

$$[1,\color{blue}{4}]^1 = [2,3]^1$$

$$[1,4,6,7]^2 = [2,3,5,\color{blue}{8}]^2$$

$$[1,4,6,7,10,11,13,\color{blue}{16}]^3 = [2,3,5,8,9,12,14,15]^3$$

and so on, for a partition of the $k$th power of the first $\color{blue}{4,8,16,32,64} = 2^{k+1}$ positive integers. (See also this post.)

II. Family 2

However, it can be noticed that,

$$[1, \color{brown}{4}]^1 = [2, 3]^1$$

$$[1, 2, 4, \color{brown}{7}]^2 = [3, 5, 6]^2$$

$$[1, 2, 4, 8, 9, \color{brown}{12}]^3 = [3, 5, 6, 7, 10, 11]^3$$

$$[1, 6, 9, 11, 12, 14, 15, 16, 17]^4 = [2, 3, 4, 5, 7, 8, 10, 13, 18, \color{brown}{19}]^4$$

$$[1, 5, 7, 8, 12, 14, 17, 18, 19, 20, 22, 24, 25, 26]^5 = [2, 3, 4, 6, 9, 10, 11, 13, 15, 16, 21, 23, 27, \color{brown}{28}]^5$$

and so on, with the sequence $\color{brown}{4,7,12,19,28} = k^2+3.$ (For $k=3$, see this post.)

Questions:

  1. Is it true that there is a partition of the $k$th power of the first $k^2+3$ positive integers such that the sum of each set is equal?
  2. Is $k^2+3$ the minimum number of consecutive terms, or can there be a third family with a smaller number of terms for higher $k$?
  3. What is the partition of the first $n$ $6$th powers with $n\leq6^2+3$?

$\color{red}{Update:}$

It turns out $k^2+3$ is not the minimum number $n$ for higher $k$. I used Mathematica to check,

$$\sum_{m=1}^n \epsilon\, m^k = 0$$

where $\epsilon = \pm1$. For $k=1,2,3$, we find $n = 4,7,12$ as in the second family. However, $k=4$ has a smaller solution at $n=16$,

$$[1, 2, 3, 4, 8, 9, 10, 11, 12, 16]^4 = [5, 6, 7, 13, 14, 15]^4$$

and $k=5$ also has one at $n=24$,

$$[1, 2, 5, 7, 10, 13, 14, 15, 19, 20, 21, 23]^5 = [3, 4, 6, 8, 9, 11, 12, 16,17, 18, 22, 24]^5$$

Presumably for $k=6$, it should be $28\leq n<<39$, but my Mathematica code is too slow for $n>28$. (The Wikipedia link above gives a pseudo-polynomial time algorithm, maybe some interested soul might be interested to implement it.)

It seems there might be several families then, and it would be nice to find a unifying principle like in the first family.

$\endgroup$
1
$\begingroup$

There are $2^n$ subsets of the first $n$ positive integers, and for each subset the sum is bounded below by zero and above by $\sum_{i=1}^n i^k = O(n^k/k)$. The problem of finding a partition with equal sums is equivalent to finding a subset with a particular sum in this range, specifically $\frac 12 \sum_{i=1}^n i^k$. If we think these subset sums are distributed somewhat uniformly in this range, then this heuristic suggests the minimum $n$ should grow like $k\log k$, and for $n=k^2+3$ there should be increasingly many possible partitions.

Note that in addition to your examples there are at least 15 other partitions with $k=4,n=19$, e.g. $$ \begin{align} \frac 12 \sum_{i=1}^{19} i^4 &= [1, 3, 4, 8, 10, 11, 14, 17, 19]^4 \\ &= [1,2,3,6,7,14,15,17,18]^4 \\ &= [1,2,4,9,11,12,15,17,18]^4 \\ & = [1,2,5,7,8,11,14,15,16,18]^4 \end{align} $$ and two others for $k=5,n=24$, and at least five more for $k=5,n=28$. So it seems to me you won't be able to unify a sequence of solutions into a family based solely on the values of $n$.

I found these for $k=6,n=32$ $$ \begin{align} \frac 12 \sum_{i=1}^{32} i^6 & = [1, 2, 3, 4, 6, 8, 9, 10, 15, 16, 17, 21, 23, 28, 31, 32]^6 \\ & = [1, 2, 3, 8, 11, 13, 14, 16, 17, 18, 21, 24, 26, 27, 29, 32]^6 \\ &= [1, 2, 7, 8, 9, 12, 14, 17, 18, 19, 20, 23, 24, 29, 30, 31]^6 \end{align} $$ but I only looked for balanced partitions, so I haven't verified there are none with $n<32$.

$\endgroup$
  • $\begingroup$ Ah, so there's that elusive creature, $$\small[1, 2, 3, 4, 6, 8, 9, 10, 15, 16, 17, 21, 23, 28, 31, 32]^6 = [5, 7, 11, 12, 13, 14, 18, 19, 20, 22, 24, 25, 26, 27, 29, 30]^6$$ My primitive code would have taken $2^{31}$ steps to find it. Thanks! (Yes, for the $k < 6$, I did notice there were multiple solutions.) $\endgroup$ – Tito Piezas III Apr 4 '15 at 6:57
  • $\begingroup$ For $k=7$, what do you think should be $n$ for $$\sum_{m=1}^n \pm m^7 = 0$$ I assumed $n=40$, rigged a faster code, ran it for more than hour before giving up. It can't be $n=41,42$ as the positive sum is odd, so is it $44<n<49$? In other words, for $k>3$, is $n\leq k^2$ a conservative bound? $\endgroup$ – Tito Piezas III Apr 16 '15 at 12:27

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.