How divisible is the average integer? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T19:13:35Z http://mathoverflow.net/feeds/question/33162 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33162/how-divisible-is-the-average-integer How divisible is the average integer? David Spivak 2010-07-24T02:19:00Z 2010-07-25T00:41:03Z <p>I don't know any number theory, so excuse me if the following notions have names that I'm not using. </p> <p>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$.</p> <p>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 <em>divisibility of $n$</em>. 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$.</p> <p><strong>Question:</strong> 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 <em>expected divisibility for integers between 1 and $p$</em>, I want to know the value of $$E:=lim_{p\rightarrow\infty}E(p),$$ the <em>expected divisibility for positive integers</em>.</p> <p>Hints: </p> <ol> <li><p>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.$</p></li> <li><p>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.</p></li> </ol> http://mathoverflow.net/questions/33162/how-divisible-is-the-average-integer/33164#33164 Answer by Cam McLeman for How divisible is the average integer? Cam McLeman 2010-07-24T02:43:29Z 2010-07-25T00:41:03Z <p>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.</p> <p>Your function $Log(n)$ is the additive function $\Omega(n)$. According to the mathworld entry</p> <p><a href="http://mathworld.wolfram.com/PrimeFactor.html" rel="nofollow">http://mathworld.wolfram.com/PrimeFactor.html</a>,</p> <p>$\Omega(n)$ has been dubbed the "multiprimality of $n$" by Conway, and satisfies </p> <p>$$\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$.</p> http://mathoverflow.net/questions/33162/how-divisible-is-the-average-integer/33166#33166 Answer by Will Jagy for How divisible is the average integer? Will Jagy 2010-07-24T02:49:07Z 2010-07-24T02:49:07Z <p>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."</p>