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.
$\begingroup$
$\endgroup$
9
-
$\begingroup$ 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). $\endgroup$– Qiaochu YuanFeb 20, 2011 at 17:44
-
$\begingroup$ Have you looked at archive.numdam.org/article/JTNB_1993__5_2_411_0.pdf? (ref 5 in Wikipedia, Dickman function) $\endgroup$– Yuval FilmusFeb 20, 2011 at 18:11
-
$\begingroup$ @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#. $\endgroup$– Andrew WhiteFeb 21, 2011 at 0:28
-
$\begingroup$ @Yuval: Yes, but I doubt I need 75 pages of theory to answer this question. Did you see an explict answer in there? $\endgroup$– Andrew WhiteFeb 21, 2011 at 0:30
-
1$\begingroup$ @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 :) $\endgroup$– Andrew WhiteFeb 21, 2011 at 3:13
|
Show 4 more comments
2 Answers
$\begingroup$
$\endgroup$
1
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.)
-
$\begingroup$ I did some checking for random 2^128 bit integers to see if they were 2^32 smooth which should happen according to this formula at a rate of about 4 in 1000 and I was finding them near that rate. $\endgroup$ Jan 22, 2019 at 23:15
$\begingroup$
$\endgroup$
1
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}.$$
answered Feb 21, 2011 at 0:42
-
$\begingroup$ I should mention that a fairly good justification for taking the derivative is provided by the mean value theorem. $\endgroup$ Feb 21, 2011 at 12:49