Estimating the proportion of smooth numbers

A number is said to be “smooth” if all its prime factors are small.

To make this precise, a number is said to be y-smooth if it only has prime factors less than or equal to y.

So, for example, 1000 is 5-smooth.

The de Bruijn function φ(x, y) counts the number of y-smooth positive integers up to x, and so φ(x, y)/x is the probability that a number between 1 and x is y-smooth.

It turns out that φ(x, x1/u)/x ≈ 1/uu.

This means, for example, that the proportion of numbers with less than 100 digits whose factors all have less than 20 digits is roughly 1/55 = 1/3125.

Source: The Joy of Factoring Here’s a little Python code to experiment with this approximation.

We’ll look at the proportion of 96-bit numbers whose largest prime factor has at most 32 bits.

from secrets import randbits from sympy.


factor_ import smoothness smooth = 0 for _ in range(100): x = randbits(96) s = smoothness(x)[0] if s < 2**32: smooth += 1 print(“Num small:”, smooth) The SymPy function smoothness returns a pair, and the first element of the pair is the largest prime dividing its argument.

In our case u = 3, and so we’d expect about 1/27 of our numbers to have no factors larger than 32 bits.

I ran this five times, and got 8, 2, 5, 3, and 7.

From the approximation above we’d expect results around 4, so our results are not surprising.


Leave a Reply