Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.