A309270 a(n) is the largest k such that the first k odd primes can be covered by n arithmetic progressions of primes.

3, 5, 10, 13, 18, 22, 24, 27, 31, 34, 39, 41, 45, 50, 55, 62, 64, 68, 73, 79, 81, 89, 91, 96, 99, 102, 107, 110, 115, 119, 124, 128, 133, 137, 142, 145, 151, 156, 162, 166, 170, 174, 177, 182, 185, 190, 193, 199, 203, 208

Offset: 1

Author

Dmitry Kamenetsky, Jul 20 2019

Keywords

• nonn
• more
• hard

Comments

Here we allow the arithmetic progressions to contain one or more terms.

The first 1000 odd primes can be covered with 221 arithmetic progressions of primes (see Links).

Finding the smallest n for a given k is a set covering problem with a binary variable for each arithmetic progression and a constraint for each of the first k odd primes. - Rob Pratt, Aug 26 2019

Examples

			1 arithmetic progression of primes is needed to cover the first 3 odd primes: (3,5,7). So a(1) = 3. Note that we cannot cover the first 4 odd primes with 1 arithmetic progression.
2 arithmetic progressions of primes are needed to cover the first 5 odd primes: (3,7,11), (5,13). So a(2) = 5.
3 arithmetic progressions of primes are needed to cover the first 10 odd primes: (3,17,31), (5,11,17,23,29), (7,13,19). So a(3) = 10.
4 arithmetic progressions of primes are needed to cover the first 13 odd primes: (3,13,23), (5,17,29,41), (7,19,31,43), (11,37). So a(4) = 13.
5 arithmetic progressions of primes are needed to cover the first 18 odd primes: (5,11,17,23,29), (7,19,31,43), (41,47,53,59), (13,37,61), (3,67). So a(5) = 18.
		

Links

• dxdy forum, Covering of primes with arithmetic progressions of primes (in Russian)
• Dmitry Kamenetsky, Covering of the first 1000 odd primes
• Carlos Rivera, Puzzle 963: minimal quantity of prime arithmetic progressions to cover the first primes

Crossrefs

Cf. A309095.

Extensions

a(27)-a(50) from Rob Pratt, Aug 26 2019