Euler Problem 76 asks:

It is possible to write five as a sum in exactly six different ways:

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1How many different ways can one hundred be written as a sum of at least two positive integers?

This is a Euler Partition problem, one of at least 4 in the problem set (Nos. 31, 77, and 78 are also.) I didn’t now that when I solved #31. I came across Euler partitions as a hint to solving problem #76.

Two things I’ve learned about Project Euler:

- If Leonhard Euler was involved with it, Project Euler is involved with it, and
- There’s probably a PhD in a mathematics department somewhere that has a monograph on the topic

Problem 76 is right out of that playbook. The paper *Playing with Partitions on the Computer* from the mathematics server of Temple University is exactly on point. In fact, if you catch the hint in the document, the answer is right there in the back. No computer required. The authors provide a Section 4, *A Basic Program to Generate Partitions*.

This is my VBA translation of the authors’ algorithms. The number of partitions for zero, *P(0),* is defined as 1, there being only one way to take zero, and the number of partitions for any negative number is zero, so when the indexing reaches for a negative partition, we can stop the loop. The partitions for later numbers grow from the partitions of earlier numbers by pentagonal numbers (as F below). That’s what Euler discovered. It’s covered in the reference.

The code names that tune in “zero” notes, err seconds, per the timer.

Dim P(0 To 100) As Long

Dim N As Long

Dim K As Long, F As Long

Dim Sign As Long

Dim Answer As Long, T As Single

T = Timer

P(0) = 1 ‘ defined

For N = 1 To 100

Sign = 1

P(N) = 0

For K = 1 To 100

F = K * (3 * K – 1) / 2

If F > N Then Exit For ‘ P(N-F) = 0

P(N) = P(N) + Sign * P(N – F)

F = K * (3 * K + 1) / 2

If F > N Then Exit For ‘ P(N-F) = 0

P(N) = P(N) + Sign * P(N – F)

Sign = -Sign

Next K

Next N

Answer = P(100) – 1

Debug.Print Answer; ” Time:”; Timer – T

End Sub

The usual angle brackets substitutions are in the above. This code, slightly modified, will directly solve #78. You’ll need to make the partition reachback (K) bigger, and look for a different kind of endpoint. The number of partitions corresponding to the answer of #78 is a 257 digit number.

Euler partitions occasionally make the news. They’ll explain them better than I can, for sure.

Now, what I can’t figure out is what to change when the increments are prime numbers (as in #77), rather than unitary. I’d think it should be N, or the Loop step, but I haven’t got it yet.

…mrt

Euler was a genius.

I think we used the same reference, Michael. Your code is more concise and readable than mine, so I’m not going to embarrass myself by posting mine. I’m interested in seeing how that code can be adapted to solving #77 with prime numbers.

In the comment thread for Euler Problem 124, we had a discussion about how Problem #77 (prime partition) seemed similar to Problem #31 (investigating the number of ways to make change). Michael posted a very nice recursive solution to #31, which I’ve managed to adapt to work with prime numbers for #77. Here’s the code with the usual angle bracket adjustments.

‘This is based on a solution to #31 found in the PE forums

Dim MaxNum As Long, StartTime As Single

StartTime = Timer

MaxNum = 1

Do

MaxNum = MaxNum + 1

ArrayOfPrimesCounter = 0

Call GetListOfPrimes(MaxNum)

Loop Until findposs(MaxNum, 1) &GT 5000

Debug.Print MaxNum, Timer – StartTime

End Sub

Function findposs(money As Long, maxcoin As Long) As Long

Dim sum As Long, i As Long

sum = 0

For i = maxcoin To ArrayOfPrimesCounter

If money – ArrayOfPrimes(i) = 0 Then sum = sum + 1

If money – ArrayOfPrimes(i) &GT 0 Then sum = sum + findposs(money – ArrayOfPrimes(i), i)

Next i

findposs = sum

End Function

My routines for finding / listing prime numbers are not shown here, but ArrayOfPrimesCounter is the number of primes less than or equal to the limit, and they are stored in the array ArrayOfPrimes (1-based). It would be more efficient if I didn’t get a new list of primes every time through the Do loop, but the limit is quite small and the Sieve of Eratosthenes is extremely fast. The added coding time wasn’t worth the slightly decreased execution time. The above code runs in under a second on my machine. I may be getting ahead of myself here, but I wonder if this can be adapted to #249?

-Josh

Hi Josh –

Thank you. It frustrates me when the Euler examples from the forum can really only be deciphered by the author, and in a month, I’d bet he can’t do it.

And now it’s me doing something wrong. My (new) sieve is quick enough. With a limit of 50 million, it found and counted 3 million primes in 17 seconds (problem 187). It does the ones here in a blink.

However, the recursion following your example takes 6 seconds. Don’t know why.

…mrt

Hi Michael,

I share your frustrations with the forums. Being neither a mathematician nor a real computer programmer, my eyes tend to glaze over when reading some solutions. But every once in a while someone points you to Euler’s Partition Function and you wonder how your life was ever complete before.

I’m consistently getting 0.6 – 0.7 seconds. It’s strange that it’s taking you much longer, since our timings on other problems are pretty similar. I use Longs for the primes array. I think my sieve is a bit faster than yours, but the limit is so low that it shouldn’t matter. Could the recursive part be slowing you down? I use XL2007. One option would be to add a second timer in the Main sub to cumulatively time all of the calls to the GetPrimes or findposs. This way you could at least see where the slowdown is. I’m curious to see the problem.

-Josh

Hi Josh –

The recursion is definitely the problem. Timers around the other steps are zero. I put a global variable inside findposs that’s incremented by 1 every call. findposs is called 1207704 times!

Whoa! and other words that start with W

…mrt

That W word stands for “I should know better” I wasn’t re-initializing the variable, and it just accumulated until I did a reset.

Now it’s only is called 603,852 times ;-) Half the above, but repeatable.

