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.

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

Does a combination of proper arithmetic progressions behave Dirichlet-like?

Conjecture: If M is a non-empty finite collection of proper arithmetic progressions, and {x(n)} is the progression created by setting its n-th term equal to the n-th term of a (uniformly) randomly picked member of M, then the probability that {x(n)} contains a prime is unity.

So, my question is, is this in fact true?

Here's my attempt at a proof:

By induction on the cardinality, w, of M:

By Dirichlet's theorem, it is true for w = 1.

Suppose that it is true for w.

Let H be a collection of exactly (w + 1) proper arithmetic progressions.

Case 1. Suppose that one of the members of H has only finitely many terms occurring in {x(n)}. Then, by truncating this initial segment length from consideration, this case collapses to the case where the cardinality is w.

Case 2. Suppose that every member of H has infinitely many terms occurring in {x(n)}. Pick one of the members of H, and block out its terms. The remaining terms constitute a progression satisfying the induction hypothesis.

end of proof

share|cite|improve this question
You refer to $x(n)$ as an arithmetic progression, but there's no reason why it should be an arithmetic progression. – Gerry Myerson Sep 29 '13 at 0:47
@GerryMyerson: You're right. I've made the correction. – EsperantoSpeaker1 Sep 29 '13 at 12:43
up vote 2 down vote accepted

Let one of the progressions in $M$ have primes at locations $a_1,a_2,\dots$. The probability that $x(a_1)$ does not come from that progression is $1-(1/m)$, where $m$ is the number of progressions in $M$. The probability that none of the terms $x(a_1),x(a_2),\dots,x(a_r)$ comes from that progression is $(1-(1/m))^r$. This goes to zero as $r$ increases, so the probability that there is a prime in $x(n)$ is $1$.

share|cite|improve this answer

Your Answer


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.