Project Euler Problem 204

Solution

Answer: 2944730

1. Mathematical analysis

We want to count generalised Hamming numbers of type 100 not exceeding $10^9$.

A number is a generalised Hamming number of type $n$ if all prime factors are $\le n$.

For type $100$, the allowed primes are:

$$2,3,5,7,11,\dots,97$$

That is, all primes $\le 100$.

We need to count integers of the form

$$m = \prod_{p\le 100} p^{e_p}$$

such that

$$m \le 10^9, \qquad e_p \ge 0.$$

Key insight: recursive generation by prime powers

A brute-force search over integers up to $10^9$ would be hopeless.

Instead, observe that every valid number has a unique prime factorization, so we can recursively build all possibilities.

Suppose the primes are:

$$p_1,p_2,\dots,p_k$$

For each prime $p_i$, we may choose exponent

$$e_i = 0,1,2,\dots$$

subject to staying below the limit.

At each recursive step:

choose a power of the current prime,
multiply it into the current product,
recurse to the next prime.

Because prime factorization is unique:

every valid number is generated exactly once, and
no invalid number is generated.

This is essentially a depth-first enumeration of exponent vectors.

For example, with type $5$, allowed primes are:

$$2,3,5$$

and we generate numbers of form

$$2^a3^b5^c \le N.$$

For $N=10^8$, the count should be 1105, matching the problem statement.

2. Python implementation

from sympy import primerange

LIMIT = 10**9

# All allowed prime factors (primes <= 100)
primes = list(primerange(1, 101))

def count_hamming(index, current):
    """
    Recursively count generalised Hamming numbers.

    index   : which prime we are currently processing
    current : current product formed so far
    """
    # If all primes processed, we found one valid number
    if index == len(primes):
        return 1

    total = 0
    p = primes[index]

    # Try all powers of p that keep us <= LIMIT
    value = current
    while value <= LIMIT:
        total += count_hamming(index + 1, value)
        value *= p

    return total

answer = count_hamming(0, 1)
print(answer)

3. Code walkthrough

Step 1: Generate primes

primes = list(primerange(1, 101))

This creates:

$$[2,3,5,7,11,\dots,97]$$

These are exactly the allowed prime factors.

Step 2: Recursive counting function

def count_hamming(index, current):

index tells us which prime we are considering.
current is the product accumulated so far.

Step 3: Base case

if index == len(primes):
    return 1

Once we've processed every prime, we have constructed one valid Hamming number.

Count it.

Step 4: Try every exponent

value = current
while value <= LIMIT:

We repeatedly multiply by the current prime:

$$p^0,\ p^1,\ p^2,\ \dots$$

until we exceed the limit.

Each choice recursively explores all later primes.

Step 5: Accumulate counts

total += count_hamming(index + 1, value)

We count all valid completions from that choice of exponent.

Small-example verification

For type $5$, allowed primes are $2,3,5$.

Running the same recursion with:

LIMIT = 10**8
primes = [2, 3, 5]

returns:

$$1105$$

which exactly matches the problem statement.

So the algorithm is validated.

4. Final verification

The result should be:

much larger than 1105, since type $100$ allows 25 primes,
but still only a few million because $10^9$ severely limits exponent combinations.

The recursive search counts each valid factorization exactly once and avoids double counting.

The computed total is:

$$2,!944,!730$$

Answer: 2944730