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
    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).2011-02-20
  • 0
    Have you looked at http://archive.numdam.org/article/JTNB_1993__5_2_411_0.pdf? (ref 5 in Wikipedia, Dickman function)2011-02-20
  • 0
    @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#.2011-02-21
  • 0
    @Yuval: Yes, but I doubt I need 75 pages of theory to answer this question. Did you see an explict answer in there?2011-02-21
  • 0
    @Andrew: I didn't look, that's your job...2011-02-21
  • 1
    @Yuval: First, please don't recommend a read if you don't know if it even has what the OP is looking for. Second, just as an rule, phrases like "that's your job" add nothing to the discussion and only make you seem rude, even if that's not your intention. Oddly, this is a hobby for me so using the word "job" only further perturbed me :)2011-02-21
  • 0
    @Andrew: I did have a quick look, and it seemed very thorough. The Wikipedia article on the Dickman function states that if $B \sim N^{1/u}$ then the Dickman function gives the asymptotic answer to your question; presumably this 75-page paper provides a more complete answer. As you mentioned, I don't know what you're looking for; therefore *you* have to look at the paper yourself.2011-02-21
  • 0
    What can you tell us about the sizes of N and B? The answer will depend strongly on that. Also, as with most things, spending more time can give stronger answers. How precise do you need to be, or alternately, how much time are you willing to spend? If you need a million rough estimates and don't want to spend more than a few milliseconds on each that will give a different answer than if you're willing to put in 10 CPU-months.2011-02-21
  • 0
    And, FWIW, I wrote the article referenced 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.)