A091652 A stable set of primes created by a greedy algorithm.

3, 7, 13, 23, 31, 37, 43, 47, 53, 61, 67, 73, 79, 83, 89, 97, 113, 127, 139, 151, 157, 167, 181, 193, 199, 211, 223, 227, 233, 241, 251, 263, 271, 277, 293, 317, 337, 349, 359, 367, 373, 379, 389, 401, 409, 421, 433, 439, 443, 449, 457, 467, 479, 491, 503, 523

Offset

1,1

Comments

The Greenfields show that the integers from 1 to 2n can always be paired to form n (not necessarily distinct) primes. A greedy algorithm, starting with 2n, quickly finds the n primes. Interestingly, as n increases, the set of primes produced by this algorithm forms a stable set of prime numbers. Why?

Links

T. D. Noe, Table of n, a(n) for n=1..1000

L. E. Greenfield and S. J. Greenfield, Some Problems of Combinatorial Number Theory Related to Bertrand's Postulate, J. Integer Sequences, 1998, #98.1.2.

Example

When the greedy algorithm pairs the numbers 1 to 20, it finds the following 10 primes: 37=20+17, 37=19+18, 31=16+15, 23=14+9, 23=13+10, 23=12+11, 13=8+5, 13=7+6, 7=4+3 and 3=2+1.

Mathematica

n=1000; lst=Reverse[Range[2n]]; prms={}; Do[m=lst[[1]]; lst=Delete[lst, 1]; pos=1; While[Not[PrimeQ[m+lst[[pos]]]], pos++ ]; prms=Union[prms, {m+lst[[pos]]}]; lst=Delete[lst, pos], {i, n}]; prms

Crossrefs

Cf. A091653 (complement of these primes), A091654 (frequency of these primes).

Sequence in context: A002623 A173196 A081662 * A334163 A291546 A134197

Adjacent sequences: A091649 A091650 A091651 * A091653 A091654 A091655

Keyword

easy,nonn

Author

T. D. Noe, Jan 26 2004

Status

approved