Take the 2-minute tour ×
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.

Let $S$ be an finite or infinite subset of the primes. Let $f(x)=1$ if $x$ has no factors in $S$. If not, $f(x)=0$. Is there a way to calculate the limit $\displaystyle\sum_{n=1}^{x} f(n)/x$, as $x$ grows big?

Examples;
S contains all primes of form $2778t+79$
S={2,5,17}

share|improve this question
    
You should clarify "$2778t + 79$." What are the restrictions on $t$? Furthermore, can you show there are an infinity of primes of the form $2778t + 79$? –  ThisIsNotAnId Jun 4 '12 at 0:01
    
Since $\mathrm{gcd}(2778,79)=1$, then by Dirichlet theorem (en.wikipedia.org/wiki/…) this progression contains infinitely many primes –  Norbert Jun 4 '12 at 0:04
    
For finite set i think its easy, because f(n) is periodic, right? –  Sigma23 Jun 4 '12 at 0:06

1 Answer 1

up vote 2 down vote accepted

Yes, for a finite set it's easy. For your example, $S=\{{2,5,17\}}$, $x$ has no factors in $S$ if and only if $x$ is relatively prime to $170=2\times5\times17$. The number of integers less than and relatively prime to 170 is $\phi(170)=1\times4\times16=64$, and then it's periodic beyond 170, so your limit is $64/170$, also known as $32/85$.

For infinite sets of primes, life is more difficult. I suspect that for the infinite set of primes in an arithmetic progression the limit is zero, that is, almost all big numbers have a factor in every arithmetic progression, but I can't provide a reference for this.

EDIT: A well-known example. The numbers that can be written as a sum of two squares, that's known to be a set of density zero (see, e.g., http://www.math.niu.edu/~rusin/known-math/93_back/2squares). Now those include all the numbers that have no prime factors of the form $4t+3$, so it follows that the set of numbers with no prime factor $4t+3$ has density zero.

share|improve this answer

Your Answer

 
discard

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

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