Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.