Monthly Archives: June 2011

Euler Problem 87 – More Primes

I started this one by iterating 50 million times. The code worked but it was damn slow. I figured it would take 27 hours. Not good. Then … lightbulb! Flip the question over by iterating on only the possible primes. Simple, elegant, fast — works in 4 seconds.

#Euler87
import math
class Problem: 
    def primeGen (self, lowerLimit, upperLimit):
            isPrime = [False] + [True]*(upperLimit-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    
    def Solution(self):
        P2 = self.primeGen(2,int(math.exp(.5*math.log(50e6))))
        P3 = self.primeGen(2,int(math.exp(math.log(50e6)/3)))
        P4 = self.primeGen(2,int(math.exp(.25*math.log(50e6))))
        print "Number of Primes for ", "2^:", len(P2), "3^:", len(P3), "4^:", len(P4)
        N = []
        for p2 in P2:
            for p3 in P3:
                for p4 in P4:
                    if p2**2 + p3**3 + p4**4 <= 50e6:
                        N.append(p2**2 + p3**3 + p4**4)
        print "\nAnswer =", len(set(N))
if __name__ == '__main__':
    P = Problem()
    P.Solution()

Euler Problem 102 – Vectors

This one was really interesting because so far, I haven’t seen very many Euler Project problems based on vector algebra. My solution is predicated on the theorem that if a point P is inside triangle ABC, then Area PAB + Area PBC + Area PAC = Area ABC

Visually, you can easily see how this works. This one is inside:

And this one is outside:

And there is a Wikipedia article on triangles that covers area calculations using vectors:

http://en.wikipedia.org/wiki/Triangle#Using_vectors

Note I had to calculate a delta value and test if its below a cut-off value (0.1 in this case). This is due to rounding errors in the math class. I could have played with decimal class precision, but calculating a delta is simple and it works.

import math
class Problem:
    def Area (self, P1, P2, P3):
        V1 = [P1[0]-P2[0],P1[1]-P2[1]]
        V2 = [P1[0]-P3[0],P1[1]-P3[1]]
        return float(.5)*math.sqrt((self.Mag(P1,P2)**2)*(self.Mag(P1,P3)**2)-(self.Dot(V1,V2)**2))
    def Mag (self, V1, V2):
        return math.sqrt(((V2[0]-V1[0])**2)+((V2[1]-V1[1])**2))
    def Dot (self, V1, V2):
        return (V1[0]*V2[0])+(V1[1]*V2[1])
    def Solution(self):
        count = 0
        P = [0,0]
        T = []
        f = open("triangles.txt", "r")
        for row in f.readlines():
            c = row.split(",")
            for i in [0,1,2,3,4,5]:
                c[i] = int(c[i])
            T.append(c)
        f.close()
        for t in T:
            A = [t[0],t[1]]
            B = [t[2],t[3]]
            C = [t[4],t[5]]
            sum = self.Area(P,A,B)+self.Area(P,B,C)+self.Area(P,A,C)
            delta = abs(self.Area(A,B,C)-sum)
            if delta < 0.1:
                count += 1
            print count,A,B,C,sum,self.Area(A,B,C),delta
        print "Answer =", count
if __name__ == '__main__':
    P = Problem()
    P.Solution()

Euler Problem 206 – Don’t be such a square!


Check out the wikipedia article on square numbers (the numbers article, not the algebra one).
A couple few interesting properties emerge that can be exploited.

http://en.wikipedia.org/wiki/Square_number

1) A square number can end only with digits 00,1,4,6,9, or 25 in base 10; So that eliminates 2 digits, we now end with a 9.
2) Squares of odd numbers are odd.
3) If the last digit of a number is 3 or 7, its square ends in 9.

and if, and if, and if … you get the idea.

PS. I could have used the divisible by 4 rule also here, but I didn’t need to. This routine still runs in under a minute without importing psyco.

