Tag Archives: partitions

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

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 != [1]:
            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):
        answer = 0
        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
        return "Answer = " + str(answer)
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 != [1]:
            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()