cp's OEIS Frontend

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

%I A123556 #65 Aug 16 2025 06:19:52
%S A123556 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,
%T A123556 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,
%U A123556 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
%N A123556 Number of elements in longest possible arithmetic progression of primes with difference n.
%C A123556 Length of n-th row of A124064.
%C A123556 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
%C A123556 From _Bernard Schott_, Feb 24 2023: (Start)
%C A123556 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.
%C A123556 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.
%C A123556 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.
%C A123556 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}.
%C A123556 Terms are ordered without repetition in A173919. (End)
%H A123556 Diophante, <a href="http://www.diophante.fr/problemes-par-themes/arithmetique-et-algebre/a1-pot-pourri/3940-a1880-np-en-pa">A1880. NP (Nombres Premiers) en PA (Progression Arithmétique)</a> (in French).
%H A123556 Wikipedia, <a href="https://en.wikipedia.org/wiki/Primes_in_arithmetic_progression">Primes in arithmetic progression</a>.
%H A123556 <a href="/index/Pri#primes_AP">Index entries for sequences related to primes in arithmetic progressions</a>.
%F A123556 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.
%e A123556 a(1) = 2 for the AP (arithmetic progression) (2, 3) with A342309(1) = 2.
%e A123556 a(2) = 3 for the AP (3, 5, 7) with A342309(2) = 3.
%e A123556 a(3) = 2 for the AP (2, 5) with A342309(3) = 2.
%e A123556 a(6) = 5 for the AP (5, 11, 17, 23, 29) with A342309(6) = 5.
%e A123556 a(7) = 1 for the AP (2) with A342309(7) = 2.
%e A123556 a(18) = 4 for the AP (5, 23, 41, 59) with A342309(18) = 5.
%e A123556 a(30) = 6 for the AP (7, 37, 67, 97, 127, 157) with A342309(30) = 7.
%e A123556 a(150) = 7 for the AP (7, 157, 307, 457, 607, 757, 907) with A342309(150) = 7.
%e A123556 From _Bernard Schott_, Feb 25 2023: (Start)
%e A123556 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.
%e A123556 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, ...
%e A123556 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)
%o A123556 (PARI) A053669(n) = forprime(p=2, , if(n%p, return(p)));
%o A123556 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
%Y A123556 Cf. A007921, A053669, A124064, A342309.
%Y A123556 Cf. A002110, A151799, A173919.
%Y A123556 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).
%K A123556 nonn
%O A123556 1,1
%A A123556 _David W. Wilson_, Nov 15 2006, revised Nov 25 2006