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

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 42, 47, 52, 57, 62, 67, 72, 78, 84, 90, 96, 102, 108, 114, 120, 126, 132, 138, 144, 151, 158, 165, 172, 179, 186, 193, 200, 207, 215, 223, 231, 239, 247, 255, 263, 271, 279, 287, 295, 303, 311, 319, 327, 335, 343, 351, 360, 369

Offset

0,3

Comments

In other words, a(n) is the maximum sum of a Sidon set whose elements are <= n.

a(n) is also the maximum sum of a subset of {1..n} such that every pair of distinct elements has a distinct difference.

Links

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

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) = 5 = sum of {2,3}.
a(4) = 8 = sum of {1,3,4}.
a(5) = 11 = sum of {2,4,5}.
a(12) = 37 = sum of {6,8,11,12} or {5,9,11,12}.
a(20) = 78 = sum of {2,8,12,17,19,20}.
See also the examples in A143823.

Prog

(PARI)
a(n)={
   my(recurse(k, b, w)=
      if(k > n, 0,
         my(s=self()(k+1, b, w));
         b+=1<<k; if(!bitand(w, b<<k), s=max(s, k+self()(k+1, b, w + (b<<k))));
         s)
   );
   recurse(1, 0, 0);
}
(Python)
def a(n):
    def recurse(k, b, w):
        if k > n: return 0
        s = recurse(k+1, b, w)
        b += (1<<k)
        if not w & (b<<k): s = max(s, k+recurse(k+1, b, w+(b<<k)))
        return s
    return recurse(1, 0, 0)
print([a(n) for n in range(40)]) # Michael S. Branicky, Oct 27 2024 after Andrew Howroyd

Crossrefs

Cf. A143823, A143824 (maximum size of set), A377419.

Sequence in context: A094228 A278586 A001855 * A006591 A310027 A310028

Adjacent sequences: A377407 A377408 A377409 * A377411 A377412 A377413

Keyword

nonn

Author

Andrew Howroyd, Oct 27 2024

Status

approved