A123556 Number of elements in longest possible arithmetic progression of primes with difference n.

2, 3, 2, 3, 2, 5, 1, 3, 2, 3, 2, 5, 1, 3, 2, 2, 2, 4, 1, 3, 2, 2, 1, 4, 1, 2, 2, 3, 2, 6, 1, 2, 1, 3, 2, 4, 1, 3, 2, 3, 2, 5, 1, 2, 2, 2, 1, 5, 1, 3, 2, 2, 1, 4, 1, 2, 2, 2, 2, 6, 1, 2, 1, 3, 2, 4, 1, 3, 2, 2, 2, 4, 1, 2, 1, 2, 2, 4, 1, 3, 2, 2, 1, 4, 1, 2, 2, 2, 1, 6, 1, 2, 1, 3, 2, 5, 1, 3, 2, 2, 2, 4, 1, 3, 2

Offset: 1

Author

David W. Wilson, Nov 15 2006, revised Nov 25 2006

Keywords

• nonn

Comments

Length of n-th row of A124064.

The corresponding smallest term of the first such longest possible arithmetic progression of primes with common difference n is A342309(n). - Bernard Schott, Oct 12 2021

From Bernard Schott, Feb 24 2023: (Start)

For every positive integer n, there exists a smallest prime p that does not divide n = A053669(n); then, an AP of k primes with common difference n cannot contain more terms than this value of p so k <= p, moreover, the longest possible APs of primes have p-1 or p elements.

Proof: consider the AP of p elements (q, q+n, q+2*n, q+3*n, ..., q+(p-1)*n) with common difference n, q prime and p is the smallest prime that does not divide n; the modular arithmetic modulo p gives this set of remainders with p elements: {0, 1, 2, ..., p-1}, so there is always a multiple of p in each such AP with p terms, hence length k of longest possible AP of primes is >= p-1 and <= p.

Moreover, when the longest possible AP contains k = p elements, then this unique longest AP must start with p (corresponding to remainder = 0) and the common difference n is a multiple of A151799(p)# and not of p#, where # = primorial = A002110.

Now, always with a common difference n, when the longest possible AP contains k = p-1 elements, these longest APs with p-1 primes can start with p or with another prime q != p, and there are infinitely many such longest APs with p-1 terms (see Properties in Wikipedia link) in this case. When this AP starts with p, the set of remainders is {0, 1, ..., p-2} and when this AP starts with q, then the set of remainders becomes {1, 2, ..., p-1}.

Terms are ordered without repetition in A173919. (End)

Examples

			a(1) = 2 for the AP (arithmetic progression) (2, 3) with A342309(1) = 2.
a(2) = 3 for the AP (3, 5, 7) with A342309(2) = 3.
a(3) = 2 for the AP (2, 5) with A342309(3) = 2.
a(6) = 5 for the AP (5, 11, 17, 23, 29) with A342309(6) = 5.
a(7) = 1 for the AP (2) with A342309(7) = 2.
a(18) = 4 for the AP (5, 23, 41, 59) with A342309(18) = 5.
a(30) = 6 for the AP (7, 37, 67, 97, 127, 157) with A342309(30) = 7.
a(150) = 7 for the AP (7, 157, 307, 457, 607, 757, 907) with A342309(150) = 7.
From _Bernard Schott_, Feb 25 2023: (Start)
For n = 12, p = A053669(12) = 5 and the AP (5, 17, 29, 41, 53) has 5 elements that are primes (the next should be 65 = 5*13), so a(12) = 5. This AP is the unique longest possible AP of primes with a common difference n = 12.
For n = 30, p = A053669(30) = 7 and the AP (7, 37, 67, 97, 127, 157) has 7-1 = 6 elements that are primes (the next should be 187 = 11*17) so a(30) = 6. Also, there are infinitely many such longest APs with common difference 30 and 6 elements. These other longest APs start with primes q that are > p = 7. The first few next q are 107, 359, 541, 2221, 6673, 7457, ...
For n = 60, p = A053669(60) = 7 and the longest AP that starts with 7 is (7, 67, 127) has only 3 elements that are primes (the next should be 187 = 11*17) so a(60) = 6. Also, there are infinitely many such longest APs with common difference 60 and 6 elements. All these longest APs start with primes q that are > p = 7. The first few such q are 11, 53, 641, 5443, 10091, 12457, ... and the smallest such AP is (11, 71, 131, 191, 251, 311). (End)
		

Links

• Diophante, A1880. NP (Nombres Premiers) en PA (Progression Arithmétique) (in French).
• Wikipedia, Primes in arithmetic progression.
• Index entries for sequences related to primes in arithmetic progressions.

Crossrefs

Cf. A007921, A053669, A124064, A342309.

Cf. A002110, A151799, A173919.

Sequences such that a(n) = k iff ...: A007921 (a(n)=1), A359408 (a(n)=2), A206037 (a(n)=3), A359409 (a(n)=4), A206039 (a(n)=5), A359410 (a(n)=6), A206041 (a(n)=7), A360146 (a(n)=10), A206045 (a(n)=11).

Programs

PARI

A053669(n) = forprime(p=2, , if(n%p, return(p)));
a(n) = my(p=A053669(n)); for (i=1, p-1, if (!isprime(p+i*n), return(p-1))); p; \\ Michel Marcus, Feb 26 2023

Formula

Assume the k-tuples conjecture. Let p = A053669(n). If the arithmetic progression of p elements starting at p with difference n consists of primes, then a(n) = p, otherwise a(n) = p-1.