1
$\begingroup$

I have been thinking about this problem for a while but have been unable to formalize a complete answer.

Given an integer $n \geq 3$, how many different sets can you sum the integer elements in the set to equal n ?

Constraints:

1) Each set must contain at least 2 elements.

2) All elements in a set must sum to $n$ (all elements must be greater than 0).

3) Normal set rules apply: No elements in a set can be repeated, and Order doesn't matter

Examples:

when n = 3 the only possible set is {1, 2} so the answer would be 1.

when n = 4 the only possible set is {1, 3} so the answer would be 1.

when n = 5 there are two sets {1, 4}, {2, 3} so the answer would be 2.

This is meant to be a programming question. I think the answer could be computed as a math equation, or at least a dynamic programming approach. My goal is for the run time to not exceed O(n), however O(1) would be great. If you want to provide code python like syntax would be fine.

$\endgroup$
3
  • $\begingroup$ And for $n=6$ you have $\{1,5\},\{2,4\},\{1,2,3\}$ for $3$ $\endgroup$
    – Ross Millikan
    Commented Jan 9, 2018 at 17:40
  • $\begingroup$ As a first step, you can bound the size of your set by finding the least $k$ for which $1+2+\cdots +k >n$ (simple quadratic to solve). $\endgroup$
    – lulu
    Commented Jan 9, 2018 at 17:41
  • $\begingroup$ @lulu Yes I could do something like that, and enumerate all sets with a bounded size, then step down (-1) the bounded size and repeat until a bounded size of 2. However, that method would get very messy and would be very inefficient because I would be wasting time computing the actual sets, when I only want the number of possible sets. $\endgroup$
    – Jake
    Commented Jan 9, 2018 at 17:47

2 Answers 2

Reset to default
2
$\begingroup$

This is one less than OEIS A000009, which begins $1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, 340, 390, 448, 512, 585, 668, 760, 864, 982, 1113, 1260, 1426, 1610, 1816, 2048, 2304, 2590, 2910, 3264, 3658, 4097, 4582, 5120, 5718, 6378$. The one less comes because you prohibit the partition of $n$ into $\{n\}$ which the OEIS sequence allows. No simple formula is given, but one of the asymptotic ones is $$a(n) \approx \exp(\pi\sqrt{n/3})/(4\cdot 3^{1/4}\cdot n^{3/4}) \cdot (1 + (\pi/(48\sqrt3) - (3\sqrt3)/(8\pi))/\sqrt n + (\pi^2/13824 - 5/128 - 45/(128\pi^2))/n)$$

$\endgroup$
8
  • $\begingroup$ Lets say n had an upper bound of 200. Would the equation be able to handle that as a floor or a ceiling for all integers between 3 <= n <= 200? $\endgroup$
    – Jake
    Commented Jan 9, 2018 at 17:51
  • $\begingroup$ Could you also explain the "one less" comment in more detail? $\endgroup$
    – Jake
    Commented Jan 9, 2018 at 17:52
  • 1
    $\begingroup$ For $6$ they also count $\{6\}$, getting four choices. You don't count that, so get $3$. The first $1$ in the sequence corresponds to $n=0$ and the $4$ corresponds to $n=6$. $\endgroup$
    – Ross Millikan
    Commented Jan 9, 2018 at 18:13
  • $\begingroup$ I see, the only thing I don't understand now is how to compute the next number in the sequence. $\endgroup$
    – Jake
    Commented Jan 9, 2018 at 19:34
  • $\begingroup$ I tried the approximation but it was severely off . $\endgroup$
    – Jake
    Commented Jan 10, 2018 at 0:52
-1
$\begingroup$

Let $N_i(n)$ give the number sets of size $i$. You want $\sum_{i=2}^\infty N_i(n)$.

Clearly $N_2(n) = \lfloor\frac{n-1}{2}\rfloor$.

To compute $N_3(n)$, we're going to try to find the three-member set from least to greatest. If the least member is a $1$, then the other members are all at least $2$; we can subtract $1$ from the other $2$ members, and we need two unequal numbers adding to $n-3$; there are $N_2(n-3)$ such possibilities. Similarly, if the least member is $2$, there are $N_2(n-6)$ possibilities; etc. So $N_3(n) = \sum_{i=1}^{\lfloor\frac{n}{3}\rfloor} N_2(n-3i)$.

Similarly, $N_4(n) = \sum_{i=1}^{\lfloor\frac{n}{4}\rfloor} N_3(n-4i)$

You can try to devise some computation method based on these relations; however, I'm not sure it will be so computationally efficient.

$\endgroup$
1
  • $\begingroup$ Better/not worse/amounts to the same is to recursively create a table for $S(n,k)$ the number of subsets $\subset \mathbb N_{\leq k}$ with sum $n$. For the recursion, distinguish according to the largest element. «Dynamic programming» to use a fancy word. $\endgroup$
    – Bart Michels
    Commented Jan 10, 2018 at 19:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .