How divisible is the average integer? - MathOverflow

How divisible is the average integer?

2010-07-24T02:19:00Z

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:

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

Answer by Cam McLeman for How divisible is the average integer?

2010-07-24T02:43:29Z

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

Answer by Will Jagy for How divisible is the average integer?

2010-07-24T02:49:07Z

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