Question:

Here is how <a href="http://projecteuler.net/index.php?section=problems&id=76" rel="nofollow" title="original problem description">Project Euler Problem #76</a> sounds like: "How many different ways can one hundred be written as a sum of at least two positive integers?"

I've struggled to get it right for a couple of days, tried to solve in different ways and got mostly the same results for small numbers (those that are easy to check). I ended up with an algorithm that lists all partitions for a given number in alphabetical order, descending (starting from "N-1 + 1"). Written in VB.NET:

```
Dim ub As Integer = 6
Dim wayCount As Integer = 0
For n = ub - 1 To 1 Step -1
'init value array (first combination)
Dim s As New List(Of Integer)
For m = 1 To ub \ n : s.Add(n) : Next
Dim b As Integer = ub Mod n
If b <> 0 Then s.Add(b)
'from where to start decrementing
Dim k As Integer = s.Count - 1
While k > 0 And s(k) = 1 : k -= 1 : End While
Do
wayCount += 1 : Console.WriteLine(String.Join(" + ", s) & " = " & s.Sum)
If s(k) = 1 Then k -= 1
If k = -1 Then Exit Do
s(k) -= 1
s.Add(1)
Loop While k >= 1
Next
Console.WriteLine("count=" & wayCount)
```

The code works for numbers 1-6 inclusive and starts failing for N=7, with 1 combination missed. For N=8 it misses 2 (19 instead of 21). For N=100 the answer is 4576, which is several orders of magnitude less than required. Clearly, I am missing some very important detail.

If you don't have time or means to compile and run the above code, here is the output (N=7):

```
6 + 1 = 7
5 + 2 = 7
5 + 1 + 1 = 7
4 + 3 = 7
4 + 2 + 1 = 7
4 + 1 + 1 + 1 = 7
3 + 3 + 1 = 7
3 + 2 + 1 + 1 = 7
3 + 1 + 1 + 1 + 1 = 7
2 + 2 + 2 + 1 = 7
2 + 2 + 1 + 1 + 1 = 7
2 + 1 + 1 + 1 + 1 + 1 = 7
1 + 1 + 1 + 1 + 1 + 1 + 1 = 7
count=13
```

I've studied these links:

<a href="https://stackoverflow.com/questions/438540/projecteuler-sum-combinations" rel="nofollow">(ProjectEuler) Sum Combinations</a> - provides a mathematical solution, which does not list all combinations

<a href="https://stackoverflow.com/questions/400794/generating-the-partitions-of-a-number" rel="nofollow">Generating the partitions of a number</a> - is in python, which I cannot read/run/understand.

Any help would be much appreciated, thanks in advance!

Answer1:You say, "The code works for numbers 1-6 inclusive and starts failing for N=7, with 1 combination missed." You should step through your code one line at a time for N=7, either in a debugger or by hand. By seeing in detail exactly what your code is doing you will be able to see where it misses a combination.

Answer2:There is a fairly accurate closed-form solution to this problem, believe it or not.

Hardy and Ramanujan's formula:

```
e^(PI sqrt(2n/3))
p(n) ~ -----------------
4n sqrt(3)
```

which gets closer as n->infinity. The mathematician Rademacher made an exact formula, but it isn't pretty. <a href="http://users.math.yale.edu/~alf8/Folsom-Masri-MathAnn07-10.pdf" rel="nofollow">Here's a discussion.</a>

I would recommend reading about it on Wikipedia and Mathworld <a href="http://mathworld.wolfram.com/PartitionFunctionP.html" rel="nofollow">here</a> and <a href="http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Partition_function" rel="nofollow">here</a>.

<a href="https://mathoverflow.net/questions/47611/exact-formulas-for-the-partition-function" rel="nofollow">This</a> is the MathOverflow discussion of the problem.

I'm not saying these are the best solutions to this problem. In fact for reasonably small values of n they're a waste of time, but it is interesting to see this solution as well as the more "computer-oriented" ones.

Answer3:As promised, here is some code that does partitioning of N (stored in ub) using natural numbers up to N, but not including it. With slight modification, it should be able to partition by any function, including that with floating point output.

Basic idea is that for every value used in partitioning we are using coefficient bucket, which is a multiplier of that value. On every step we either charge the value to maximum available, move left or right, decrement current multiplier and test if we get to the sum. Once sum was successfully partitioned, wayCount is incremented and result is printed to the screen.

This might be a somewhat dirty implementation, but it works in a reasonable time even for the scope of the problem in question (under 5 minutes on my machine), generating several millions of partitions per second. Healthy criticism is always welcome!

```
Dim ub As Integer = 10
Dim availableIncrements(ub - 2) As Integer
Dim weightCoefficients(ub - 2) As Integer
For i = 0 To ub - 2
availableIncrements(i) = ub - i - 1
weightCoefficients(i) = -1 'indicates that enumeration has not started yet
Next
Dim wayCount As Integer = 0
Dim pos, sum As Integer
pos = 0 : sum = 0
Do
If weightCoefficients(pos) = -1 Then
'when we came here first, charge coefficient to maximum available
weightCoefficients(pos) = (ub - sum) \ availableIncrements(pos)
ElseIf weightCoefficients(pos) > 0 Then
'regular cycle: decrease by one
weightCoefficients(pos) -= 1
Else
'return to previous bucket
If pos = 0 Then Exit Do
pos -= 1
Continue Do
End If
'calculate current sum
sum = 0
For k = 0 To pos
sum += availableIncrements(k) * weightCoefficients(k)
Next
'found combination
If sum = ub And weightCoefficients(pos) > 0 Then
wayCount += 1
'printing to screen, remove when expecting many combinations
Dim printList As New List(Of Integer)
For i = 0 To pos 'which number to print
For k = 1 To weightCoefficients(i) 'how many times to print a number
printList.Add(availableIncrements(i))
Next
Next
Console.WriteLine(String.Join(" + ", printList))
'if we were in the last bucket and we just partitioned the number,
'no need to go down and check all lower coefficients, instead move one column back.
If pos = UBound(availableIncrements) Then
pos -= 1
Continue Do
End If
End If
If pos < UBound(availableIncrements) Then
pos += 1
weightCoefficients(pos) = -1 'prepare to charge
End If
'this is something to keep you busy (so you know it's not hanging)
'uncomment for long enumerations
'If wayCount Mod 100000 = 0 Then Console.WriteLine(wayCount)
Loop
Console.WriteLine("count=" & wayCount)
```