Generalised Hamming Numbers

Problem 204

A Hamming number is a positive number which has no prime factor larger than 5. So the first few Hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. There are 1105 Hamming numbers not exceeding 10⁸.

We will call a positive number a generalised Hamming number of type n, if it has no prime factor larger than n. Hence the Hamming numbers are the generalised Hamming numbers of type 5.

How many generalised Hamming numbers of type 100 are there which don't exceed 10⁹?

The recent email starting with this one, led to someone mentioning Project Euler Problem #204, so I am playing with Project Euler once again.



In [1]:

    
MAX_PRIME = 100
MAX_SMOOTH = 10**9



In [2]:

    
def is_prime(x):
    return all(x % divisor != 0 for divisor in range(2, x))



In [3]:

    
primes = tuple(x for x in range(2, MAX_PRIME+1) if is_prime(x))



In [4]:

    
def n_smooth_numbers(n, x, primes, max_smooth):
    if not primes:
        return n
    while True:
        n = n_smooth_numbers(n, x, primes[1:], max_smooth)
        x *= primes[0]
        if x > max_smooth:
            return n
        n += 1



In [5]:

    
n_smooth_numbers(1, 1, (2, 3, 5), 30)









    Out[5]:





18



In [6]:

    
def foo():
    return n_smooth_numbers(1, 1, primes, MAX_SMOOTH)



In [7]:

    
%timeit foo()
foo()









    



1 loop, best of 3: 25.1 s per loop






    Out[7]:





2944730

Using default values for n and x makes the first call easier and the execution speed slower.



In [8]:

    
def n_smooth_numbers(primes, max_smooth, n=1, x=1):
    if not primes:
        return n
    while True:
        n = n_smooth_numbers(primes[1:], max_smooth, n, x)
        x *= primes[0]
        if x > max_smooth:
            return n
        n += 1



In [9]:

    
n_smooth_numbers((2, 3, 5), 30)









    Out[9]:





18



In [10]:

    
def foo():
    return n_smooth_numbers(primes, MAX_SMOOTH)



In [11]:

    
%timeit foo()
foo()









    



1 loop, best of 3: 26.4 s per loop






    Out[11]:





2944730

Using tuple unpacking below makes the code easier to readn and slower.



In [12]:

    
def n_smooth_numbers(primes, max_smooth, n=1, x=1):
    if not primes:
        return n
    first_prime, *other_primes = primes
    while True:
        n = n_smooth_numbers(other_primes, max_smooth, n, x)
        x *= first_prime
        if x > max_smooth:
            return n
        n += 1



In [13]:

    
n_smooth_numbers((2, 3, 5), 30)









    Out[13]:





18



In [14]:

    
def foo():
    return n_smooth_numbers(primes, MAX_SMOOTH)



In [15]:

    
%timeit foo()
foo()









    



1 loop, best of 3: 32.1 s per loop






    Out[15]:





2944730