14
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

15
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ A note for anybody who is coming here years later: $\Omega(n)\sim ln(ln(n))$ is true, no need for the +mess; you only need that for a more detailed asymptotic relationship if that is what you so desire. $\endgroup$
    – Milo Moses
    Oct 29, 2021 at 22:49
8
$\begingroup$

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

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