Month: August 2009

Euler Problem 76

Posted on by Michael

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 + 1

How 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:

  1. If Leonhard Euler was involved with it, Project Euler is involved with it, and
  2. 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.

Sub Problem_076()
 
   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