Detailed mathematical approach

Problem Summary

A generalized Hamming number of type \(T\) is a positive integer whose prime divisors are all at most \(T\). For this problem we must count how many numbers \(n \le L\) satisfy that condition when \(T=100\) and \(L=10^9\).

If we write the set of admissible numbers as \(\mathcal{H}(T,L)\), then the task is to determine \(|\mathcal{H}(100,10^9)|\). The key observation is that only the primes up to \(T\) matter: once those primes are fixed, every allowed composite factor is already built from them.

Mathematical Approach

Let \(p_1 \lt p_2 \lt \cdots \lt p_r\) be the primes not exceeding \(T\). The implementations count generalized Hamming numbers by exploring the exponent choices of these primes in increasing order.

Prime Factors Are the Entire State Space

By the fundamental theorem of arithmetic, every admissible number has a unique representation

$n=\prod_{i=1}^{r} p_i^{e_i}, \qquad e_i \ge 0,$

and the condition \(n \le L\) becomes

$\prod_{i=1}^{r} p_i^{e_i} \le L.$

So the problem is not about testing arbitrary integers one by one. It is a structured counting problem over exponent vectors \((e_1,\dots,e_r)\). Composite numbers \(\le T\) do not need their own branches, because their prime factors are already among the \(p_i\).

A Counting Recurrence

Define \(F(i,m)\) to be the number of integers \(n \le m\) whose prime factors all belong to \(\{p_i,p_{i+1},\dots,p_r\}\). Then the base case is

$F(r+1,m)=1,$

because once no primes remain, there is exactly one completion: choose all remaining exponents to be zero. For \(1 \le i \le r\), the exponent of \(p_i\) can be \(0,1,2,\dots\) as long as \(p_i^k \le m\), so

$F(i,m)=\sum_{\substack{k \ge 0 \\ p_i^k \le m}} F\!\left(i+1,\left\lfloor \frac{m}{p_i^k} \right\rfloor\right).$

This is the exact mathematics implemented by the depth-first search. Instead of storing \(m\) explicitly, the code keeps the current product and lets the remaining budget be \(L\) divided by that product.

Why the Depth-First Enumeration Is Exact

At recursion depth \(i\), the current value has the form

$x=\prod_{j=1}^{i-1} p_j^{e_j},$

with \(x \le L\). This is the core invariant: the exponents for the first \(i-1\) primes are already fixed, and only the later primes are still free. The next loop tries \(x\), \(x p_i\), \(x p_i^2\), and so on until the limit would be exceeded.

Because primes are handled in one fixed order, every exponent vector produces exactly one root-to-leaf path. By uniqueness of prime factorization, no valid number can appear twice under different branches. When the search reaches the level after the last prime, one and only one generalized Hamming number has been fully specified, so the counter is increased by 1. The all-zero exponent choice is therefore counted automatically, giving the number \(1\).

Worked Example: Type 5 Up to 100

For \(T=5\), the allowed primes are \(2,3,5\). If \(L=100\), then

$F(1,100)=F(2,100)+F(2,50)+F(2,25)+F(2,12)+F(2,6)+F(2,3)+F(2,1).$

These seven terms correspond to the possible exponents of \(2\): \(2^0,2^1,\dots,2^6\). Each term is then split again by the exponent of \(3\), and each of those branches is finally split by powers of \(5\). Carrying the recursion through gives 34 numbers in total, namely the integers of the form \(2^a3^b5^c \le 100\).

This small example is exactly the same tree structure used for type \(100\) and limit \(10^9\); only the list of primes and the search depth become larger.

How the Code Works

The C++, Python, and Java implementations all follow the same two-phase pattern: first generate the relevant primes, then recursively enumerate every valid exponent combination.

Prime Generation

The implementation begins with a sieve up to \(T\) and collects all primes \(\le T\). For Problem 204 this yields \(r=\pi(100)=25\) primes. That prime list completely determines the search tree.

Recursive State and Branches

The recursive state is naturally described by a pair \((i,x)\), where \(i\) is the next prime index and \(x\) is the current product already formed from earlier primes. From that state, the implementation recursively explores

$x,\; x p_i,\; x p_i^2,\; x p_i^3,\dots$

for as long as those values stay within the limit. Moving to the next level means that the exponent of \(p_i\) has been fixed and the search continues with the next prime.

Base Case and Safety Guard

When all primes have been processed, the recursion has fixed a complete exponent vector, so one valid number is counted. Before multiplying by the next prime, the implementation checks

$x \le \left\lfloor \frac{L}{p_i} \right\rfloor,$

which is equivalent to \(x p_i \le L\). This keeps the search inside the bound and also avoids overflowing the integer type during multiplication.

Complexity Analysis

Generating the primes with a sieve costs \(O(T \log\log T)\) time and \(O(T)\) memory.

For the search itself, let \(N=|\mathcal{H}(T,L)|\) and let \(r=\pi(T)\). The recursion depth is \(r\). Every node at depth \(i\) is a partial product built from the first \(i-1\) primes, and that partial product is itself a generalized Hamming number not exceeding \(L\). Hence there are at most \(N\) nodes on each depth level, giving \(O(rN)\) recursive calls overall.

For the actual problem \(T=100\), \(r=25\), so the depth is tiny and the method is effectively output-sensitive: it spends its time enumerating precisely the valid exponent combinations rather than scanning all integers up to \(10^9\). The extra memory used by the search is \(O(r)\) for the recursion stack, in addition to the sieve storage.

Footnotes and References

1. Project Euler 204: Generalised Hamming Numbers
2. Wikipedia: Regular number
3. Wikipedia: Fundamental theorem of arithmetic
4. Wikipedia: Sieve of Eratosthenes
5. Wikipedia: Depth-first search