Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $d(n)$ denote the largest divisor of $n$ less than $\sqrt{n}$. Are there good lower bounds for $d$ that hold for almost all natural numbers?

More precisely, is there a function $f$, say $f(n)=\frac{\sqrt{n}}{(\log{n})^{100}}$, such that for large $x$, $d(n)\geq f(n)$ holds for almost all $n\leq x$.

share|improve this question
There is some work of Knuth and Trabb-Pardo, which says what the size of the largest prime factor of all numbers below x is expected to be (or something similar and pertinent to your question. I think their work implies that for almost all n less than x, your d(n) is less than n^0.4. Gerhard "Ask Me About System Design" Paseman, 2013.04.27 –  Gerhard Paseman Apr 27 '13 at 21:22
I believe there is a big difference between the largest prime factor and the largest divisor - I think it is known that the average value of $d(n)$ when $1\leq n \leq x$ is at least $\sqrt{x}/log(x)^C$ for some constant $C$. –  trebe Apr 27 '13 at 22:16
The state of the art for questions such as this is Kevin Ford's paper arxiv.org/pdf/math/0401223v5.pdf. For the $f(n)$ given in the question, or in fact any $f(n)$ with $f(n) = n^{1/2+o(1)}$, one gets from Ford's work that the set of $n$ with $d(n) \ge f(n)$ has asymptotic density zero. –  Anonymous Apr 27 '13 at 22:34
@Anonymous : Could one get asymptotic density one from say $f(n)=n^{1/2 - \epsilon}$; if not, do you know how slow $f$ would have to be to get asymptotic density one? –  trebe Apr 27 '13 at 23:09
From Ford's paper, cited above, Theorem 1(v): when $\epsilon$ is sufficiently small, you still don't get density 1 from $f(n) = n^{1/2-\epsilon}$. You do get density 1 from $f(n) = n^{1/4}$, although I can't immediately tell whether that's the best exponent or not. –  Greg Martin Apr 28 '13 at 2:47

1 Answer 1

If $n$ has a prime factor $p<y$ then $pd(n) > \sqrt{n}$ so $d(n) > \sqrt{n}/y$. The number of integers without a prime factor less than $y$ (for suitably small $y$) is approximately $x\prod_{p<y} (1-1/p)$ which in turn is approximately $cx/\log y$. Taking $y = (\log x)^{a}$, for some $a$ probably works ok.

share|improve this answer
Dear Felipe, Apologies if I've misunderstood your answer but I'm not sure how your reasoning works. Why must $pd(n)>\sqrt{n}$ hold? If $n=2p$ for some large prime $p$, then $d(n)=2$ and it is certainly not the case that $2d(n)>\sqrt{n}$. –  trebe Apr 27 '13 at 22:08
@trebe: My mistake. If $pd(n)$ is itself a divisor of $n$, then my argument works. As your example shows, this is not always the case. –  Felipe Voloch Apr 27 '13 at 22:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.