# Number of smooth numbers less than x

A $$p$$-smooth number is defined as an integer whose prime factors are all less than or equal to $$p$$

In the wiki article about smooth numbers it states:

Let $$\displaystyle \Psi (x,y)$$ denote the number of $$y$$-smooth integers less than or equal to $$x$$ (the de Bruijn function). If the smoothness bound $$B$$ is fixed and small, there is a good estimate for $$\displaystyle \Psi (x,B)$$: $$\displaystyle \Psi (x,B)\sim \frac {1}{\pi (B)!}\prod _{p\leq B}{\frac {\log x}{\log p}}$$ where $$\displaystyle \pi (B)$$ denotes the number of primes less than or equal to $$B$$.

How was this derived? Are there any other good bounds on $$\Psi(x,y)$$?

Let $$S(x, B)$$ be the set of $$B$$ smooth numbers less than or equal than $$x$$. You notice that $$n \in S(x, B)$$ iff $$\log(n) \le \log(x)$$. Writing

$$n = \prod_{p_i \le B} p_i^{\alpha_i}$$

For $$p_i$$ primes and $$\alpha_i$$ the exponent with which appears (possibly zero), $$n\in S(x, B)$$ iff

$$\sum_i \alpha_i \log p_i \le \log(x)$$

This is like asking how many integer coordinates points $$(\alpha_1, \ldots, \alpha_m)$$ are contained in the region

$$A(x, B) = \{ (t_1, \ldots, t_m) \in \mathbb{R}^m : \sum (\log p_i) t_i \le \log(x), \ \ \ t_i \ge 0\}$$

Here $$m =\pi(B)$$ is the number of free parameters we have. It turns out this is closely related to the volume of this region: up to small problems on the boundary, a integer coordinate point contribute with a cube of volume 1, so that

$$\# \{\text{integer coordinate points in } A(x, B) \} \sim \text{volume}(A(x, B))$$

Since the boundary has one dimension less, the approximation gets better and the better as $$x$$ gets larger with respect to $$B$$.

Let's wrap our head around how to calculate this volume. We could do the integral but it's boring. Geometrically, it is a little pyramid of dimension $$m+1$$, with a nice angle at zero and then some edges departing from it. The edges are long $$\log(x) /\log(p_i)$$: you get this by taking the maximum possible $$t_i$$ while all the other parameters are zero, because we are going along an axis.

The volume is linear in the length of the edges, so that we can factor out a

$$\prod_{p\le B} \frac{\log(x) }{\log(p) }$$

And we are left with computing the volume of

$$D =\{(t_1, \ldots, t_m) : \sum t_i \le 1, \ \ t_i \ge 0\}$$

For $$m=2$$, this is $$1/2$$. Let's show by induction that the volume of such a pyramid in dimension $$k$$ is $$1/k!$$. If we know this for $$k$$, we also know that a tiny piramid with edges $$=s$$ has volume $$s^k/k!$$, by the same scaling argument as above. For $$k+1$$, we can section along a coordinate and we get pyramids of size $$s$$ for all $$0\le s \le 1$$. Integrating we get

$$\int_{s=0}^1 \frac{s^k}{k! } = \frac{1}{(k+1)! }$$

As desired. Getting back to our original problem, we had $$m=\pi(B)$$ dimensions, so that

$$\Psi(x, B) \sim \frac{1}{\pi(B)! } \prod_{p \le B} \frac{\log x}{\log p}$$

As desired. Note also that you have estimates of both parts in term of $$x, B$$, so that you get a neat estimate in the end!

If we let $$y=5$$, for example, each $$5-$$smooth number $$N$$ can be written as $$N=2^a3^b5^c$$. We then have $$\log N=a\log 2 + b\log 3 +c\log 5$$. You can think of a lattice, three dimensional because we have three primes, with each $$5-$$smooth number identified with the point $$(a,b,c)$$ in the lattice. The lattice spacing is $$\log 2, \log 3, \log 5$$ in the three dimensions. $$\Psi(x,5)$$ is then the number of lattice points nearer the origin than a plane that goes through the point $$\log N$$ on each axis. There are $$\frac {\log N} {\log 2}$$ points along the $$2$$ axis and similarly along the other axes. This means the volume of a lattice cell is $$\prod_{p \le 5} \log p$$, which gets us the product in your expression. The fact that we have a tetrahedron instead of a rectangular block give a factor $$\frac 16$$, which corresponds to the $$\frac 1{\pi(B)!}$$ in your expression.