Monthly Archives: February 2011

Euler Problem 74

Just iterate, create a list for each, test for replication and increment if 60.

#Euler74
class Algorithms:
    def sumBang(self, strStart):
        sum = 0
        for digit in range(0, len(strStart)):
            bang = 1
            for n in range (2,int(strStart[digit])+1):
                bang *= n
            sum += bang
        return sum
class Problem74:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        count = 0
        for n in range (78, self.limit+1):
            result = 0
            L = [n]
            while result != n:
                if len(L) == 1:
                    result = self.Euler.sumBang(str(n))
                else:
                    result = self.Euler.sumBang(str(result))
                if result in L:
                    L.append(result)
                    break
                else:
                    L.append(result)
            if len(L)-1 == 60:
                count += 1
            if n % 10000 == 0:
                print n, count
        return "Answer:"+str(count)
if __name__ == '__main__':
    P = Problem74(1000000)
    print P.Solution()

Euler Problem 73

Just use brute force to test the GCD for each iteration.

#Euler73
class Algorithms:
    def gcd(self, a, b):
        while b:
            a, b = b, a%b
        return a
class Problem73:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        count = 0
        for n in range(5, self.limit+1):
            for d in range(n/3 + 1, (n-1)/2 + 1):
                if self.Euler.gcd(n,d) == 1:
                    count += 1
            if n % 1000 == 0:
                print n, count
        return "Answer:"+str(count)
if __name__ == '__main__':
    P = Problem73(12000)
    print P.Solution()

Euler Problem 72

Just add up the totient functions between 2 and 10E6.

#Euler72
class Algorithms:
    def totient(self, n):
        result = float(n)
        i = 2
        while i*i <= n:
            if n % i == 0:
                result -= result/i
            while n % i == 0:
                n /= i
            i += 1
        if n > 1:
            result -= result/n
        return result
class Problem72:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        count = 0
        for n in range (2, self.limit+1):
            count += int(self.Euler.totient(n))
            if n % 50000 == 0:
                print n
        return "Answer:"+str(count)
if __name__ == '__main__':
    P = Problem72(1000000)
    print P.Solution()

Euler Problem 71

A lot of simplification and reduction. Not too complicated. Nice and short. Runs fast.

#Euler71
class Problem71:
    def __init__(self, limit):
        self.limit = limit
    def Solution(self):
        min = 0
        min_n = 0
        for n in range (int(min*self.limit), int(self.limit*float(3)/7)):
            f = float(n)/self.limit
            if f < float(3)/7:
                if f > min:
                    min = f
                    min_n = n
        return "Answer:"+str(min_n)
if __name__ == '__main__':
    P = Problem71(1000000)
    print P.Solution()

Euler Problem 70

So I could have kept calculating the totient function directly and left it to run for years. Instead, I googled totient and discovered an interesting little mathematical quirk that would enable me to significantly reduce my testing set.
If a number is a product of two prime numbers …

  • n = p1 * p2

then the totient of that number is …

  • phi (n) = (p1-1) * (p2-1)

The square root of 10E7 is about 3100 plus change. So I calculated all the prime numbers 30% above and below that number. Then tested each of those numbers whereby the products were < 10E7. Smallest n/phi(n) wins. Routine runs in about 5 minutes. By the way, I wrote this routine to leverage (and re-learn Pythonian OOP).

#Euler70
from math import sqrt
class Algorithms:
    def permutate(self, sequence):
        if not sequence:
            return [sequence]
        else:
            set = []
            for k in range(len(sequence)):
                part = sequence[:k] + sequence[k+1:]
                for m in self.permutate(part):
                    set.append(sequence[k:k+1] + m)
            return set 
    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 Problem70:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        primes = self.Euler.primeGen(.7 * sqrt(self.limit), 1.3 * sqrt(self.limit))
        print "Primes:"+str(primes)+"\n"
        i = 0
        minNDivPhi = 10
        minN = 0
        for p1 in primes:
          print "Testing:"+str(p1)
          i += 1
          for p2 in primes[i:]:
            n = p1 * p2
            if n > self.limit:
                break
            phi = (p1-1) * (p2-1)
            nDivPhi = n / float(phi)
            if nDivPhi < minNDivPhi:
                if str(int(n)) in self.Euler.permutate (str(int(phi))):
                    minNDivPhi = nDivPhi
                    minN = n
                    print "n:"+str(n)+" phi:"+str(phi)+" nDivPhi:"+str(nDivPhi)
        return "Value of n where nDivPhi is minimized:"+str(minN)
if __name__ == '__main__':
    P = Problem70(10000000)
    print P.Solution()

Hubble Palette

The Orion Nebula (Messier 42) is one of the most impressive astronomical objects to capture by CCD. Most images of it are captured using the standard RGB palette. Not to be outdone, I’ve attempted to create a stacked image using different wavelength filters, essentially mimicking what’s been dubbed the Hubble palette.

This image was taken using three 120 second exposures on Lightbuckets LB-0003 with the following filters:

  • Hydrogen-Alpha in Green
  • Sodium II in Red
  • Oxygen III in Blue

I used MaximDL to stack, align and screen stretch. Then I used Gimp to add weight to the Red channel, which brings out all the yellows and colour details. Not bad for my first attempt using such a short exposure. MaximDL is awesome!

Euler Problem 69

I tried this first with a GCD function and found it too slow. In fact it would have taken nearly a month to run. So I looked for a more efficient algorithm. Surprisingly, I found this one in Java (ironic isn’t it?) then translated it to Python.

I must admit, working out Euler Problems is a bit easier with Python. I suppose manipulating lists etc. in a higher level scripting language requires less work. Java was a bit too system-level for this kind of work. So this routine is pretty slick. It runs through the entire set in under 90 seconds. Next.

#Euler69
def totient(n):
    result = float(n)
    i = 2
    while i*i <= n:
        if n % i == 0:
            result -= result/i
        while n % i == 0:
            n /= i
        i += 1
    if n > 1:
        result -= result/n
    return result
print "Crunching Phi's\n"
max_n = 0
max_n_div_phi = float(0)
for n in range(2,1000001):
    phi = totient(n)
    n_div_phi = float(n/phi)
    if n_div_phi > max_n_div_phi:
        max_n = n
        max_n_div_phi = n_div_phi
        print "n:"+str(n)+" phi:"+str(phi)+" n/phi:"+str(n_div_phi)
    if n % 100000 == 0:
        print "Testing "+str(n)+"s"
print "\nAnswer: Value of n with max_n_div_phi is "+str(max_n)