# Euler Problem 78

Another variant of the previous two problems, but the trick is knowing that partition theory is related to generalised pentagonal number generation. So I just found a generator and modified it for my needs.

```#Euler78
class Algorithms:
def pentGen(self, num):
pentagonal = lambda n : n*(3*n-1)/2
def generalised_pentagonal(n):
if n < 0:
return 0
if n % 2 == 0:
return pentagonal(n/2+1)
else:
return pentagonal(-(n/2+1))
pt = 
for n in range (1, num+1):
r = 0
f = -1
i = 0
while 1:
k = generalised_pentagonal(i)
if k > n:
break
if i % 2 == 0:
f = -f
r += f*pt[n - k]
i += 1
pt.append(r)
if r % 1000000 == 0:
return n
if n % 10000 == 0:
print n
class Problem78:
def __init__(self, stop):
self.stop = stop
self.Euler = Algorithms()
def Solution(self):
n = self.Euler.pentGen(self.stop)
return "Answer = " + str(n)
if __name__ == '__main__':
P = Problem78(60000)
print P.Solution()
```

# Euler Problem 77

So this one is simply a variant of the previous problem, but with the additional of a prime number filter. Its necessary to work backwards until you have a count that closest to 5000, without going under.

```#Euler77
class Algorithms:
def partitionsGen(self, n):
ms = {n: 1}
keys = [n]
yield ms
while keys != :
if keys[-1] == 1:
del keys[-1]
reuse = ms.pop(1)
else:
reuse = 0
i = keys[-1]
newcount = ms[i] = ms[i] - 1
reuse += i
if newcount == 0:
del keys[-1], ms[i]
i -= 1
q, r = divmod(reuse, i)
ms[i] = q
keys.append(i)
if r:
ms[r] = 1
keys.append(r)
yield ms
def primeGen (self, lowerLimit, upperLimit):
isPrime = [False, True]
i = 2
while i < upperLimit:
isPrime.append(True)
i += 1
p = 2
while p * p < upperLimit:
if isPrime[p] == True:
m = p * p
while m < upperLimit:
if m % p == 0:
isPrime[m] = False
m += p
p += 1
P = []
count = 0
for p in isPrime:
if p and count >= lowerLimit :
P.append(count)
count += 1
return P
class Problem77:
def __init__(self, limit):
self.limit = limit
self.Euler = Algorithms()
def Solution(self):
Primes = self.Euler.primeGen(2,self.limit+1)
print Primes
while answer == 0:
count = 0
print "Prime Partitioning "+str(self.limit)
for part in self.Euler.partitionsGen(self.limit):
flag = True
for n in part:
if n not in Primes:
flag = False
if flag == True:
count += 1
print "Count = "+str(count)
if count < 5000:
answer = self.limit + 1
self.limit -= 1
if __name__ == '__main__':
P = Problem77(73)
print P.Solution()
```

# Euler Problem 76

This problem is all about partitions. So I found a fast integer partitions generator. Well, its not fast enough but it does the trick. This routine still takes a while to run.

```#Euler76
class Algorithms:
def partitionsGen(self, n):
ms = {n: 1}
keys = [n]
yield ms
while keys != :
if keys[-1] == 1:
del keys[-1]
reuse = ms.pop(1)
else:
reuse = 0
i = keys[-1]
newcount = ms[i] = ms[i] - 1
reuse += i
if newcount == 0:
del keys[-1], ms[i]
i -= 1
q, r = divmod(reuse, i)
ms[i] = q
keys.append(i)
if r:
ms[r] = 1
keys.append(r)
yield ms
class Problem76:
def __init__(self, limit):
self.limit = limit
self.Euler = Algorithms()
def Solution(self):
count = 0
print "Partitioning "+str(self.limit)
for p in self.Euler.partitionsGen(self.limit):
count += 1
if count % 200000 == 0:
print count
return "Answer = "+str(count-1)
if __name__ == '__main__':
P = Problem76(100)
print P.Solution()
```