Density of numbers not divisible by a large prime power - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T20:29:09Z http://mathoverflow.net/feeds/question/60189 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60189/density-of-numbers-not-divisible-by-a-large-prime-power Density of numbers not divisible by a large prime power Woett 2011-03-31T13:40:24Z 2011-03-31T17:37:40Z <p>Although the answer to my question is probably implicit in the answers to the question asked here: <a href="http://mathoverflow.net/questions/14664/density-of-numbers-having-large-prime-divisors-formalizing-heuristic-probability" rel="nofollow">http://mathoverflow.net/questions/14664/density-of-numbers-having-large-prime-divisors-formalizing-heuristic-probability</a>, I can't extract it.</p> <p>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}$. </p> <p>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}$</p> <p>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.</p> <p>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.</p> <p>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$?</p> http://mathoverflow.net/questions/60189/density-of-numbers-not-divisible-by-a-large-prime-power/60198#60198 Answer by GH for Density of numbers not divisible by a large prime power GH 2011-03-31T15:45:09Z 2011-03-31T16:05:19Z <p>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 &lt; n \leq 2x$ which are composed of primes $z &lt; 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} &lt; p \leq 2x}(cx/p+O(1)) - \sum_{z &lt; 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$.</p> <p>EDIT: I improved slightly my original argument.</p>