# How divisible is the average integer?

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.

Hints:

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.

-
This might help: mathworld.wolfram.com/PrimeFactor.html –  Anweshi Jul 24 '10 at 2:24

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

-
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."

-