login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A377419
Minimum sum of a maximal subset of {1..n} such that every unordered pair of (not necessarily distinct) elements has a different sum.
1
0, 1, 3, 3, 5, 7, 7, 7, 10, 10, 13, 15, 15, 15, 17, 17, 19, 19, 23, 24, 28, 29, 30, 30, 33, 34, 35, 36, 41, 41, 46, 48, 50, 52, 52, 53, 56, 56, 59, 59, 61, 63, 65, 68, 71, 71, 75, 81, 83, 84, 86, 87, 88, 89, 90, 91, 92, 93, 95, 95, 98, 98, 98, 105, 112, 118, 121, 121, 124
OFFSET
0,3
COMMENTS
In other words, a(n) is the minimum sum of a maximal Sidon set of {1..n}.
a(n) is also the minimum sum of a maximal subset of {1..n} such that every pair of distinct elements has a distinct difference.
EXAMPLE
a(0) = 0 = sum of {}.
a(1) = 1 = sum of {1}.
a(2) = 3 = sum of {1,2}.
a(3) = 3 = sum of {1,2}.
a(4) = 5 = sum of {2,3}.
a(5) = 7 = sum of {1,2,4}.
a(12) = 15 = sum of {1,2,5,7} or {1,2,4,8}.
a(20) = 28 = sum of {2,5,10,11} or {1,2,4,8,13}.
See also the examples in A325879.
PROG
(PARI)
a(n)={
my(ismaxl(b, w)=for(k=1, n, if(!bittest(b, k) && !bitand(w, bitor(b, 1<<k)<<k), return(0))); 1);
my(recurse(k, b, w)=
if(k > n, if(ismaxl(b, w), 0, n^2),
my(s=self()(k+1, b, w));
b+=1<<k; if(!bitand(w, b<<k), s=min(s, k+self()(k+1, b, w + (b<<k))));
s);
);
recurse(1, 0, 0);
}
CROSSREFS
Cf. A325879, A377410 (maximum sum).
Sequence in context: A335045 A110246 A070543 * A342194 A196372 A168053
KEYWORD
nonn,changed
AUTHOR
Andrew Howroyd, Oct 27 2024
STATUS
approved