$p$-Splittable Integers

Let $p$ be a positive integer. For each nonnegative integer $k$, write $[k]$ for the set $\{0,1,2,\ldots,k\}$. Also, we define $[-1]:=\emptyset$. We say that an integer $k\geq -1$ is $p$-splittable if there is a partition of $[k]$ into $p$ subsets $A_1$, $A_2$, $\ldots$, $A_p$ such that $\sum_{x\in A_1}\,x=\sum_{x\in A_2}\,x=\ldots=\sum_{x\in A_p}\,x$ (i.e., these sets have the same sum). Such a partition $\left\{A_1,A_2,\ldots,A_p\right\}$ is called a $p$-splitting of $[k]$.

What are all $p$-splittable integers for a given $p$? How many $p$-splittings of $[k]$ are there for each of these available $k$’s? If the exact number of $p$-splittings of $[k]$ is not easily computable, then what is the asymptotic answer?

Clearly, $k=-1$ and $k=0$ are $p$-splittable. We can also ignore the trivial case $p=1$. We know that, if $p=2$, then all $p$-splittable numbers are of the forms $4t-1$ and $4t$, where $t$ is a nonnegative integer. If $p$ is an odd prime, then all $p$-splittable numbers are integers of the forms $tp-1$ and $tp$, where $t\in\{0,2,3,4,\ldots\}$.

For $p=2$, we can show that the number of $2$-splittings of a $2$-splittable integer $k$ is given by the coefficient of $x^{\frac{k(k+1)}{4}}$ in the expansion of $\prod_{r=1}^k\,\left(1+x^r\right)$. For example, if $k=3$, there are two $2$-splittings of $[3]$, namely, $\big\{\{0,1,2\},\{3\}\big\}$ and $\big\{\{1,2\},\{0,3\}\big\}$, whereas $$\prod_{r=1}^3\,\left(1+x^r\right)=1+x+x^2+2x^3+x^4+x^5+x^6$$ whose coefficient of $x^{\frac{k(k+1)}{4}}=x^3$ is also $2$. Similarly, there are $2$, $8$, and $14$ $2$-spittings of $[k]$ for $k=4$, $k=7$, and $k=8$, respectively. I do not know if there is any closed form for this coefficient for an arbitrary $2$-splittable $k$.

I conjecture the following:

(1) If $p$ is odd, then, for any $j\in\{-1,0,1,2,\ldots,p-2\}$ such that $p\mid j(j+1)$, every integer of the form $tp+j$, where $t\in\{2,3,4,\ldots\}$, is $p$-splittable, and nothing else (except $-1$ and $0$) is $p$-splittable.

(2) If $p$ is even, then, for any $j\in\{-1,0,1,2,\ldots,2p-2\}$ such that $2p\mid j(j+1)$, every integer of the form $2tp+j$, where $t$ is a positive integer, is $p$-splittable, and nothing else (except $-1$ and $0$) is $p$-splittable.

This conjecture is true, at least, if $p$ is a prime power (where $j=-1$ and $j=0$ are the only possible choices of $j$). If you can show that (1) holds for $t=2$ and for $t=3$, and that (2) holds for $t=1$, then you are done. It is worth noting that, if $k$ is $p$-splittable, then $k+2p$ is $p$-splittable.

Inspiration: Partitioning $\{1,\cdots,k\}$ into $p$ subsets with equal sums

P.S. I include $k=0$ and $k=-1$ for the sake of completeness. There is nothing subtle about these numbers.

Solutions Collecting From Web of "$p$-Splittable Integers"

likely last edit, formatting for clarity:

We say $n$ is $p$-splittable if there is a partition $A_1,…,A_p$ of $\{1,…,n\}$ with $\sum A_i := \sum_{a \in A_i} a = \sum A_j$ for all $i,j\leq p$

We call $n$ uniformly $p$-splittable if there is such a partition with $|A_i|=|A_j|$ for all $i,j \leq p$

We call such a partition a $p$-split of $n$

Let $s_p(n)$ $(\bar{s}_p(n))$ denote the number of (uniform) $p$-splits of $n$


Some truths:

$\bar{s}_p \leq s_p$

If $n$ is $p$-splittable then $p| \frac{(n+1)n}{2}$

