1
$\begingroup$

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}

$\endgroup$
  • 1
    $\begingroup$ By the pigeonhole principle, there are at most $k-1$ non-$k$ numbers in the partition. This may make the generation of the partitions easier when $k$ is small. $\endgroup$ – Bullet51 Jul 18 '18 at 15:10
  • 1
    $\begingroup$ What does OEIS say? $\endgroup$ – Per Alexandersson Jul 18 '18 at 21:01
  • 1
    $\begingroup$ Als the sum over the empty subset (which is zero) is allowed to be divisible by k $\endgroup$ – Jan-Willem van Ittersum Jul 19 '18 at 8:53
  • 1
    $\begingroup$ I get a bit confused. Is the number $k$ denoting the number of parts equal to the divisor $k$? In your example the first is 4 and the latter 5. Moreover, shouldn't 7 + 5 + 2 + 2 = 16 be another example? $\endgroup$ – Jan-Willem van Ittersum Jul 19 '18 at 9:08
  • 1
    $\begingroup$ For computational purposes, it might be better to do the complementary problem (partition kp-N into at most k pieces each of size less than p) and use some technique like the one I mentioned to prune partitions. This is a much smaller problem if N/kp is close to 1. Gerhard "More Ways To Trim Problem" Paseman, 2018.07.19. $\endgroup$ – Gerhard Paseman Jul 19 '18 at 17:36
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The problem is potentially combinatorially explosive. To ease into it, you might consider generating those partitions with 1 distinct non p number, followed by 2 distinct, 3, and so on. Gerhard "Eat Mountain In Small Bites" Paseman, 2018.07.19. $\endgroup$ – Gerhard Paseman Jul 19 '18 at 16:04

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.