login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A072753 Maximum gap in two-stage prime-sieves. 3
2, 4, 10, 24, 31, 42, 60, 74, 94, 117, 148, 173, 213, 236, 275, 316, 364, 409, 436 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,1

COMMENTS

From John F. Morack, Dec 20 2012: (Start)

There is a relationship between this sequence and Goldbach's Conjecture.

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.

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)

From Giovanni Resta, Aug 06 2015: (Start)

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.

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).

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).

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).

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)

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

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

LINKS

Table of n, a(n) for n=3..21.

John F. Morack, Sequences and Mods for a(17) and a(18)

John F. Morack, Mod Sets and Sequences for Terms a(17)-a(19)

Mario Ziller, John F. Morack, Divisibility in paired progressions, Goldbach’s conjecture, and the infinitude of prime pairs, arXiv:1706.00317 [math.NT], 2017.

Mario Ziller, John F. Morack, On the computation of the generalised Jacobsthal function for paired progressions, arXiv:1706.03668 [math.NT], 2017.

FORMULA

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)) }

a(n) = (A288815(n) - 6)/6. - Mario Ziller, Jun 19 2017

EXAMPLE

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).

CROSSREFS

Cf. A072752, A288815.

Sequence in context: A156806 A192523 A065832 * A009884 A032023 A094837

Adjacent sequences:  A072750 A072751 A072752 * A072754 A072755 A072756

KEYWORD

hard,more,nonn

AUTHOR

Mario Ziller, Jul 10 2002

EXTENSIONS

a(11) from Mario Ziller, May 30 2005

a(12) from Mario Ziller, Jun 20 2013

a(13) from Mario Ziller, Sep 26 2014

a(14)-a(15) from Mario Ziller, Aug 06 2015

a(16) from Giovanni Resta, Aug 06 2015

a(17)-a(18) from John F. Morack Jan 03 2016

a(19) from John F. Morack Jan 08 2016

a(19) corrected and a(20)-a(21) added by Mario Ziller, Jun 17 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 6 14:04 EDT 2020. Contains 334827 sequences. (Running on oeis4.)