…mrt

Michael,

I was just composing a reply, telling you that my counter showed exactly half of your value, when I decided to refresh the page. I see you’ve gotten there already. Is your solution is still taking 6 seconds?

-Josh

Good morning, Josh –

I think I’m as stripped as I can get. I essentially have a parallel structure to yours. Takes 3.4 seconds, 604K trips.

About the best I can do I think.

…mrt

And good morning to you Michael,

If you like, you can post / email me your code and I can try it out to see if the time discrepancy is related to different versions or some such. Or, you can move on.

-Josh

Hi Josh – FWIW

Sub Euler77()

Dim MaxNum As Long, T As Single

Dim Prime() As Boolean

T = Timer

Num = 0

If PrimeCol.Count 0 Then

Do

PrimeCol.Remove (PrimeCol.Count)

Loop Until PrimeCol.Count = 0

End If

MaxNum = 1

Do

MaxNum = MaxNum + 1

ReDim Prime(1 To MaxNum) As Boolean

Sift Sieve:=Prime

If Prime(MaxNum) Then PrimeCol.Add Item:=MaxNum, Key:=CStr(MaxNum)

Loop Until findsum(MaxNum, 1) > 5000

Debug.Print MaxNum, Timer – T, Num

End Sub

Function findsum(money As Long, maxcoin As Long) As Long

Dim sum As Long, i As Long

Num = Num + 1

sum = 0

If maxcoin = PrimeCol.Count Then

findsum = 1

Exit Function

End If

For i = maxcoin To PrimeCol.Count

If money – PrimeCol(i) = 0 Then sum = sum + 1

If money – PrimeCol(i) > 0 Then sum = sum + findsum(money – PrimeCol(i), i)

Next i

findsum = sum

End Function

Function Sift(ByRef Sieve As Variant) As Variant

‘Sets Sieve(N) TRUE if prime

Dim Limit As Long, BreakPT As Long

Dim N As Long, M As Long, Count As Long

Limit = UBound(Sieve)

BreakPT = Int(Sqr(Limit))

Sieve(1) = False

Sieve(2) = True

For N = 3 To Limit

Sieve(N) = True

If N Mod 2 = 0 Then Sieve(N) = False

Next N

For N = 3 To BreakPT Step 2

If Sieve(N) Then

For M = N * N To Limit Step 2 * N

Sieve(M) = False

Next M

End If

Next N

End Function

…mrt

At the top, it’s

If PrimeCol.Count != to 0 then

…mrt

Hi Michael,

Your code as posted takes about 6 seconds on my machine. I think I found the slowdown though – it’s the collection object. You’re only adding a few numbers to the collection, but by my count you’re extracting a number about 15 million times! For comparison I decided to get a list of the first few primes, store them in a collection, and then time how long it took to extract the same number 15 million times. I then stored the numbers as Longs in an array and timed how long it took to extract the same number 15 million times.

Extract from collection: 3.6 seconds

Extract from array: 0.5 seconds

I modified your code to use an array rather than a collection and consistently got around 1 second. Hope this helps.

-Josh

Josh –

Oh. Haven’t got the hang of it yet. My old code did run in 3.5 seconds. New arrayed code in 1.5. Something eludes my grasp here about ref to arrays. No globals any more.

Dim MaxNum As Long, T As Single, i As Long, j As Long

Dim Item As Long, Key As String, T1 As Single

Dim Prime() As Boolean, PrimeArr(1 To 100) As Long

T = Timer

MaxNum = 1

j = 0

Do

MaxNum = MaxNum + 1

ReDim Prime(1 To MaxNum) As Boolean

Sift Sieve:=Prime

If Prime(MaxNum) Then

j = j + 1

PrimeArr(j) = MaxNum

End If

Loop Until findsum(MaxNum, 1, PrimeArr, j) > 5000

Debug.Print MaxNum, Timer – T

End Sub

Function findsum(money As Long, maxcoin As Long, ByRef PrimeArr As Variant, j As Long) As Long

Dim sum As Long, i As Long

sum = 0

If maxcoin = j Then

findsum = 1

Exit Function

End If

For i = maxcoin To j

If money – PrimeArr(i) = 0 Then sum = sum + 1

If money – PrimeArr(i) > 0 Then sum = sum + findsum(money – PrimeArr(i), i, PrimeArr, j)

Next i

findsum = sum

End Function

Same number of trips. No surprise there. j is the pointer to the last added prime. Was the collection count before.

…mrt

Michael,

Your new code runs in 2.5 seconds for me. You must have a fast machine indeed!

Suggestion: in the findsum function argument list, change the line from

ByRef PrimeArr as Variant

to

ByRef PrimeArr() as Long

Cuts the time to ~0.75 seconds for me.

I try not to use globals much, but I make an exception for the primes array. They get used and passed between procedures so often that it’s easier for me to just let them go everywhere on their own.

-Josh

Hi Josh –

Victory! 0.5625 seconds. Thank you.

Per the System Properties/General: Intel(R) Core(TM)2 Duo CPU E8400 @3.00GHz 1.97GHz, 3.46GB of RAM

It’s my tech refresh hot rod. Now on to the next one.

…mrt

Michael,

Glad to help.

That’s a pretty sweet machine for sure.

What problem are you working on next? This latest collection of partition problems, especially #76, is one of the reasons I love PE. I can often hack my way to a solution, sometimes in Euler time and sometimes not, and then visit the forums and get blown away by something I’ve never heard of before. The flip side of this is that many times it seems that if you don’t know the right algorithm / equation, the problem is nearly impossible to solve. #233 for example seems to fall in this class. It can be really frustrating. I think I’ve found the right approach, but it took quite a while to find it and even longer to understand how to use it. Now, I just need to figure out how to program it…

-Josh

Hi Josh –

I just did 131 exactly that way. Double ugly. Then in the forum found a 4-liner solution once the arrays are populated. Some times I have the math insight, but most often not. For 131 I was sort of half-math ;-)

Not sure what’s next…I sort of do them in difficulty order picking one that I think understand on page 3 when the problems are sorted in ascending order of difficulty.

#205 goes up Saturday. I found an approach that took me from 385 seconds to about 0.6 seconds.

…mrt

Hi Michael,

Can you explain what the line of code in your post on August 05, 2009 at 2:26 pm does?

It is inside your prime sieve.

I have not seen/used this before.

-Tim

Hi Tim –

Prime is an array of Booleans. In the above, it keeps getting Re-Dimmed to a larger array.

Sift() is a functional implementation (it’s above) of the Sieve of Eratosthenes (see http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). It

very quicklyassigns TRUE to the boolean if the index is a prime number. So you can find if a number is prime by “If Prime(n)” returns true. To make this work, you have to have set the boundaries above the n you are interested in.So my “Sift Sieve:=Prime” is a VBA play on words (“sifting the prime sieve” )to create the proper boolean array. Works very well. It can be made faster by being TRUE if a number is NOT PRIME, but I like the logic better this way.

…mrt