Monthly Archives: March 2011

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

Happy Pi Day!

Just so everyone knows the difference between Pi day and Pi Approximation Day. Its an easy thing to confuse. 🙂
 
Pi Day is observed on March 14 because of the date’s representation as 3/14 in month/day date format. This representation adheres to the commonly used approximation of 3.14 for pi. Whereas the fractional approximation of pi (or 22⁄7) resembles the date July 22 in the day/month format. So Pi Approximation Day is therefore celebrated on July 22.
 

Bright Spiral

Messier 99 is easily visible this time of year, situated in constellation Coma Berenices. It was one of the first objects to be identified as a spiral.

I used Lightbuckets and a standard RGB filter with a 60 second exposure for each. Imported into Maxim for stacking and screen stretching. Not as nice as I would have hoped. Maybe I just missed something in Maxim.