Holy crap, that’s fast! Just re-ran the previous routine using PyPy. Ran in 40 seconds instead of 10 mins! Giddy-Up!

# Monthly Archives: October 2012

# Euler 221 – Alexandrian Numbers

When I came upon this Euler problem, and saw it was based on my namesake, I couldn’t help going for it. As with many of the Project Euler problems, the trick is to find a technique that reduces the brute force solution into something more efficient.

```
```

```
The functions from the original problem can be re-written to:
A = p(p + d)((p^2 + 1)/d + p)
```

The Alexandrian numbers are calculated from the new function, where d runs over divisors of p^2+1 and p runs over all positive integers. Used a fast Divisor routine that I Googled, then started building a Set (which is speed optimized to avoid duplicates) until length is 15K. Convert to a List, then sort and display 150,000th number. Numbers 1 thru 6 also listed to verify computation working. Runs in about 10 mins on my quad core iMac.

```
```

```
# e221.py
from math import sqrt
from functools import reduce
def appendEs2Sequences(sequences, es):
result = []
if not sequences:
for e in es:
result.append([e])
else:
for e in es:
result += [seq + [e] for seq in sequences]
return result
def primefactors(n):
i = 2
while i <= sqrt(n):
if n % i == 0:
l = primefactors(n // i)
l.append(i)
return l
i += 1
return [n]
def factorGenerator(n):
p = primefactors(n)
factors = {}
for p1 in p:
try:
factors[p1] += 1
except KeyError:
factors[p1] = 1
return factors
def divisors(n):
factors = factorGenerator(n)
divisors = []
listexponents = [list(map(lambda x:k ** x, list(range(0, factors[k] + 1)))) for k in factors.keys()]
listfactors = reduce(appendEs2Sequences, listexponents, [])
for f in listfactors:
divisors.append(reduce(lambda x, y: x * y, f, 1))
divisors.sort()
return divisors
if __name__ == "__main__":
A = set()
p = 1
while len(A) <= 1500001:
for d in divisors((p * p) + 1):
A.add(int(p * (p + d) * (p + ((p * p) + 1) / d)))
p += 1
L = list(A)
L.sort()
for i in [1,2,3,4,5,6,150000]:
print (str(i) + ": " + str(L[i-1]))
```

# Euler 113 – Bouncy Numbers

This one has to do with combinatorics and we use the good old fashion binomial coefficient identity (built from factorials or Bang!). Any increasing number can be represented using binary strings. For example, all 3-digit increasing numbers using 0, 1, 2 can be represented with 5-digit binary numbers:

```
```

```
11100 = 000
11010 = 001
11001 = 002
10110 = 011
10101 = 012
10011 = 022
01110 = 111
01101 = 112
01011 = 122
00111 = 222
```

Which means that there are (5 choose 3) - 1 = 9 of these numbers. The reason for subtracting 1 is that we don’t want to count the number “000”. By extension, all 3-digit increasing numbers with the digits 0-9 requires a binary string containing 3 ones and 9 zeroes and so on. The same can be extended to 10^100.

For decreasing numbers, the only difference is that we might have a zero in the front and end of the string. Note the following pattern of zeros.

```
```

```
111000 = 000
110100 = 002
110010 = 001
110001 = 000 *
101100 = 022
101010 = 021
101001 = 020
100110 = 011
100101 = 010
100011 = 000 *
011100 = 222
011010 = 221
011001 = 220
010110 = 211
010101 = 210
010011 = 200
001110 = 111
001101 = 110
001011 = 100
000111 = 000 *
```

You can see for 3-digit numbers that “000” will be repeated 3 times after the initial time. For an n-digit number the pattern repeats n times. This gives us (n+10 choose 10) -1 -n. Additionally, numbers like 222 and 11 have both properties. Since we have counted them twice, they need to be removed. There are 9*100 of these numbers which are counted twice.

Here's the Python code. Its pretty short since we've simplified everything down to a couple binomial calculations.

```
```

```
def bang (x):
return x > 1 and x * bang (x - 1) or 1
def choose (n, k):
return bang (n) / (bang (k) * bang (n-k))
if __name__ == "__main__":
print (int (choose (110, 10) + choose (109, 9) - 1002))
```

# Euler 107 – Back to Python

Haskell has a lot going for it. It is brilliantly conceived to ensure functional programming paradigm purity, has hardly any squiggly brackets and most importantly, no freaking semi-colons on every single freaking line. But I digress. I’ve found that package and module management is spotty at best, with Cabal choking regularly. There’s no decent IDE, although I’ve been able to find loads of text editors that can run GHCi in a console. I did finally manage to wrap my brain around functional programming concepts, but interestingly I found that I was spending too much time thinking about how to write it, rather than actually writing. So back to Python. Its might be slow, but its still the best all round language.

Euler problem 107 piqued my interest immediately due to the practical application. Minimum Spanning Tree (MST) routing problems are a cornerstone of networking theory. This solution employs a simple implementation of Kruskal’s algorithm. Also used a very handy Disjointed Set class.

```
# e107.py
from operator import itemgetter
class DisjointSet (dict):
def add(self, item):
self[item] = item
def find(self, item):
parent = self[item]
while self[parent] != parent:
parent = self[parent]
self[item] = parent
return parent
def union(self, item1, item2):
self[item2] = self[item1]
def kruskal (nodes, edges):
forest = DisjointSet ()
mst = []
for n in nodes:
forest.add (n)
sz = len(nodes)-1
for e in sorted (edges, key = itemgetter(2)):
n1, n2, _ = e
t1 = forest.find (n1)
t2 = forest.find (n2)
if t1 != t2:
mst.append (e)
sz -= 1
if sz == 0:
return mst
forest.union (t1, t2)
def convert2Edges (m):
e = []
for i in range (1, len(m)):
for j in range (0,i):
if m[i][j] != 0:
e.append ([str(i), str(j), m[i][j]])
return e
def generateNodes (m):
n = []
for i in range(0, len(m)):
n.append(str(i))
return n
def calcWeight(e):
w = 0
for i in e:
w += i[2]
return w
def generateMatrix ():
m = []
f = open ("network.txt", "r")
for line in f.read().split ('\n'):
m.append (line.split (","))
f.close()
num = len(m)
for i in range (0, num-1):
for j in range (0, num-1):
if m[i][j] == '-' or m[i][j] == '-\r':
m[i][j] = '0'
m[i][j] = int (m[i][j])
m.pop()
return m
if __name__=="__main__":
m = generateMatrix()
e = convert2Edges (m)
n = generateNodes (m)
e1 = kruskal (n,e)
w1 = calcWeight (e)
w2 = calcWeight (e1)
print ("Original weight: " + str (w1))
print ("New weight: " + str (w2))
print ("Difference: "+ str (w1-w2))
```

Sweet! Just found out that Python supports list comprehensions — sort of. Definitely the most useful part of Haskell’s functional syntax. As an example, the weight function can be lightened down to (pun intended):

```
def calcWeight (e): return sum ([x[2] for x in e])
```

Pretty cool to use for the simple stuff.