$B$-smooth integers with constrained factors

Published February 27, 2026｜5 minute read

As part of a project, I needed to compute the probability of a large integer being $B$-smooth, conditional on knowledge about the sizes of its prime factors. I found very little information about this problem in the literature.

This post (1) solves this problem with high accuracy, and (2) verifies the theoretical results experimentally.

Problem Statement

Choose an integer uniformly at random from the interval $[N, N + L]$, where $N \gg L$. Given that the integer $N$ has no prime factors in an interval $[B_0, B_1]$, what is the (conditional) probability that it is $B$-smooth?

This problem can be easily extended to e.g. restrict prime factors to multiple subintervals. For simplicity, we will analyze the single-interval problem above. In what follows, we assume that $B_0 < B_1 < B$.

Solution

Let $K(a, b) \subseteq [a, b]$ denote the set of $B$-smooth integers in the interval $[a, b]$. Observe that the set of integers in $K(a, b)$ divisible by a fixed prime $p$ is in bijection with the set $K(a/p, b/p)$.

By the principle of inclusion-exclusion (PIE), the number $M$ of integers in $K(N, N+L)$ which are not divisible by any $p \in [B_0, B_1]$ is$$\begin{aligned} M = \, &|K(N, N+L)| \\ &- \sum_{B_0 \leq p \leq B_1} |K(N/p, (N+L)/p)| \\ &+ \sum_{B_0 \leq p_1 < p_2 \leq B_1} |K(N/(p_1 p_2), (N+L)/(p_1 p_2))| \\ &- \cdots \end{aligned}$$Recall that $K(a, b) \sim (b-a) \, \rho(\ln(a)/\ln(B))$ for intervals with $b-a \ll a$, where $\rho$ is the Dickman-de Brujin function. We therefore have$$\begin{aligned} \frac{M}{L} \sim \, &\rho(\ln{N}/\ln{B}) \\ &- \sum_{B_0 \leq p \leq B_1} \rho\left(\frac{\ln{N} - \ln{p}}{\ln{B}}\right) \\ &+ \sum_{B_0 \leq p_1 < p_2 \leq B_1} \rho\left(\frac{\ln{N} - \ln{p_1} - \ln{p_2}}{\ln{B}}\right) \\ &- \cdots \end{aligned}$$Using the heuristic measure$$\mathbb{1}_{\text{primes}} \sim \frac{dx}{x \ln{x}} \sim \frac{du}{u}$$where $u := \ln{x}$, we may write$$\begin{aligned} \frac{M}{L} \sim \, &\rho(\ln{N}/\ln{B}) \\ &- \int_{\ln{B_0}}^{\ln{B_1}} \frac{1}{u} \, \rho\left(\frac{\ln{N} - u}{\ln{B}}\right) \dd{u} \\ &+ \frac{1}{2!} \int_{\ln{B_0}}^{\ln{B_1}} \int_{\ln{B_0}}^{\ln{B_1}} \frac{1}{uv} \, \rho\left(\frac{\ln{N} - u - v}{\ln{B}}\right) \dd{u} \dd{v} \\ &- \cdots \end{aligned}$$This is a bit unwieldy, and the multidimensional integrals are difficult to compute numerically. Luckily, it's possible to simplify this quite a bit.

Simplification

Recursively define the helper function$$I_0(x) := \rho(x/\ln{B}),$$ $$I_n(x) := \frac{1}{n} \int_{\ln{B_0}}^{\ln{B_1}} \frac{I_{n-1}(x-u)}{u} \, \dd{u}.$$Then we have the much nicer expression$$\mathbb{P}(\text{clean and }B\text{-smooth}) := \frac{M}{L} = \sum_{n=0}^\infty (-1)^n \, I_n(\ln{N}),$$where I have defined clean to be the property of having no prime factors in the interval $[B_0, B_1]$, and smooth to mean $B$-smooth.

The functions $I_n$ are easily computed iteratively over $n$, by keeping track of all values over the interval $-1 < x \leq \ln{N}$. To obtain correct results, it is important to use the convention $\rho(x) = 0$ for $x < 0$ to remain consistent with the original formula from PIE.

Finally, we get the desired conditional probability$$\mathbb{P}(B\text{-smooth} \, | \, \text{clean}) = \frac{\mathbb{P}(\text{clean and }B\text{-smooth})}{\mathbb{P}(\text{clean and }\infty\text{-smooth})},$$where both the numerator and denominator can be computed using the formula above.^[1]

Numerical Computation

The below plot shows the quantities $\mathbb{P}(B\text{-smooth})$, $\mathbb{P}(\text{clean})$, and $\mathbb{P}(\text{clean and }B\text{-smooth})$ for concrete values $(B_0, B_1, B) = 2^{20}, 2^{32}, 2^{37}$.

Note that the slight wiggles in the purple curve are real and not numerical artifacts!

As $N \to \infty$, the probability $\mathbb{P}(\text{clean})$ tends towards the value $\ln{B_0}/\ln{B_1}$. This is consistent with Mertens’ third theorem.

From the above curves, we can also compute the conditional probability of interest. As expected, the probability of a clean integer being $B$-smooth is lower than that of a generic integer.

Finally, we can experimentally generate clean integers^[2] and plot the probability of being $B$-smooth for various values of $B$, and compare against the theoretical reference.

We get excellent agreement, even down to the subtle wiggles in the theoretical prediction.