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

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

Author

Andrew Howroyd, Mar 23 2025

Keywords

• nonn
• more
• changed

Comments

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.

Links

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

Crossrefs

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

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