# Probability of being B smooth

Given an integer N and a smooth base B; what is the (approximate) probability that N is completely divisible by primes <= B.

I assume there is some nice connection to the de Bruijn or Dickman function but I can't see it.

-
The natural density of B-smooth integers is zero for any B, so you should probably ask a more precise question (for example about N in a certain range). – Qiaochu Yuan Feb 20 '11 at 17:44
Have you looked at archive.numdam.org/article/JTNB_1993__5_2_411_0.pdf? (ref 5 in Wikipedia, Dickman function) – Yuval Filmus Feb 20 '11 at 18:11
@Qiaoch: I have a box that takes N and B and produces P which is it's best guess to the chance of N and numbers around it being B smooth. Example: N is a 2000 digit number and B is 10#. – Andrew White Feb 21 '11 at 0:28
@Yuval: Yes, but I doubt I need 75 pages of theory to answer this question. Did you see an explict answer in there? – Andrew White Feb 21 '11 at 0:30
@Andrew: I didn't look, that's your job... – Yuval Filmus Feb 21 '11 at 1:27

Let $p_1, ... p_n$ be the first $n$ primes and let $\pi_n(N)$ be the number of positive integers less than or equal to $N$ divisible by only the primes $p_i$. This is precisely the number of non-negative integer solutions to

$$\sum_{i=1}^n e_i \log p_i \le \log N$$

which defines an $n$-dimensional region with volume $V = \frac{(\log N)^n}{n! \log p_1 ... \log p_n}$. So this is a first-order estimate of the number of solutions; in other words, asymptotically we have

$$\pi_n(N) \sim \frac{(\log N)^n}{n! \log p_1 ... \log p_n}.$$

(The error term is $O(( \log N)^{n-1})$.) A reasonable guess for the probability that $N$ itself is divisible only by the primes $p_i$ is then roughly the derivative of this, or

$$\frac{n (\log N)^{n-1}}{N n! \log p_1 ... \log p_n}.$$

-
I should mention that a fairly good justification for taking the derivative is provided by the mean value theorem. – Qiaochu Yuan Feb 21 '11 at 12:49

See "Prime Numbers: A Computational Perspective," by Crandall and Pomerance. The probability that a uniform integer in the ranger ${1, ..., N}$ is $B$-smooth is given there as $u^{-u}$, where $u = \ln N/\ln B$. (I am not sure whether this is heuristic or provable.)

-