I found a solution in Python for this problem, but do not understand it. The problem is how many ways an integer n can be written as the sum of at least two positive integers. For example, take n = 5. The number 5 can be written as

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Here's a solution for given $n$.

# zero-based array (first index is 0)
ways = [1, 0, ..., 0] (n zeroes)

for i in 1, ..., n-1:
    for j in i, ..., n:
        ways[j] = ways[j] + ways[j-i]

print ways[n]

This solution is elegant and efficient, but unfortunately, I do not understand the logic. Can someone please explain the logic of this solution to the problem? Is there a way to make this algorithm easy to understand?


1 Answer 1


Let us denote the array ways after $t$ iterations of the outer loop by $w_t$. The recurrence implemented by the code is $$ w_0(n) = \begin{cases} 1 & \text{if } n = 0, \\ 0 & \text{if } n > 0. \end{cases} \\ w_t(n) = \begin{cases} w_{t-1}(n) & \text{if } n < t, \\ w_{t-1}(n) + w_t(n-t) & \text{if } n \geq t. \end{cases} $$ You can prove by induction that $w_t(n)$ is the number of representations of $n$ as a sum of natural numbers between $1$ and $t$ (without regard to order). (This is also the number of representations of $n$ as a sum of at most $t$ natural numbers.)

The code returns $w_{n-1}(n)$, which is the number of representations of $n$ as an arbitrary sum of natural numbers, other than the representation $n$.

As an aside, if you allow the trivial representation then you get the partition function. Using Rademacher's asymptotic formula, the partition function can be computed in time $\tilde O(\sqrt{n})$, much faster than your $\Theta(n^2)$ algorithm.

  • $\begingroup$ "This is also the number of representations of $n$ as a sum of at most $t$ natural numbers" Is this intuitively equivalent to the number of partitions of $n$ to numbers at most $t$ (the statement to prove with induction)? I don't quite see the relation between both statements. $\endgroup$ Dec 26, 2019 at 2:51
  • 1
    $\begingroup$ Conjugation moves you from one to the other. Look it up. $\endgroup$ Dec 26, 2019 at 7:44
  • $\begingroup$ I was able to prove the statement by proving that the number representations of $n$ as a sum of exactly $t$ numbers is equal to the number of representations of $n-t$ as a sum of at most $t$ numbers. $\endgroup$ Dec 26, 2019 at 15:53
  • 1
    $\begingroup$ See here: en.wikipedia.org/wiki/…. $\endgroup$ Dec 26, 2019 at 15:56
  • $\begingroup$ However, I couldn't find resources about the conjugation you mentioned above (there were many different "kinds" of conjugation in wikipedia and I didn't know which one did you mean) $\endgroup$ Dec 26, 2019 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.