|
| |
|
|
A193258
|
|
Sprimes: A sparse prime-like set of numbers that are constructed recursively to satisfy a Goldbach-type conjecture.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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.
|
|
|
LINKS
|
|
|
|
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).
|
|
|
EXAMPLE
|
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.
|
|
|
PROG
|
(Sage)
@cached_function
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]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
