MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I don't know any number theory, so excuse me if the following notions have names that I'm not using.

For a positive natural number $n\in{\mathbb N}_{\geq 1}$, define $Log(n)\in{\mathbb N}$ to be the ``total exponent" of $n$. That is, in the prime factorization of $n$ it is the total number of primes being multiplied together (counted with multiplicity); for example $Log(20)=3.$ I'll define $log_2(n)\in{\mathbb R}$ to be the usual log-base-2 of $n$, so $log_2(20)\approx 4.32$.

One can think of $log_2(n)$ as "the most factors that $n$ could have" and think of $Log(n)$ as the number of factors it actually has. Define $D(n)$ to be the ratio of those quantities $$D(n)=\frac{Log(n)}{log_2(n)}\in(0,1],$$ and call it the divisibility of $n$. Hence, powers of 2 are maximally divisible, and large primes have divisibility close to 0. Another example: $D(5040)=\frac{8}{12.3}\approx 0.65$, whereas $D(5041)\approx\frac{2}{12.3}\approx 0.16$.

Question: What is the expected divisibility $D(n)$ for a positive integer $n$? That is, if we define $$E(p):=\frac{\sum_{n=1}^p D(n)}{p},$$ the expected divisibility for integers between 1 and $p$, I want to know the value of $$E:=lim_{p\rightarrow\infty}E(p),$$ the expected divisibility for positive integers.


  1. I once wrote and ran a program to determine $E(p)$ for input $p$. My recollection is a bit faint, but I believe it calculated $E(10^9)$ to be about $0.19.$

  2. A friend of mine who is a professor in number theory at a university once guessed that $E$ should be 0. I never understood why that would be.

share|cite|improve this question
This might help: – Anweshi Jul 24 '10 at 2:24
up vote 14 down vote accepted

Hopefully I've read all your notation correctly. If so, by playing (very) fast and loose with heuristics, I think your friend is right that the answer is 0.

Your function $Log(n)$ is the additive function $\Omega(n)$. According to the mathworld entry,

$\Omega(n)$ has been dubbed the "multiprimality of $n$" by Conway, and satisfies

$$ \Omega(n)\sim \ln\ln(n)+\text{mess}, $$ so (very roughly), $$ D(n)\sim \frac{\ln\ln(n)}{\ln(n)}, $$ and $$ E(p)\sim \frac{1}{p}\int_e^p \frac{\ln\ln n}{\ln n}dn. $$ This goes to 0 (very very slowly) as $p\rightarrow\infty$.

share|cite|improve this answer
Thanks to Dror Speiser for catching some errors in an earlier version of this. – Cam McLeman Jul 25 '10 at 12:02

Hardy and Wright define $$ \Omega (n) $$ to be the sum of the exponents. This is on page 354 in the fifth edition, section 22.10. Then we have Theorem 430, the "average order" of $ \Omega (n) $ is $ \log \log n .$ Then Theorem 431, same answer for the "normal order." $$ $$ I just saw Cam's answer, I think I will leave this anyway. The result on the average order answers your question. The book is "An Introduction to the Theory of Numbers."

share|cite|improve this answer

Your Answer


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.