[Math] How divisible is the average integer

factorizationnt.number-theory

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.

Best Answer

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

http://mathworld.wolfram.com/PrimeFactor.html,

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

Related Question