A recent mailing list post inspired this one. See the email and the code for details.

#!/usr/bin/python # This proglet finds the first 3000 Hamming numbers, numbers with no prime # factors greater than 5. # It was inpired by the an email from Jonathan McKeown on a programming # mailing list. MAX_NUMBER = 3000 def getPrimes(maxnum): """Calculates all the prime numbers less than maxnum. This may not be the best algorithm to use, but I've gone for simplicity over elegance and performance here.""" primes = [2] for number in range(2, maxnum): number += 1 isPrime = 1 for prime in primes: if (number % prime) == 0: isPrime = 0 break if isPrime: primes.append(number) return primes def getHamming(maxnum): """Calculates Hamming numbers from 1 to maxnum.""" # We want all the primes less than half the maximum number except the # first three: primes = getPrimes(maxnum/2)[3:] hamming = [] for number in range(maxnum): number += 1 isHamming = 1 for prime in primes: if prime > number: break if number % prime == 0: isHamming = 0 break if isHamming: hamming.append(number) return hamming print getHamming(MAX_NUMBER)

This was called "unpythonic", so it was replaced by the following, which also halves the numbers checked for primeness to only the odds.

#!/usr/bin/python # This proglet finds the first 3000 Hamming numbers, numbers with no prime # factors greater than 5. # It was inpired by the an email from Jonathan McKeown on a programming # mailing list. MAX_NUMBER = 3000 def getPrimes(maxnum): """Calculates all the prime numbers less than maxnum. This may not be the best algorithm to use, but I've gone for simplicity over elegance and performance here.""" primes = [2] [ primes.append(i) for i in xrange(3,maxnum+1,2) if not 0 in [i%j for j in primes] ] return primes def getHamming(maxnum): """Calculates Hamming numbers from 1 to maxnum.""" # We want all the primes less than half the maximum number except the # first three: primes = getPrimes(maxnum/2)[3:] hamming = [] [ hamming.append(i) for i in xrange(1,maxnum+1) if not 0 in [i%j for j in primes] ] return hamming print getHamming(MAX_NUMBER)

After this version, I realised that I had misread the question and calculated the Hamming numbers up to 3000 rather than the first 3000 Hamming numbers. The latter problem is more easily solved by generation rather than decimation, so that's what I tried next:

#!/usr/bin/python # This proglet finds the first 3000 Hamming numbers, numbers with no prime # factors greater than 5. # It was inpired by the an email from Jonathan McKeown on a programming # mailing list. def getHamming(num): hamming = [1, 2] current = [] cIdx = 0 while len(hamming) < num: current.append(hamming[cIdx] * 5) current.append(hamming[cIdx] * 3) current.append(hamming[cIdx] * 2) cIdx += 1 while (current[0] < current[-1]): if hamming[-1] != current[0]: hamming.append(current.pop(0)) else: current.pop(0) if len(hamming) >= num: break current.sort() return hamming for item in getHamming(3000): print item

The numbers coming out of this look smaller than those generated by others, but I'm not sure where the error is. I'll check back after the weekend.