Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the asymptotic order of numbers divisible by no primes except those of the form $an+b$ ($a$, $b$ fixed)?

Surely (except for the trivial cases) they are of order strictly between that of he primes and of all numbers.

share|cite|improve this question
I would guess something like $n/\sqrt{\log n}$. – André Nicolas Apr 16 '12 at 23:01
@AndréNicolas: That would be my guess as well. Is this in Hardy & Wright, perhaps? – Charles Apr 16 '12 at 23:08
Don't own it, alas, and don't remember seeing the result there. However, the above is what one gets for sums of two squares, and the numbers expressible as a sum of two squares are a constant multiple away from numbers divisible only by $2$ or primes of the form $4k+1$. My guess is that a partial imitation of the proof of the two squares result would do the job. – André Nicolas Apr 16 '12 at 23:16
Given a subset of the primes $\mathcal{S}$ with positive density $\alpha$, I believe the asymptotics for the counting function for the integers formed by products of those primes will be $$\sim C \frac{x}{(\log x)^{1-\alpha}},$$ for some constant $C$. The idea is that the function $$\zeta_\mathcal{S}(s)=\prod_{p\in\mathcal{S}} (1-p^{-s})^{-1}$$ will have a singularity of the form $\frac{1}{(s-1)^{\alpha}}$ and then integrating $ \frac{x^s}{(s-1)^{\alpha}}dx$ gives a main term of $$\frac{x}{(\log x)^{1-\alpha}}.$$ – Eric Naslund Apr 17 '12 at 12:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.