If we have equality $s_p(n)=1$ (there is exactly one $p$-split of $n$)

$2p$ and $2p-1$ are $p$-splittable, $2p$ uniformly.

If $n$ is $p$-splittabe and $p’|p$ then $n$ is $p’$-splittable and we obtain a lower bound of $s_{p’}(n)\geq \frac {p!}{(\frac{p}{p’}!)^{p’}}$ (the number of ways to make a $p$-split into a $p’$-split by melting groups of $\frac{p}{p’}$ together)

(it may be possible to get a bound in terms of $s_p(n)$ if one can argue away double counting)

If $n$ is uniformly $p$-splittable then $mn$ is uniformly $p$-splittable for all m$\in \mathbb{N}$

If $n$ is $p$-splittable and $k$ is uniformly $p$-splittable, then $m+k$ is $p$-splittable

If $m,n$ are uniformly $p$-splittable then $m+n$ is uniformly $p$-splittable


The $p$-splittable numbers are then a finite union of (affine) copies of the uniformly $p$-splittables and are generated by finitely many primitive $p$-splittable numbers, a trivial upper bound on the count of primitives is the smallest non-zero uniformably $p$-splittable number $2p$. A better bound is achieved by $\# \{j \in \{-1,0,…,2p-2\} \; with \; 2p|j(j+1)\}$

It is conjectured this bound is exact and the primitive $p$-splittables are of the form $2p+j$ for $j$ in this set. (This is numerically proven for $p\leq 184$)

If $n$ is uniformly $p$-splittable then $n$ must be a multiple of $p$. I will give a full categorization:

Let $p \in \mathbb{N}$ then the uniformly $p$-splittables are $p \mathbb{N} \backslash p$ if $p$ is odd and $2p \mathbb{N}$ if p is even (or $\mathbb{N}$ for $p=1$)

proof: It is apparent that $2p$ is uniformly $p$-splittable and $p$ is not. It suffices to show that for odd $p$ $3p$ is uniformly $p$-splittable and for even $p$ no odd multiple is.

Let $p$ be even and $k$ odd. Then $\frac{kp(kp+1)}{2}$ is no multiple of $p$ (it is a odd multiple of $\frac p 2$)

Let $p$ be odd:

let $[i]$ denote $ i \; mod \; p$

Then a uniform $p$-split of $3p$ is given by
$A_i = \{ 1+[i], (p+1)+[\frac{p-1}{2}+i], 2p+1+[p-1-2i]\}$ for $i=0,…,p-1$
Obviously each $A_i$ has 3 elements and each number $\leq 3p$ is represented. We need to show $[i]+[\frac{p-1}{2}+i]+[p-1-2i]$ is independent of $i$.

This is true because for $i \leq (p-1)/2$ all the arguments are in $(0,…,p-1)$ and for $(p+1)/2 \leq i \leq p-1$ we have $[\frac{p-1}{2}+i]=\frac{p-1}{2}+i-p$, $[p-1-2i]=p-1-2i+p$ in each case the sum is equal to $\frac{3(p-1)}{2}\square$

$\bar{s}_p(p^2) \geq (p-1)!$ (by construction of $(p-1)!$ uniform $p²$-splits)


Things to look into:

  • The original conjecture. It can be achieved by

    1. simply constructing $p$-splits for $2p+j$ for the given $j$ (note $j=-1,0$ are trivial) or

    2. Constructing an algorithm for it. Problems here lie in proving the algorithm finishes, this leads into study of finding how to split a set into heaps of (differing) given sizes (splits would be the special case where all stacks have equal size)

    3. Note that the requirement on $j$ is equivalent to $j \equiv -1$ or $ 0 \mod p_i$ for all prime powers $p_i|p$ (note this proves the conjecture for prime $p$ after giving a split for $3p-1$ ($p$ odd) like here)

  • Said study of “fitting” a set into a given tuple of integers $(d_1,…,d_n)$ (ie finding a partition with $\sum A_i = d_i$) Here the sets of the form $\{1,…,n\}$ are of a special importance for proving things about splittability

  • Study of splittability for sets $A\subset \mathbb{N} \neq \{1,…,n\}$

  • Study of $s_p$ and/or $\bar{s}_p$, I didn’t look into the number of splits except when a bound just fell out of a proof.