2
$\begingroup$

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.

  • 0
    And, FWIW, I w$r$o$t$e the a$r$$t$icle $r$eferenced above. :)2011-02-21

2 Answers 2

4

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}.$

  • 0
    I should mention that a fairly good justification for taking the derivative is provided by the mean value theorem.2011-02-21
3

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.)