5
$\begingroup$

Here are the numbers whose prime factors all congruent to $\pm 1\pmod 8$: http://oeis.org/A058529

My questions are:

(1) What is the order of growth of these numbers? That is, what is the order of magnitude of the $n$th smallest among them?

(2) For the numbers whose prime factors are all congruent to $\pm 3\pmod 8$, is the order of growth the same as in (1)?

$\endgroup$
7
$\begingroup$

This is an old question (and according to this MO question, the result you seek was proven by Landau). In particular, it follows from this that if $S$ is a set of arithmetic progressions containing a density $1/2$ set of the primes, then number of $n \leq x$ all of whose prime factors in $S$ is asymptotic to some constant times $C \frac{x}{\sqrt{\log(x)}}$. This implies that the $n$th positive integer $q_{n}$ all of whose prime factors are $\pm 1 \pmod{8}$ satisfies $q_{n} \sim C_{1} n \sqrt{\log(n)}$. Similarly, if $r_{n}$ is the $n$th positive integer all of whose prime factors are $\pm 3 \pmod{8}$, then $r_{n} \sim C_{2} n \sqrt{\log(n)}$.

If you are looking for a modern treatment of this, which will enable you to compute the constants $C_{1}$ and $C_{2}$, this result is stated in Cojocaru and Murty's book "An introduction to sieve methods and their applications", but I don't have my copy at home right now, so I can't tell you exactly where in the book to look.

$\endgroup$
  • $\begingroup$ Shouldn't this be $q_n \sim C_1 n \sqrt{\log(n)}$ (and similarly for $r_n$)? $\endgroup$ – Michael Stoll Apr 21 '18 at 15:39
  • $\begingroup$ Indeed it should be. I will edit the answer. $\endgroup$ – Jeremy Rouse Apr 21 '18 at 15:40
  • $\begingroup$ Can it be generalized to sets of arithmetic progressions containing a density $ \delta >0$ of the primes ? $\endgroup$ – Sylvain JULIEN Apr 21 '18 at 15:55
  • 3
    $\begingroup$ Yes, and in that case the number of such integers $\leq x$ is $\sim C \frac{x}{\log(x)^{1-\delta}}$. $\endgroup$ – Jeremy Rouse Apr 21 '18 at 16:02
  • $\begingroup$ Thank you. That's precisely what I expected but I feared it might be too naive. $\endgroup$ – Sylvain JULIEN Apr 21 '18 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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