This question is motivated by an old math contest problem, and is a generalization of the original problem. I will write out the original problem as motivation.


Let us say that $n$ is $p$-Savage, for a prime $p$, if it is possible to partition $\{1, \cdots, n\}$ into $p$ sets $A\_1, \cdots, A\_{p}$ such that the following holds:


i) $\displaystyle \sum\_{x \in A\_i} x = D$, a constant, for $1 \leq i \leq p$; 


ii) $x \in A\_i$ implies that $x \equiv i-1 \pmod{p-1}$ for $1 \leq i \leq p-1$; and


iii) $x \equiv 0 \pmod{p}, 1 \leq x \leq n$ imply that $x \in A\_p$.


Do there exist $p$-Savage numbers for every prime $p$? If so, can one estimate how many $p$-savage number there are say in $[1, N]$?


This is motivated by an old Canadian math contest problem (Euclid 2003), where the question asks about 3-Savage numbers following the above definition (originally just called savage numbers). It asked in particular to show that 8 is (3-)savage, and that every even savage number $n$ satisfies $n \equiv 8 \pmod{12}$. These questions are fairly simply to answer by doing some simple (but tedious) modular arithmetic. The contest did not ask for any sufficient conditions for $n$ to be savage, nor did it ask for whether the exist infinitely many savage numbers. It also only focused on even savage numbers. One can show by modular arithmetic that if $n$ is an odd savage number, then $n \equiv 11 \pmod{12}$. 35 is an odd savage number. 



A partition problem
The answer is that for large enough $n$, it is a $p$-savage if and only if $p|n+1$ and $(p-1)|\frac{n(n+1)}{2}$.


You must have $p-1|D$ because all elements of $A\_1$ are divisible by $p-1$. And so we must have $p-1|\frac{n(n+1)}{2}=pD$. To show that $p|n+1$ we have to rule out the case $p|n$. This is easily ruled out because
$$p+2p+\cdots+p\cdot\frac{n}{p}=\frac{n(n+p)}{2p}>D.$$


Now if you assume that the divisibility conditions above are satisfied and $n$ is large enough, I claim that you can always find an admissible partition. Start by letting $A\_p=\lbrace p,2p,\dots n-p+1\rbrace$, and distribute the rest among the $A\_i$'s. Then let $f\_i=\sum\_{x\in A\_i}x-D$. It's not hard to check that $f\_i\approx \frac{n}{p(p-1)}$, but then if $f\_i$ is large enough it can be written as a sum of distinct elements from $A\_i$. We collect all such elements from the $A\_i$'s and put them in $A\_p$.


