cp's OEIS Frontend

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

%I A382397 #12 Sep 05 2025 00:58:06
%S A382397 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,
%T A382397 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
%N A382397 Minimum size of a maximal subset of {1..n} such that every pair of distinct elements has a different difference.
%C A382397 Also the minimum size of a maximal subset of {1..n} such that every pair of (not necessarily distinct) elements has a different sum.
%C A382397 a(n) is the minimum size of a set enumerated by A325879(n).
%C A382397 Number of occurrences of k: 1, 1, 3,  6, 12, 20, ...
%C A382397 Maximum n having a(n) = k:  0, 1, 4, 10, 22, 42, ...
%C A382397 There are insufficient known terms in either of the above to distinguish from other sequences.
%H A382397 Thomas Bloom, <a href="https://www.erdosproblems.com/156">Does there exist a maximal Sidon set A ⊂ {1, ..., N} of size O(N^(1/3))?</a>, Erdős Problems.
%H A382397 Terence Tao, <a href="https://github.com/teorth/erdosproblems/blob/main/README.md#table">Erdős problem database</a>, see no. 156.
%H A382397 Wikipedia, <a href="https://en.wikipedia.org/wiki/Sidon_sequence">Sidon sequence</a>.
%H A382397 <a href="/index/Go#Golomb">Index entries for sequences related to Golomb rulers</a>.
%o A382397 (PARI)
%o A382397 a(n)={
%o A382397   my(ismaxl(b,w)=for(k=1, n, if(!bittest(b,k) && !bitand(w,bitor(b,1<<k)<<k), return(0))); 1);
%o A382397   my(recurse(k,b,w)=
%o A382397       if(k > n, if(ismaxl(b,w),0,n+1),
%o A382397          my(s=self()(k+1, b,w));
%o A382397          b+=1<<k; if(!bitand(w,b<<k), s=min(s, 1+self()(k+1, b, w + (b<<k))));
%o A382397          s);
%o A382397   );
%o A382397   recurse(1,0,0);
%o A382397 }
%Y A382397 Cf. A143824 (maximum size of set), A325879, A377419 (minimum sum), A382396.
%K A382397 nonn,more,changed
%O A382397 0,3
%A A382397 _Andrew Howroyd_, Mar 23 2025