# 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 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-P2,P1-P2] V2 = [P1-P3,P1-P3] 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-V1)**2)+((V2-V1)**2)) def Dot (self, V1, V2): return (V1*V2)+(V1*V2) 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,t] B = [t,t] C = [t,t] 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 == '1': if N == '2': if N == '3': if N == '4': if N == '5': if N == '6': if N == '7': if N == '8': if N == '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
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*decimal.Decimal(pair).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()
```