Skip to main content
http -> https (the question was bumped anyway)
Source Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Let $x$ be such that $\pi(x) \sim \frac{x}{\log x} \sim r$, so that $P_r$ is about $e^x$. Let $\Psi(x,y)$ be the de Bruijn, function, the number of $y$-smooth$y$-smooth numbers less than or equal to $x$. So a crude upper bound for the quantity in question is about

$$ \Psi(e^{x/2},x) - \Psi(e^{x/2}/2,x). $$

Out of these numbers (call the set of these numbers $X$) we want to get the squarefree ones. The proportion of squarefree numbers in all the integers is $1/\zeta(2)$ so it is tempting to use $|X|/\zeta(2)$ or $|X|\prod_{p\leq x}\left(1-1/p^2\right)$ as a crude first approximation, though I'm not sure how far off it is. The thing is that one is dealing here with only $x$-smooth numbers. Perhaps for each $p \leq z \ll x$ for suitable $z$ one can estimate the size of the subset of $X$ that is in $p^2\mathbb{Z}$, then use a simple inclusion-exclusion sieve to estimate the size of the subset of $X$ of numbers that, if they are divisible by prime squares $p^2$, must have $z \leq p\leq x$. Or, use more powerful sieve methods. (Guessing that sieving for squarefree numbers should be very similar to sieving for primes.)

Good references:

A. Granville, Smooth numbers: computational number theory and beyond, Algorithmic Number Theory, MSRI Publications, Volume 44, 2008.

T. Tao's blog, 254B, Notes 7: Sieving and expanders.

Let $x$ be such that $\pi(x) \sim \frac{x}{\log x} \sim r$, so that $P_r$ is about $e^x$. Let $\Psi(x,y)$ be the de Bruijn, function, the number of $y$-smooth numbers less than or equal to $x$. So a crude upper bound for the quantity in question is about

$$ \Psi(e^{x/2},x) - \Psi(e^{x/2}/2,x). $$

Out of these numbers (call the set of these numbers $X$) we want to get the squarefree ones. The proportion of squarefree numbers in all the integers is $1/\zeta(2)$ so it is tempting to use $|X|/\zeta(2)$ or $|X|\prod_{p\leq x}\left(1-1/p^2\right)$ as a crude first approximation, though I'm not sure how far off it is. The thing is that one is dealing here with only $x$-smooth numbers. Perhaps for each $p \leq z \ll x$ for suitable $z$ one can estimate the size of the subset of $X$ that is in $p^2\mathbb{Z}$, then use a simple inclusion-exclusion sieve to estimate the size of the subset of $X$ of numbers that, if they are divisible by prime squares $p^2$, must have $z \leq p\leq x$. Or, use more powerful sieve methods. (Guessing that sieving for squarefree numbers should be very similar to sieving for primes.)

Good references:

A. Granville, Smooth numbers: computational number theory and beyond, Algorithmic Number Theory, MSRI Publications, Volume 44, 2008.

T. Tao's blog, 254B, Notes 7: Sieving and expanders.

Let $x$ be such that $\pi(x) \sim \frac{x}{\log x} \sim r$, so that $P_r$ is about $e^x$. Let $\Psi(x,y)$ be the de Bruijn, function, the number of $y$-smooth numbers less than or equal to $x$. So a crude upper bound for the quantity in question is about

$$ \Psi(e^{x/2},x) - \Psi(e^{x/2}/2,x). $$

Out of these numbers (call the set of these numbers $X$) we want to get the squarefree ones. The proportion of squarefree numbers in all the integers is $1/\zeta(2)$ so it is tempting to use $|X|/\zeta(2)$ or $|X|\prod_{p\leq x}\left(1-1/p^2\right)$ as a crude first approximation, though I'm not sure how far off it is. The thing is that one is dealing here with only $x$-smooth numbers. Perhaps for each $p \leq z \ll x$ for suitable $z$ one can estimate the size of the subset of $X$ that is in $p^2\mathbb{Z}$, then use a simple inclusion-exclusion sieve to estimate the size of the subset of $X$ of numbers that, if they are divisible by prime squares $p^2$, must have $z \leq p\leq x$. Or, use more powerful sieve methods. (Guessing that sieving for squarefree numbers should be very similar to sieving for primes.)

Good references:

A. Granville, Smooth numbers: computational number theory and beyond, Algorithmic Number Theory, MSRI Publications, Volume 44, 2008.

T. Tao's blog, 254B, Notes 7: Sieving and expanders.

Source Link
user22202
  • 548
  • 4
  • 7

Let $x$ be such that $\pi(x) \sim \frac{x}{\log x} \sim r$, so that $P_r$ is about $e^x$. Let $\Psi(x,y)$ be the de Bruijn, function, the number of $y$-smooth numbers less than or equal to $x$. So a crude upper bound for the quantity in question is about

$$ \Psi(e^{x/2},x) - \Psi(e^{x/2}/2,x). $$

Out of these numbers (call the set of these numbers $X$) we want to get the squarefree ones. The proportion of squarefree numbers in all the integers is $1/\zeta(2)$ so it is tempting to use $|X|/\zeta(2)$ or $|X|\prod_{p\leq x}\left(1-1/p^2\right)$ as a crude first approximation, though I'm not sure how far off it is. The thing is that one is dealing here with only $x$-smooth numbers. Perhaps for each $p \leq z \ll x$ for suitable $z$ one can estimate the size of the subset of $X$ that is in $p^2\mathbb{Z}$, then use a simple inclusion-exclusion sieve to estimate the size of the subset of $X$ of numbers that, if they are divisible by prime squares $p^2$, must have $z \leq p\leq x$. Or, use more powerful sieve methods. (Guessing that sieving for squarefree numbers should be very similar to sieving for primes.)

Good references:

A. Granville, Smooth numbers: computational number theory and beyond, Algorithmic Number Theory, MSRI Publications, Volume 44, 2008.

T. Tao's blog, 254B, Notes 7: Sieving and expanders.