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