Density of numbers not divisible by a large prime power

2011-03-31T13:40:24Z

Although the answer to my question is probably implicit in the answers to the question asked here: http://mathoverflow.net/questions/14664/density-of-numbers-having-large-prime-divisors-formalizing-heuristic-probability, 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$?

Answer by GH for Density of numbers not divisible by a large prime power

2011-03-31T15:45:09Z

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.

Density of numbers not divisible by a large prime power - MathOverflow

Density of numbers not divisible by a large prime power

Answer by GH for Density of numbers not divisible by a large prime power