OFFSET
0,4
COMMENTS
Also the number of maximum sized subsets of {1..n} such that every pair of (not necessarily distinct) elements has a different sum. In other words, a(n) is the number of Sidon sets with A143824(n) elements which are <= n.
LINKS
EXAMPLE
The a(0) = 1 set is {}.
The a(1) = 1 set is {1}.
The a(2) = 1 set is {1,2}.
The a(3) = 3 sets: {1,2}, {1,3}, {2,3}.
The a(4) = 2 sets: {1,2,4}, {1,3,4}.
The a(5) = 6 sets: {1,2,4}, {1,2,5}, {1,3,4}, {1,4,5}, {2,3,5}, {2,4,5}.
The a(6) = 14 sets: {1,2,4}, {1,2,5}, {1,2,6}, {1,3,4}, {1,3,6}, {1,4,5}, {1,4,6}, {1,5,6}, {2,3,5}, {2,3,6}, {2,4,5}, {2,5,6}, {3,4,6}, {3,5,6}.
The a(7) = 2 sets: {1,2,5,7}, {1,3,6,7}.
PROG
(PARI)
a(n)={
local(best, count);
my(recurse(k, r, b, w)=
if(k > n, if(r>=best, if(r>best, best=r; count=0); count++),
self()(k+1, r, b, w);
b+=1<<k; if(!bitand(w, b<<k), self()(k+1, r+1, b, w + (b<<k)));
)
);
recurse(1, 0, 0, 0);
count;
}
CROSSREFS
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Mar 23 2025
STATUS
approved