Median largest-prime-factor - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T16:01:20Z http://mathoverflow.net/feeds/question/57395 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57395/median-largest-prime-factor Median largest-prime-factor Greg Martin 2011-03-04T19:59:17Z 2012-07-03T08:41:47Z <p>Let $P(n)$ denote the largest prime factor of $n$. For any integer $x\ge2$, define the median $$M(x) = \text{the median of the set }{P(2), P(3), \dots, P(x) }.$$ Classical results of Dickman and de Bruijn show that the median is <i>roughly</i> $x^{1/\sqrt{e}}$. More specifically, I think that the Dickman-de Bruijn rho-function approach can show the following: for any function $f(x)$ tending to infinity with $x$, the median $M(x)$ is between $x^{1/\sqrt{e}}/f(x)$ and $x^{1/\sqrt{e}}f(x)$ for all sufficiently large $x$.</p> <p>But I got to thinking the other day: is there a way to determine how the median compares to $x^{1/\sqrt{e}}$ specifically? In other words, which one of the following is true?</p> <ol> <li> For all sufficiently large $x$, we have $M(x) \lt x^{1/\sqrt{e}}$. <li> Each inequality $M(x) \lt x^{1/\sqrt{e}}$ and $M(x) \ge x^{1/\sqrt{e}}$ holds for arbitrarily large $x$. <li> For all sufficiently large $x$, we have $M(x) \ge x^{1/\sqrt{e}}$. </ol> http://mathoverflow.net/questions/57395/median-largest-prime-factor/78815#78815 Answer by Greg Kuperberg for Median largest-prime-factor Greg Kuperberg 2011-10-22T03:25:59Z 2011-10-22T03:25:59Z <p>This is one of many questions that has been answered in the comments, so I will just summarize the answer with a CW posting: $M(x) &lt; x^{1/\sqrt{e}}$ according to the poster Greg Martin. In a computer search, the ratio seems to converge to roughly $0.74$ for $x$ up to a million. On the other hand, it doesn't converge very quickly and might possibly not converge at all. All that was have from the original posting is that the lim sup of the ratio is finite (and at most 1 according to the answer) while the lim inf is positive.</p> http://mathoverflow.net/questions/57395/median-largest-prime-factor/101222#101222 Answer by Eric Naslund for Median largest-prime-factor Eric Naslund 2012-07-03T08:41:47Z 2012-07-03T08:41:47Z <p>I posted <a href="http://arxiv.org/abs/1207.0232" rel="nofollow">a paper to the arXiv</a> which deals with this question along with some other things.</p> <p>Using some results regarding either the mean of $\omega(n)$, or integers without large prime factors, we can prove that $$M(x)=e^{(\gamma-1)/\sqrt{e}}x^{1/\sqrt{e}}\left(1+O\left(\frac{1}{\log x}\right)\right),$$ where $\gamma$ is the <a href="http://en.wikipedia.org/wiki/Euler%25E2%2580%2593Mascheroni_constant" rel="nofollow">Euler Mascheroni constant.</a></p> <p>More specifically, if we let $\text{li}_f(x)=\int_2^x \frac{\{x/t\}}{\log t} dt$, then $$M(x)=x^{\frac{1}{\sqrt{e}}\exp\left(-\frac{\text{li}_f(x)}{x}\right)}\left(1+O\left(e^{-c\sqrt{\log x}}\right)\right).$$ (In case the TeX is not readable, the exponent of $x$ in the above equation is $\frac{1}{\sqrt{e}}\exp\left(-\frac{\text{li}_f(x)}{x}\right)$.) </p> <p>This function $\text{li}_f(x)$ has the asymptotic expansion $$\text{li}_f(x)=c_0 \frac{x}{\log x}+c_1 \frac{x}{\log^2 x}+\cdots+c_{k-1} \frac{(k-1)!x}{\log^k x}+O\left(\frac{x}{\log^{k+1}(x)}\right),$$</p> <p>where $$c_k=1-\sum_{j=0}^k\frac{\gamma_k}{k!},$$ and $\gamma_k$ denotes the $k^{th}$ <a href="http://en.wikipedia.org/wiki/Stieltjes_constants" rel="nofollow">Stieltjes constant</a>.</p>