Integer partitions with subset sums "not divisible" by p

Question

I have the following questions: Let $N \in \mathbb{N}$ and \begin{equation} \sum_{i=1}^k n_i = N, \end{equation} with $n_i \in \mathbb{N}$ for $1 \le i \le k$ and some $k \in \mathbb{N}$, be an integer partition of $N$, such that $n_i \le p$ and for all non-empty subsets $I \subset \{1,\ldots,k\}$ we either have \begin{equation} \sum_{i \in I} n_i \notin p \mathbb{N} \end{equation} or \begin{equation} n_i = p, \;\;\;\;\;\;\;\; \forall i \in I. \end{equation} (I.e., in words, any subset sum is not a multiple of $p$ except it consists of the number $p$ only). How can I generate these partitions efficiently? Is there a closed expression for the number of such partitions?

For example, for $N=16$ and $p = 5$ I count the following 5 partitions: \begin{equation} \begin{split} 5+5+5+1 &= 16, \\ 5+5+4+2 &= 16, \\ 5+5+3+3 &= 16, \\ 5+4+4+3 &= 16, \\ 4+4+4+4 &= 16. \\ \end{split} \end{equation}

Answer 1

I do not know the literature on this problem. Hopefully someone here can provide a reference. Erdos, Turan, and others considered various problems related to your problem. Here is one result that shows k is less than p.

Take some sequence b_i of positive integers and look at s_j, the sum of the first j integers. When s_k - s_j is a multiple of p, then there is a subsum which is a multiple of p. To avoid this, all the s_j must be distinct and nonzero mod p. But then there have to be fewer than p of the s_j. So k is less than p.

I suspect dynamic programming is going to help here. Note that if j is a number in the partition, then p-j cannot be a member of the same partition. So start by creating a structure which is a bag of numbers, followed by a list of permitted elements allowed to be added to the bag, as well as a list of sums mod p. For each bag, and for each permitted element, make a new bag which has the contents of the old bag, and the new element, and compute the superset of sums mod p and use this to trim the permitted list of elements to add. In practice, most bags will not grow beyond sqrt(p) in size, and the number of distinct elements will often be below log p in size. For p less than 100, this should be a feasible computation. Use the information to guide your partition generation.

Gerhard "Is Talkin' 'Bout Our Generation" Paseman, 2018.07.19.