Problem

Consider all integer combinations of $ab$ for $2\le a\le 5$ and $2\le b\le 5$:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by $ab$ for $2\le a\le 100$ and $2\le b\le 100$?

Solution in Python

Update: After a conversation with my friend and co-worker Larry, I’ve changed just two lines of this code – using a Python set instead of a list. That has taken the runtime down considerably. The set version runs in about 2% the time of the list version. This is because checking if an element is in a set is a constant time operation, while checking membership in a list is a linear time operation.

This is one of those problems that can be over-engineered. If you simply code the basic happy-path Python version, you find that it runs very quickly and returns the result. You could consider unique factorizations and so on … and that was my initial idea, but coding the “brute-force” Python version is all you really need here.

#!/usr/bin/python
 
import time
 
# L = [] # old version with a list
L = set() # new version with a set
 
limit = 101
 
start = time.time()
 
for a in range(2,limit):
    for b in range(2,limit):
        c = a**b
        if c in L: pass
        # else: L.append(c) # old list version
        L.add(c) # new version with set
 
elapsed = time.time() - start
 
print "found %s ints in %s seconds" % (len(L), elapsed)

When executed, we get the correct result in under a second.

$ python 29.py 
# found 9183 ints in 0.66696190834 seconds # old list version
found 9183 ints in 0.0150249004364 seconds

Problem

The $n^\text{th}$ term of the sequence of triangle numbers is given by, $t_n=\frac{1}{2}n(n+1)$; so the first ten triangle numbers are: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = $t_{10}$. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and ‘Save Link/Target As…’), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Solution in Python

#!/usr/bin/python
 
import time
 
# start the clock
start = time.time()
 
# turn the string of words into a list of python strings
with open('words.txt','r') as f:
    words = f.read().split(',')
    words = [list(word.strip('\"')) for word in words]
    f.close()
 
# we should have an idea of how long the longest word is,
# giving us an idea of the magnitude of the triangle words
m = max([len(word) for word in words])
# form triangle numbers up to the given range
triangles = [n*(n + 1)/2 for n in range(1,2*m)]
 
# make a dictionary map for character values
vals = {}
s = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
for c in s:
    vals[c] = s.index(c) + 1
 
# count triangle words
triangle_words = 0
for word in words:
    if sum([vals[c] for c in word]) in triangles:
        triangle_words += 1
 
# terminate the clock
elapsed = time.time() - start
 
print "found %s triangle words in %s seconds" % (triangle_words, elapsed)

When executed, this returns as follows.

found 162 triangle words in 0.00315809249878 seconds