class Problem:
    def test (self, n):
        N = str(n*n)
        if N[0] == '1':
            if N[2] == '2':
                if N[4] == '3':
                    if N[6] == '4':
                        if N[8] == '5':
                            if N[10] == '6':
                                if N[12] == '7':
                                    if N[14] == '8':
                                        if N[16] == '9':
                                            return True
        return False
    def Solution(self):
        number = 0
        start = int(math.floor(math.sqrt(10203040506070809)))
        end = int(math.floor(math.sqrt(19293949596979899)))
        for i in range (start,end):
            if i % 2 != 0:
                if int(str(i)[-1]) == 3 or int(str(i)[-1]) == 7:
                    if self.test(i) == True:
                        number = int(math.sqrt(int(str(i*i)+"00")))
                        break
        print "Answer =", number
if __name__ == '__main__':
    P = Problem()
    P.Solution()

Euler Problem 85

This one has to do with combinatorics. Here is a page that contain a formula to solve all permutations on a m x n grid.
http://www.gottfriedville.net/mathprob/comb-subrect.html

I used a simple quadratic equation to determine that if one dimension never exceeds 1, then the other cannot exceed 2000 (roughly). So I just created a nested loop for m & n and tested for a smaller and smaller delta.

class Problem:
    def Solution(self):
        mBest = 0
        nBest = 0
        delta = 2000000
        goal = 2000000
        for m in range (1,2001):
            for n in range (1, 2001):
                test = m*(m+1)*n*(n+1)/4
                if abs(test-goal) < delta:
                    mBest = m
                    nBest = n
                    delta = abs(test-goal)
            if m % 100 == 0:
                print m,
        print "\nBest m, Best n, Delta =", mBest, nBest, delta
        print "Answer =", mBest*nBest
if __name__ == '__main__':
    P = Problem()
    P.Solution()

Euler Problem 112

I’m on a roll! Just banging them out. Must be just a series of easy ones. Just iterate over a range, checking each for increasing and decreasing numbers, then increment a counter.

#Euler112
import psyco
psyco.full()

class Problem:
    def isInc (self, num):
        counter = 0
        for c in str(num):
            if int(c) >= counter:
                counter = int(c)
            else:
                return False
        return True
    def isDec (self, num):
        counter = 9
        for c in str(num):
            if int(c) <= counter:
                counter = int(c)
            else:
                return False
        return True
    def Solution(self):
        bouncy = 0
        for i in range (1, 2000000):
            if self.isInc(i) == False and self.isDec(i) == False:
                bouncy += 1
            if float(bouncy)/i == .99:
                break
        print "Answer=", i
if __name__ == '__main__':
    P = Problem()
    P.Solution()

Euler Problem 99

This was another easy one. Using natural logarithms, this routine runs very quickly (< 5 seconds). I also used the decimal class just in case I needed extra precision.

#Euler99
import psyco
psyco.full()

import decimal
class Problem:
    def Solution(self):
        decimal.getcontext().prec = 50      
        P = []
        f = open("base_exp.txt", "r")
        for row in f.readlines():
            newRow = []
            for column in row.split(","):
                newRow.append(int(column))
            P.append(newRow)
        f.close()
        max = 0
        pos = 0
        for pair in P:
            v = decimal.Decimal(pair[1]*decimal.Decimal(pair[0]).ln()).exp()
            if v > max:
                max = v
                pos = P.index(pair)+1
            print P.index(pair)+1,
        return "\nAnswer = " + str(pos)
if __name__ == '__main__':
    P = Problem()
    print P.Solution()

Euler Problem 92

This one takes a while to run, but that’s no surprise since I used brute force. Nothing too complicated, just iterate 10 million time and keep a counter. But if you use psyco, it does speed things up a bit. Roughly 10 mins.

#Euler92
import psyco
psyco.full()

class Problem:
    def digits(self, n):
        sum = 0                
        for c in str(n):
            sum += int(c)*int(c)
        return sum
    def Solution(self):
        count = 0
        for i in range (1, 10000001):
            if i % 100000 == 0:
                print i, count
            num = i
            f1 = 0
            f89 = 0             
            while f89 < 2 and f1 < 2:
                num = self.digits(num)
                if num == 89:
                    f89 += 1
                    if f89 == 2:             
                        count += 1
                        break
                elif num == 1:
                    f1 += 1
                    if f1 == 2:
                        break
        return "Answer = " + str(count)
if __name__ == '__main__':
    P = Problem()
    print P.Solution()