A382395 Number of maximum sized subsets of {1..n} such that every pair of distinct elements has a different difference.

1, 1, 1, 3, 2, 6, 14, 2, 10, 26, 60, 110, 4, 22, 68, 156, 320, 584, 8, 24, 80, 206, 504, 1004, 1910, 3380, 10, 34, 98, 282, 760, 1618, 3334, 6360, 11482, 2, 22, 70, 214, 540, 1250, 2718, 5712, 10910, 20418, 2, 12, 30, 90, 230, 562, 1228, 2690, 5550, 11260, 21164, 2, 4, 6, 10, 18

Offset: 0

Author

Andrew Howroyd, Mar 23 2025

Keywords

• nonn

Comments

Also the number of maximum sized subsets of {1..n} such that every pair of (not necessarily distinct) elements has a different sum. In other words, a(n) is the number of Sidon sets with A143824(n) elements which are <= n.

Examples

			The a(0) = 1 set is {}.
The a(1) = 1 set is {1}.
The a(2) = 1 set is {1,2}.
The a(3) = 3 sets: {1,2}, {1,3}, {2,3}.
The a(4) = 2 sets: {1,2,4}, {1,3,4}.
The a(5) = 6 sets: {1,2,4}, {1,2,5}, {1,3,4}, {1,4,5}, {2,3,5}, {2,4,5}.
The a(6) = 14 sets: {1,2,4}, {1,2,5}, {1,2,6}, {1,3,4}, {1,3,6}, {1,4,5}, {1,4,6}, {1,5,6}, {2,3,5}, {2,3,6}, {2,4,5}, {2,5,6}, {3,4,6}, {3,5,6}.
The a(7) = 2 sets: {1,2,5,7}, {1,3,6,7}.
		

Links

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

Crossrefs

Cf. A143823, A143824 (maximum size of set), A325879, A377410, A382396, A382398.

Programs

PARI

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