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

For each prime $p$, we can consider the set of arithmetic progression made of primes that include $p$: $A_p=\{\{a_i\}_{i=1}^k \mid \text{$\{a_i\}_{i=1}^k$ is an arithmetic progression, each $a_i$ is a prime, and $p=a_j$ for some $j$}\}$. Since there is no infinite arithmetic progression of primes (since for $a+nb$, $a \mid (a+na)$) we have a particular sequence in $A_p$ that is the longest among sequences in $A_p$. We may call its length $\alpha(p)$. Has this function been studied? Or does it have trivial explicit values?

share|cite|improve this question
Since there is no infinite integer, is there a particular integer that is the largest? – Erick Wong Dec 5 '12 at 4:02
(1)What is a "prime sequence"? Since you mentioned arithmetic sequences (AS), do you mean here an AS with common difference a prime? (2) What is that "particular seq. that is the longest"? How is it defined, how do we know it is finite...In short, what's going on here?! – DonAntonio Dec 5 '12 at 4:17
Keep editing, you still haven't dealt with the questions raised in the comments. – Gerry Myerson Dec 5 '12 at 5:33
This is frustrating and I'm voting to close this question because of "this is not a real question". I thought maybe I was missing something yet after reading other people's comments I'm almost sure I am not. Here's a list of incomprehensible (for me) stuff: (1) what's "sequences made of prime that include p"? Of course, there are infinite many of this if we translate this as it is; (2) What have to do arithmetic sequences with all this? (3) Why there must be some seq. as in (1) that is "the longest"? All of them are infinite!! – DonAntonio Dec 6 '12 at 11:40
@DonAntonio: I agree that the question is badly phrased, but all your concerns are solved by replacing the word "sequences" in the first line with "arithmetic progressions", as the title of the question suggests. – Martin Argerami Dec 6 '12 at 12:40
up vote 2 down vote accepted

I'll assume you are considering only positive primes. If a prime progression (of length $>1$) contains $p$, then the common difference cannot be divisible by $p$. This gives an a priori upper bound of $2p-1$ on the length of the progression.

One can sharpen this to an upper bound of $p$ by balancing the fact that the common difference can't be large (else there is no room before $p$) against the fact that it must be divisible by many small primes (else it cannot go much further than $p$).

So there is an upper bound of $\alpha(p)\le p$. This is generally believed to be best possible since the standard conjectures (e.g. Schinzel's Hypothesis H) would imply that $\alpha(p)=p$. On the other hand, lower bounds are very hard to come by. We do not even know, for instance, that $\alpha(p) > 2$ for all odd primes $p$ (however it is known to be true for the vast majority of primes by Montgomery and Vaughan's work on the exceptional set of Goldbach's conjecture).

share|cite|improve this answer
I wonder what do you think you're answering to: you write "a prime progression": what is that, according to the OP? Can you tell? And why do you think that a "prime progression", as perhaps was defined by the OP, has or must be an arithmetic one? It obviously cannot be so. – DonAntonio Dec 6 '12 at 11:42
I may be slightly confused, but why does there need to be room 'before' $p$? What if $p$ is the first member of the progression? – Steven Stadnicki Dec 10 '12 at 19:48
@StevenStadnicki Perhaps that was poorly worded. I simply meant that the larger you make the common difference, the less room there is to place terms before $p$. The tradeoff indeed heavily favours $p$ being the first member of the progression. – Erick Wong Dec 10 '12 at 20:02
Ahhh, now I understand - I'd misunderstood the argument in the first paragraph and not caught on to the residue-classes. It makes much more sense now. – Steven Stadnicki Dec 10 '12 at 22:50

Here are a few thoughts on your problem, going to the intent of the question rather than the content.

For example, any prime arithmetic progression containing $2$ will have length at most $2$... and so is boring.

There are arbitrarily long arithmetic progressions consisting only of primes. This is the topic of the Green Tao Theorem. Their proof is not at all constructive, and it seems that a construction would be radically more difficult. What you are asking for is strictly harder than this result, and is likely beyond current methods.

share|cite|improve this answer
I must be missing something pretty elementary here: you wrote "There are arbitrarily long arithmetic progressions consisting only of primes". Could you give 1-2 examples of these or, at least, of the first few elements of some of these? I must be understanding something different somewhere and it's driving me nuts. Thanks – DonAntonio Dec 6 '12 at 12:52
@DonAntonio The longest explicitly-known progression of primes is $43142746595714191 + 23681770·23\#\cdot n$ with length $26$. This was found by PrimeGrid (the lucky machine was a Sony PlayStation 3!) – Erick Wong Dec 6 '12 at 14:51
@DonAntonio: No, I can't, since the Green Tao Theorem is not constructive. None are known. – mixedmath Dec 6 '12 at 17:05
@mixedmath I'm curious what you'd expect an example to look like... – Erick Wong Dec 6 '12 at 17:46
@Erick: That's a very good question. If we wanted a progression of $n$ primes, we'd need the common difference to be divisible by approximately the first $n$ primes. But one would anticipate that it would have to be larger to account for the growing expected difference between primes. As for the starting prime... since the difference is at least the approximate size of the product of the first $n$ primes, it would likely have to be much larger than the $n$th prime. How large? I have no idea. – mixedmath Dec 7 '12 at 4:23

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.