Take the 2-minute tour ×

Although the answer to my question is probably implicit in the answers to the question asked here: Density of numbers having large prime divisors (formalizing heuristic probability argument), I can't extract it.

Problem: find decent bounds on the number of positive integers $n$, such that, for all primes $p$ dividing $n$, if $p^k$ exactly divides $n$, then $n > p^{k+1}$.

My idea for a first upper bound: if $n$ is divisible by a prime larger than $n^{\frac{1}{2}}$, it is immediately exluded that $n$ is of the above form, so the density can never be larger than $1 - \log{2}$

My idea for a first lower bound: if $n$ has two prime divisors between $n^{\frac{1}{3}}$ and $n^{\frac{1}{2}}$, then $n$ is of the above form. But I don't know the density of these numbers.

I am probably very happy with a (reference to) a proof/theorem that implies that we have a positive lower density, but asymptotics would be great.

EDIT (after the first response of GH, for which I'm thankful!): assume $n$ lies in some moduloclass, say $a \pmod{b}$. Can we still show a positive lower density, whatever the values of $a$ and $b$?

share|improve this question
Woett, I believe my proof can be easily adapted to residue classes, but I am lazy to check all the details. –  GH from MO Mar 31 '11 at 17:51
Here is how to deduce the statement for any residue class $a \pmod{b}$ using my construction. Choose $z > 5b$, then the construction yields a set of good integers $x < n \leq 2x$ coprime with $b$, which is of positive lower density. This set intersects at least one reduced residue class $c \pmod{b}$ with positive lower density. Multiply this intersection with the residue $1 \leq a\bar c \leq b$, where $\bar c$ stands for multiplicative inverse mod $b$. For $x > b^2$ the result is a set of good integers $x < n \leq 2bx$ in the residue class $a \pmod{b}$, which is of positive lower density. –  GH from MO Mar 31 '11 at 19:20
Thanks a lot! Not that it matters much, but isn't it for large $b$ better (in the sense that, when $b$ is actually known, we get a better lower bound on the number of good integers) to choose $z$ to be $\max{17, b}$ instead of $> 5b$? –  Woett Mar 31 '11 at 19:53
$z=\max(17,b)$ is fine, I was lazy typing and had to fit my message in a bounded box :-) Also I made no attempt to optimize any of my estimates. Perhaps I should add that the original problem naturally reduces to square-free numbers as the density of numbers with a square divisor exceeding $u^2$ is less than $1/u$ (think of $u$ as a large constant). Actually, this is how I was led to my solution. –  GH from MO Mar 31 '11 at 20:30

1 Answer 1

Your numbers have positive lower density. To see this let $z$ be a positive integer to be fixed later, and denote $$ c:=\prod_{p \leq z}(1-1/p). $$ Consider all square-free integers $x < n \leq 2x$ which are composed of primes $z < p \leq \sqrt{x}$. Note that these numbers satisfy the requirements. Their number, by a crude estimate, is at least $$ cx+O(1)-\sum_{\sqrt{x} < p \leq 2x}(cx/p+O(1)) - \sum_{z < p \leq \sqrt{2x}}(cx/p^2 +O(1)), $$ which is at least $$ c(1-\log 2-1/z+o(1))x. $$ That is, the lower density is at least $$ c(1-\log 2-1/z)/2.$$ For $z:=5$ the left hand side exceeds $0.0142$, while for $z:=17$ it exceeds $0.0223$.

EDIT: I improved slightly my original argument.

share|improve this answer

Your Answer


