2
$\begingroup$

That is, how to calculate it given the size of N(that is, logN) and assuming that logN is much greater than M. Its an approximation. There is no exact formula.

I do know that according to the prime number theorem the probability for N being prime is 1/ln(N) for large positive integers.

Thanks.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ You are clearly talking about infinitely many $N$ here. What is the distribution on this infinite set of numbers? Or do you want to know the limit of the probablities of $N$ having at least $M$ factors for $N$ in an interval $(a,b)$ where $a$ is large compared to $M$ and $b$ goes to infinity? In this case you would have to argue why this limit exists. $\endgroup$
    – Stefan Geschke
    Sep 2, 2012 at 11:01
  • $\begingroup$ Try en.wikipedia.org/wiki/Divisor_function for the basics on the function d(n). $\endgroup$
    – Charles Matthews
    Sep 2, 2012 at 11:01
  • $\begingroup$ Also, in what sense is the probability of $N$ being prime $1/\ln(N)$? Given $N$, the probability that $N$ is prime is either $0$ or $1$. $\endgroup$
    – Stefan Geschke
    Sep 2, 2012 at 11:05
  • 1
    $\begingroup$ @Stefan I think the questioner is trying to ask something like: "Given positive integer $N$, and numbers $L,M< N$, if you pick a random number in the set $\{N+i,N−i|0\leq i<L \}$ (Numbers "around" $N$) , what is the probability that it has at least $M$ factors? "Or maybe not so symmetric sample around $N$. What if we pick a number out of the set of all numbers with the same number of digits as $N$ instead? $\endgroup$
    – LeBlanc
    Sep 2, 2012 at 11:54
  • 1
    $\begingroup$ I'd recommend looking at the beautiful and accessible MAA book by Mark Kac, Statistical Independence in Probability, Analysis and Number Theory. This deals in a very nice way with the number of divisors function. $\endgroup$
    – Anthony Quas
    Sep 2, 2012 at 18:00

3 Answers 3

Reset to default
4
$\begingroup$

The count of numbers up to $x$ having at most $k$ prime divisors (counted with mutiplicity) is asymtotically equal to (see for example Almost prime on Wikipedia) $$ \frac{x}{\log x} \frac{(\log \log x)^{k-1}}{(k-1)!} .$$

Thus, since the number of divisors is definitely greater than the number of prime divisors, the probabilty (in the informal sense used in the question) that some $N$ has at least $M\ge 3$ divisors is (asymtotically) at least $$ 1 - \frac{1}{\log N} \frac{(\log \log N)^{M-3}}{(M-3)!} .$$

It might well be possible to improve this as there are 'few' numbers for which the number of primes divisors (with mutiplicty) is 'close to' the number of divisors.

A quick guess, possibly wrong, would be that one might be able to improve this towards something like $$ 1 - c \frac{(\log \log N)^{\log M}}{\log N}, $$ by looking at distinct prime divisors.

And this would be about optimal, which can be seen via noting that if the number of prime divisors (with multiplicty) is $k$ this bounds the number of divisors by $2^k$, and using the above argument in the other direction.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It occurs to me that despite most people, including me, talking about divisors the 'factprs' of OP might in fact be the number of factors one gets when decomposing the number into primes; yet this then would be the primes divisors (with multiplicty), so implictly address in my answer as well, and indeed simpler. $\endgroup$
    – user9072
    Sep 2, 2012 at 22:40
3
$\begingroup$

The Erdős-Kac theorem gives that, for a fixed function $M(N)$ with $\limsup M(N)/\log \log N < 1$,

$\frac{1}{N} |\{n\in[N,2N] : \omega(n) > M(N)\}|\rightarrow 1$.

Likewise if $\liminf M(N)/\log \log N > 1$,

$\frac{1}{N} |\{n\in[N,2N] : \omega(n) > M(N)\}| = o(1)$,

where here $\omega(n)$ counts the number of prime divisors of $n$ without multiplicity. (So $\omega(4) = \omega(2) = 1$, while $\omega(6) = 2$.) The same results will be true if prime factors are counted with multiplicity however. (i.e. we consider $\Omega(n)$, where $\Omega(4) = 2$ for instance.)

More precise asymptotics can be obtained, especially easily for $M(N) = o(\log \log N)$, by using formula of Sathe and Selberg, and its extensions. These are uniform versions of the theorem of Landau which has been mentioned by quid. Where $M(N)$ grows like $\log \log N$ or faster, I'm afraid these formula become somewhat complicated, and I wouldn't expect a nice asymptotic expression (but I could be wrong). A reference is "On the number of prime factors of an integer" by Hildebrand and Tenenbaum, the easiest offshoot of which (due to Sathe) is that Landau's formula holds uniformly for $k = o(\log \log x)$. Formula (1.7) of Pomerance will give you (with a little patience) nice upper bounds.

The book of Tenenbaum already mentioned is also nice reference for some of these questions, as is chapter 7 of Montgomery and Vaughan's "Multiplicative Number Theory I". Kac's book is great for anyone to read, interested in these questions or not.

Improve this answer
$\endgroup$
2
$\begingroup$

For all such questions ( including the meta question of what the question really is) check out Gerald Tenenbaum's analytic and probabilistic number theory book. The book certainly talks at length about the statistics of the divisor function.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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