login
A stable set of primes created by a greedy algorithm.
3

%I #11 May 01 2015 12:40:57

%S 3,7,13,23,31,37,43,47,53,61,67,73,79,83,89,97,113,127,139,151,157,

%T 167,181,193,199,211,223,227,233,241,251,263,271,277,293,317,337,349,

%U 359,367,373,379,389,401,409,421,433,439,443,449,457,467,479,491,503,523

%N A stable set of primes created by a greedy algorithm.

%C 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?

%H T. D. Noe, <a href="/A091652/b091652.txt">Table of n, a(n) for n=1..1000</a>

%H L. E. Greenfield and S. J. Greenfield, <a href="https://cs.uwaterloo.ca/journals/JIS/green.html">Some Problems of Combinatorial Number Theory Related to Bertrand's Postulate</a>, J. Integer Sequences, 1998, #98.1.2.

%e 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.

%t 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

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

%K easy,nonn

%O 1,1

%A _T. D. Noe_, Jan 26 2004