cp's OEIS Frontend

A072753 Maximum gap in two-stage prime-sieves.

%I A072753 #79 Aug 02 2017 13:09:57
%S A072753 2,4,10,24,31,42,60,74,94,117,148,173,213,236,275,316,364,409,436
%N A072753 Maximum gap in two-stage prime-sieves.
%C A072753 From _John F. Morack_, Dec 20 2012: (Start)
%C A072753 There is a relationship between this sequence and Goldbach's Conjecture.
%C A072753 If you consider that you are "sieving" from the even number down and from 1 up, then if the even number is a power of 2 this is exactly a two-stage sieve, but you must include the 3, so each term is multiplied by 3. For other even numbers, all two-stage sieves including 3 will over-exclude numbers, so if anything is left after the sieve, it must be prime, excluding the number 1.
%C A072753 Consider the following: Let p be the largest prime < sqrt(2N), further let p be the m-th prime. Let's deal with the m-th term in the sequence a(m). If a(m)*3 < (N - 2) for all N > K for some constant K, there is a set of two primes that sum to 2N. (End)
%C A072753 From _Giovanni Resta_, Aug 06 2015: (Start)
%C A072753 a(n) is the maximal value m such that there exist n-2 pairs 0 <= a_i, b_i < prime(i) for each 3 <= i <= n, such that each number between 1 and m is either a_i or b_i mod prime(i). The condition a(k) >= m can be verified by solving an integer linear programming problem with binary variables x_i_j, where i ranges between 3 and k and j ranges between 0 and prime(k)-1, and x_i_j = 1 if a_i = j or b_i = j.
%C A072753 For a(11) = 148 the pairs are 5 (1,3) 7 (4,5) 11 (2,4) 13 (9,10) 17 (1,12) 19 (1,15) 23 (4,7) 29 (7,26) 31 (11,14) 37 (17,21) 41 (3,23).
%C A072753 For a(12) = 173 they are 5 (1,3) 7 (1,2) 11 (5,7) 13 (2,4) 17 (1,8) 19 (7,14) 23 (1,20) 29 (10,19) 31 (1,12) 37 (13,18) 41 (29,34) 43 (1,36).
%C A072753 For a(13) = 213 they are 5 (1,3), 7 (1,2), 11 (7,9) 13 (1,11) 17 (2,9) 19 (4,14) 23 (3,9) 29 (16,25) 31 (4,5) 37 (10,34) 41 (17,28) 43 (36,39) 47 (12,14).
%C A072753 For a(14) = 236 they are 5 (1,3) 7 (3,5) 11 (4,5) 13 (4,9) 17 (5,14) 19 (7,10) 23 (11,17) 29 (3,26) 31 (3,19) 37 (5,25) 41 (2,31) 43 (1,34) 47 (3,41) 53 (20,32). (End)
%C A072753 a(17) and a(18) were calculated using _Giovanni Resta_'s ILP approach with models generated from all combinations of primes to 17. We are looking for a GPU approach. GLPK was used to process the auto-generated models. - _John F. Morack_ is solely responsible for the computation work. - _John F. Morack_, Jan 03 2016
%C A072753 a(19) verification computation was completed Jan 08 2016. An interesting point about the term 355 is that it was found through trial and error using sole prime placement counts, and only after finding it as a candidate was it verified using exhaustive computation. The computation again used all combinations of the primes to 17 and the rejection of all first-occurring sole prime placements of the prime 5 using _Giovanni Resta_'s ILP approach with all binary variables. - _John F. Morack_, Jan 08 2016
%H A072753 John F. Morack, <a href="/A072753/a072753.txt">Sequences and Mods for a(17) and a(18)</a>
%H A072753 John F. Morack, <a href="/A072753/a072753_1.txt">Mod Sets and Sequences for Terms a(17)-a(19)</a>
%H A072753 Mario Ziller, John F. Morack, <a href="https://arxiv.org/abs/1706.00317">Divisibility in paired progressions, Goldbach’s conjecture, and the infinitude of prime pairs</a>, arXiv:1706.00317 [math.NT], 2017.
%H A072753 Mario Ziller, John F. Morack, <a href="https://arxiv.org/src/1706.03668v1/anc/full_details.pdf">On the computation of the generalised Jacobsthal function for paired progressions</a>, arXiv:1706.03668 [math.NT], 2017.
%F A072753 Let p(n) be the sequence of primes, i.e., p(1)=2. For n>=3 we define a(n) = max { m IN N | EXIST c(k), d(k) IN N, k=3, .., n : FOR ALL i IN {1, .., m} EXISTS j IN {3, .., n} : i == c(j) (mod p(j)) OR i == d(j) (mod p(j)) }
%F A072753 a(n) = (A288815(n) - 6)/6. - _Mario Ziller_, Jun 19 2017
%e A072753 a(5) = 10 because c(3)=2, d(3)=4, c(4)=1, d(4)=3, c(5)=4, d(5)=6 satisfy the requirements: 1 == 1 (mod 7), 2 == 2 (mod 5), 3 == 3 (mod 7), 4 == 4 (mod 5), 5 == 5 (mod 11), 6 == 6 (mod 11), 7 == 2 (mod 5), 8 == 1 (mod 7), 9 == 4 (mod 5), 10 == 3 (mod 7).
%Y A072753 Cf. A072752, A288815.
%K A072753 hard,more,nonn
%O A072753 3,1
%A A072753 _Mario Ziller_, Jul 10 2002
%E A072753 a(11) from _Mario Ziller_, May 30 2005
%E A072753 a(12) from _Mario Ziller_, Jun 20 2013
%E A072753 a(13) from _Mario Ziller_, Sep 26 2014
%E A072753 a(14)-a(15) from _Mario Ziller_, Aug 06 2015
%E A072753 a(16) from _Giovanni Resta_, Aug 06 2015
%E A072753 a(17)-a(18) from _John F. Morack_ Jan 03 2016
%E A072753 a(19) from _John F. Morack_ Jan 08 2016
%E A072753 a(19) corrected and a(20)-a(21) added by _Mario Ziller_, Jun 17 2017