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 = [1]
        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()

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s