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

1, 3, 7, 11, 13, 27, 31, 35, 49, 61, 77, 79, 93, 101, 115, 117, 133, 163, 183, 187, 193, 235, 245, 257, 271, 279, 323, 335, 343, 381, 399, 439, 481, 497, 507, 535, 549, 569, 619, 669, 681, 693, 713, 739, 815, 833, 863, 905, 941, 973, 1033, 1053, 1089, 1119

Offset: 1

Author

Ian R Harris, Aug 26 2011

Keywords

• nonn

Comments

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.

Examples

			a(1)=1.
Note that S1={1}, so A={1}.
Now m=min{N\A}=2.
Thus C1={3} (amongst the natural numbers only 3 can be added to 1 to give 4).
Since 3 is the only candidate, a(2)=3.
To get a(3), we repeat steps 2) to 6).
So, S2={1,3}, A={1,2,3}, m=min{N\A}=4.
Thus the candidate set is C2={5,7} (we can add 5 to 3 to get 8, or 7 to 1 to get 8).
Then w5=|({(5+1)/2, (5+3)/2} union{5}) intersect {4,5,6,7,8,9,10,...}|=|{4,5}|=2.
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.
Since of the two candidates, 7 has the higher worth, then a(3)=7.
		

Links

• Ian R Harris, Technical report

Crossrefs

Cf. A000040, A008578, A000959, A123509, A126684, A008932.

Programs

Sage

@cached_function
def A193258(n):
    if n == 1: return 1
    S = set(A193258(i) for i in [1..n-1])
    A = set((i+j)/2 for i, j in cartesian_product([S, S]))
    m = next(i for i in PositiveIntegers() if i not in A)
    C = set(2*m-i for i in S if 2*m-i > A193258(n-1))
    worthfn = lambda c: len(set((c+i)/2 for i in S).difference(A))
    wc = sorted(list((worthfn(c), c) for c in C)) # sort by worth and by c
    return wc[-1][1]
# D. S. McNeil, Aug 29 2011

Formula

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

1) a(1)=1

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

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

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

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

6) a(k+1)=max{i in Ck | wi=maximum (over {j in Ck}) (wj)}.

Repeat steps 2) to 6).