cp's OEIS Frontend

A382396 Number of minimum sized maximal subsets of {1..n} such that every pair of distinct elements has a different difference.

%I A382396 #8 Mar 24 2025 15:15:09
%S A382396 1,1,1,3,1,6,14,18,14,10,4,110,172,216,226,214,184,152,116,82,50,26,
%T A382396 10,3696,3904,3942,3768,3504,3016,2548,2060,1598,1170,832,538,330,196,
%U A382396 106,52,20,10,4,2,69610,62594,55294,47610,40502,33538,27254,21544,16764,12676,9258,6534,4516,3042,1990,1254,754,448
%N A382396 Number of minimum sized maximal subsets of {1..n} such that every pair of distinct elements has a different difference.
%C A382396 Also the number of minimum sized maximal subsets of {1..n} such that every pair of (not necessarily distinct) elements has a different sum.
%H A382396 Wikipedia, <a href="https://en.wikipedia.org/wiki/Sidon_sequence">Sidon sequence</a>.
%H A382396 <a href="/index/Go#Golomb">Index entries for sequences related to Golomb rulers</a>.
%e A382396 The a(0) = 1 set is {}.
%e A382396 The a(1) = 1 set is {1}.
%e A382396 The a(2) = 1 set is {1,2}.
%e A382396 The a(3) = 3 sets: {1,2}, {1,3}, {2,3}.
%e A382396 The a(11) = 4 sets: {1,2,4,8}, {1,2,4,9}, {1,2,4,10}, {1,2,4,11}.
%e A382396 The a(42) = 2 sets: {10,18,19,25,30}, {13,18,24,25,33}.
%e A382396 See also the examples in A325879.
%o A382396 (PARI)
%o A382396 a(n)={
%o A382396   local(best,count); best=n+1;
%o A382396   my(ismaxl(b,w)=for(k=1, n, if(!bittest(b,k) && !bitand(w,bitor(b,1<<k)<<k), return(0))); 1);
%o A382396   my(recurse(k,r,b,w)=
%o A382396       if(k > n, if(ismaxl(b,w),if(r<best,best=r;count=0); count++),
%o A382396          self()(k+1, r, b, w);
%o A382396          if(r<best, b+=1<<k; if(!bitand(w,b<<k), self()(k+1, r+1, b, w + (b<<k))));
%o A382396          );
%o A382396   );
%o A382396   recurse(1,0,0,0);
%o A382396   count
%o A382396 }
%Y A382396 Cf. A143823, A325879, A377419, A382395, A382397 (minimum size of set).
%K A382396 nonn
%O A382396 0,4
%A A382396 _Andrew Howroyd_, Mar 23 2025