A377410 Maximum sum of a subset of {1..n} such that every pair of distinct elements has a different difference.

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

Author

Andrew Howroyd, Oct 27 2024

Keywords

• nonn

Comments

Also the maximum sum of a subset of {1..n} such that every unordered pair of (not necessarily distinct) elements has a different sum. In other words, a(n) is the maximum sum of a Sidon set whose elements are <= n.

Examples

			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.
		

Links

• Wikipedia, Sidon sequence.
• Index entries for sequences related to Golomb rulers.

Crossrefs

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

Programs

PARI

a(n)={
   my(recurse(k,b,w)=
      if(k > n, 0,
         my(s=self()(k+1, b, w));
         b+=1<
				

Python

def a(n):
    def recurse(k, b, w):
        if k > n: return 0
        s = recurse(k+1, b, w)
        b += (1<Michael S. Branicky, Oct 27 2024 after Andrew Howroyd

Extensions

Name edited by Andrew Howroyd, Mar 24 2025