A377419 Minimum sum of a maximal subset of {1..n} such that every unordered pair of (not necessarily distinct) elements has a different sum.

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.

Links

Table of n, a(n) for n=0..68.

Wikipedia, Sidon sequence.

Index entries for sequences related to Golomb rulers.

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

Adjacent sequences: A377416 A377417 A377418 * A377420 A377421 A377422

Keyword

nonn,changed

Author

Andrew Howroyd, Oct 27 2024

Status

approved