cp's OEIS Frontend

A193258 Sprimes: A sparse prime-like set of numbers that are constructed recursively to satisfy a Goldbach-type conjecture.

%I A193258 #32 Feb 27 2020 04:28:37
%S A193258 1,3,7,11,13,27,31,35,49,61,77,79,93,101,115,117,133,163,183,187,193,
%T A193258 235,245,257,271,279,323,335,343,381,399,439,481,497,507,535,549,569,
%U A193258 619,669,681,693,713,739,815,833,863,905,941,973,1033,1053,1089,1119
%N A193258 Sprimes: A sparse prime-like set of numbers that are constructed recursively to satisfy a Goldbach-type conjecture.
%C A193258 Closely related to A123509, and the concept of a "basis". A key difference is that the set described here can only generate even numbers, and 0 is not allowed in the set.
%H A193258 Ian R Harris, <a href="http://faculty.smu.edu/iharris/OJISdraft1.pdf">Technical report</a>
%F A193258 The set of numbers S is chosen to satisfy the Goldbach conjecture. That is any even positive number must be able to be written as the sum of exactly two members of S (typically there are multiple ways to do this). The members of the set are generated by a deterministic recursive algorithm as follows (N is the set of positive integers):
%F A193258 1) a(1)=1
%F A193258 2) Given Sk={a(1),...,a(k)}, form the set A={n in N | exists a(i), a(j) in Sk, (a(i)+a(j))=2n}.
%F A193258 3) Let m=min{N\A}. (Then 2m is the smallest positive even number which cannot be formed from sums of the current finite list of sprimes.)
%F A193258 4) Define candidate set Ck={n in \N| n > a(k), exists a(i) in Sk such that a(i)+n=2m}. (This is a set of possible choices for a(k+1).)
%F A193258 5) To each member of Ck, assign "worth" wi=|({(i+a(j))/2| a(j) in Sk} union {i}) intersect {N\A}|. (This assigns to each candidate a worth equal to the number of new values that will be added to set A if the candidate is added to Sk.)
%F A193258 6) a(k+1)=max{i in Ck | wi=maximum (over {j in Ck}) (wj)}.
%F A193258 Repeat steps 2) to 6).
%e A193258 a(1)=1.
%e A193258 Note that S1={1}, so A={1}.
%e A193258 Now m=min{N\A}=2.
%e A193258 Thus C1={3} (amongst the natural numbers only 3 can be added to 1 to give 4).
%e A193258 Since 3 is the only candidate, a(2)=3.
%e A193258 To get a(3), we repeat steps 2) to 6).
%e A193258 So, S2={1,3}, A={1,2,3}, m=min{N\A}=4.
%e A193258 Thus the candidate set is C2={5,7} (we can add 5 to 3 to get 8, or 7 to 1 to get 8).
%e A193258 Then w5=|({(5+1)/2, (5+3)/2} union{5}) intersect {4,5,6,7,8,9,10,...}|=|{4,5}|=2.
%e A193258 And w7=|({(7+1)/2, (7+3)/2} union {7}) intersect {4,5,6,7,8,9,10,11,12,13,14,...}|=|{4,5,7}|=3.
%e A193258 Since of the two candidates, 7 has the higher worth, then a(3)=7.
%o A193258 (Sage)
%o A193258 @cached_function
%o A193258 def A193258(n):
%o A193258     if n == 1: return 1
%o A193258     S = set(A193258(i) for i in [1..n-1])
%o A193258     A = set((i+j)/2 for i, j in cartesian_product([S, S]))
%o A193258     m = next(i for i in PositiveIntegers() if i not in A)
%o A193258     C = set(2*m-i for i in S if 2*m-i > A193258(n-1))
%o A193258     worthfn = lambda c: len(set((c+i)/2 for i in S).difference(A))
%o A193258     wc = sorted(list((worthfn(c), c) for c in C)) # sort by worth and by c
%o A193258     return wc[-1][1]
%o A193258 # _D. S. McNeil_, Aug 29 2011
%Y A193258 Cf. A000040, A008578, A000959, A123509, A126684, A008932.
%K A193258 nonn
%O A193258 1,2
%A A193258 _Ian R Harris_, Aug 26 2011