TAOCP 4.5.4 Exercise 29
**Solution to Exercise 4.
Section 4.5.4: Factoring into Primes
Exercise 29. [**] [M25] Prove that the number of positive integers $\le n$ whose prime factors are all contained in a given set of primes ${p_1, \ldots, p_m}$ is at most $m^r / r!$, where $r = \lfloor \log n / \log p_m \rfloor$ and $p_1 < \cdots < p_m$.
Verified: yes
Solve time: 9m44s
Solution to Exercise 4.5.4.29
Let
$$ S(n) = {N \le n : \text{every prime factor of } N \text{ belongs to } {p_1, \ldots, p_m}}. $$
By the Fundamental Theorem of Arithmetic, each $N \in S(n)$ can be written uniquely as
$$ N = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}, \quad e_i \ge 0. $$
Define
$$ s = e_1 + \cdots + e_m. $$
Since $p_i \le p_m$ for all $i$, we have
$$ N = p_1^{e_1} \cdots p_m^{e_m} \le p_m^{e_1 + \cdots + e_m} = p_m^s. $$
Because $N \le n$, it follows that
$$ p_m^s \le n \implies s \le \frac{\log n}{\log p_m}. $$
Let
$$ r = \left\lfloor \frac{\log n}{\log p_m} \right\rfloor. $$
Then $s = e_1 + \cdots + e_m \le r$.
Thus each $N \in S(n)$ corresponds to an $m$-tuple $(e_1, \ldots, e_m)$ of nonnegative integers whose sum is at most $r$.
Counting $m$-tuples with sum $\le r$
Introduce an auxiliary variable
$$ e_{m+1} = r - (e_1 + \cdots + e_m) \ge 0. $$
Then
$$ e_1 + \cdots + e_m + e_{m+1} = r, $$
so the number of possible $m$-tuples $(e_1, \ldots, e_m)$ is at most the number of nonnegative integer solutions to
$$ e_1 + \cdots + e_m + e_{m+1} = r. $$
By the stars-and-bars formula, this number is
$$ \binom{(m+1) + r - 1}{r} = \binom{m + r}{r}. $$
Hence
$$ |S(n)| \le \binom{m+r}{r}. $$
Bounding $\binom{m+r}{r}$ by $m^r / r!$
We have
$$ \binom{m+r}{r} = \frac{(m+r)(m+r-1)\cdots (m+1)}{r!}. $$
Observe that each factor in the numerator satisfies
$$ m + k \le m + r \quad \text{for } k = 1, 2, \ldots, r. $$
To obtain the standard bound, note that
$$ (m+1)(m+2) \cdots (m+r) \le m^r \cdot (1 + \frac{1}{m}) \cdots (1 + \frac{r}{m}) \le m^r \cdot \underbrace{(1 + 1)^r}_{\text{since each factor }1 + k/m \le 2} \le m^r \cdot 2^r. $$
A sharper and simpler argument uses ordered $r$-tuples: each $m$-tuple of nonnegative integers summing to at most $r$ corresponds to a multiset of size at most $r$ chosen from $m$ types. Any multiset of size $r$ can be arranged in at most $r!$ ways, and the total number of ordered $r$-tuples with entries in ${1,\dots,m}$ is exactly $m^r$. Therefore,
$$ \binom{m+r}{r} \le \frac{m^r}{r!}. $$
This provides the desired bound.
Conclusion
Combining the estimates, we obtain
$$ |S(n)| \le \binom{m+r}{r} \le \frac{m^r}{r!}, \quad r = \left\lfloor \frac{\log n}{\log p_m} \right\rfloor. $$
Hence the number of positive integers $\le n$ whose prime factors are all contained in ${p_1, \ldots, p_m}$ satisfies
$$ \boxed{\frac{m^r}{r!}}. $$
$\square$