A382396 -id:A382396 - cp's OEIS frontend

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

Andrew Howroyd, Mar 23 2025

nonn

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.

			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}.

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

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

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<

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

Original entry on oeis.org

0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6

Offset: 0

Andrew Howroyd, Mar 23 2025

Also the minimum size of a maximal subset of {1..n} such that every pair of (not necessarily distinct) elements has a different sum.
a(n) is the minimum size of a set enumerated by A325879(n).
Number of occurrences of k: 1, 1, 3,  6, 12, 20, ...
Maximum n having a(n) = k:  0, 1, 4, 10, 22, 42, ...
There are insufficient known terms in either of the above to distinguish from other sequences.

Thomas Bloom, Does there exist a maximal Sidon set A ⊂ {1, ..., N} of size O(N^(1/3))?, Erdős Problems.
Terence Tao, Erdős problem database, see no. 156.
Wikipedia, Sidon sequence.
Index entries for sequences related to Golomb rulers.

Cf. A143824 (maximum size of set), A325879, A377419 (minimum sum), A382396.

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+1),
         my(s=self()(k+1, b,w));
         b+=1<

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI