%I #21 Aug 26 2019 18:44:16
%S 3,5,10,13,18,22,24,27,31,34,39,41,45,50,55,62,64,68,73,79,81,89,91,
%T 96,99,102,107,110,115,119,124,128,133,137,142,145,151,156,162,166,
%U 170,174,177,182,185,190,193,199,203,208
%N a(n) is the largest k such that the first k odd primes can be covered by n arithmetic progressions of primes.
%C Here we allow the arithmetic progressions to contain one or more terms.
%C The first 1000 odd primes can be covered with 221 arithmetic progressions of primes (see Links).
%C 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
%H dxdy forum, <a href="https://dxdy.ru/topic135734.html">Covering of primes with arithmetic progressions of primes</a> (in Russian)
%H Dmitry Kamenetsky, <a href="/A309270/a309270.txt">Covering of the first 1000 odd primes</a>
%H Carlos Rivera, <a href="https://www.primepuzzles.net/puzzles/puzz_963.htm">Puzzle 963: minimal quantity of prime arithmetic progressions to cover the first primes</a>
%e 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.
%e 2 arithmetic progressions of primes are needed to cover the first 5 odd primes: (3,7,11), (5,13). So a(2) = 5.
%e 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.
%e 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.
%e 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.
%Y Cf. A309095.
%K nonn,more,hard
%O 1,1
%A _Dmitry Kamenetsky_, Jul 20 2019
%E a(27)-a(50) from _Rob Pratt_, Aug 26 2019
|