A377419 Minimum sum of a maximal subset of {1..n} such that every pair of distinct elements has a different difference.

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

Author

Andrew Howroyd, Oct 27 2024

Keywords

• nonn

Comments

Also the minimum sum of a maximal 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 minimum sum of a maximal Sidon set of {1..n}.

Examples

			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.
		

Links

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

Crossrefs

Cf. A325879, A377410 (maximum sum).

Programs

PARI

a(n)={
  my(ismaxl(b,w)=for(k=1, n, if(!bittest(b,k) && !bitand(w,bitor(b,1< n, if(ismaxl(b,w),0,n^2),
         my(s=self()(k+1, b,w));
         b+=1<
				

Extensions

Name edited by Andrew Howroyd, Mar 24 2025