OFFSET
1,1
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)
LINKS
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.
EXAMPLE
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, ... (End)
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)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
David W. Wilson, Nov 15 2006, revised Nov 25 2006
STATUS
approved