cp's OEIS Frontend

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

%I A382395 #10 Mar 24 2025 15:15:13
%S A382395 1,1,1,3,2,6,14,2,10,26,60,110,4,22,68,156,320,584,8,24,80,206,504,
%T A382395 1004,1910,3380,10,34,98,282,760,1618,3334,6360,11482,2,22,70,214,540,
%U A382395 1250,2718,5712,10910,20418,2,12,30,90,230,562,1228,2690,5550,11260,21164,2,4,6,10,18
%N A382395 Number of maximum sized subsets of {1..n} such that every pair of distinct elements has a different difference.
%C A382395 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.
%H A382395 Wikipedia, <a href="https://en.wikipedia.org/wiki/Sidon_sequence">Sidon sequence</a>.
%H A382395 <a href="/index/Go#Golomb">Index entries for sequences related to Golomb rulers</a>.
%e A382395 The a(0) = 1 set is {}.
%e A382395 The a(1) = 1 set is {1}.
%e A382395 The a(2) = 1 set is {1,2}.
%e A382395 The a(3) = 3 sets: {1,2}, {1,3}, {2,3}.
%e A382395 The a(4) = 2 sets: {1,2,4}, {1,3,4}.
%e A382395 The a(5) = 6 sets: {1,2,4}, {1,2,5}, {1,3,4}, {1,4,5}, {2,3,5}, {2,4,5}.
%e A382395 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}.
%e A382395 The a(7) = 2 sets: {1,2,5,7}, {1,3,6,7}.
%o A382395 (PARI)
%o A382395 a(n)={
%o A382395    local(best,count);
%o A382395    my(recurse(k,r,b,w)=
%o A382395       if(k > n, if(r>=best, if(r>best,best=r;count=0); count++),
%o A382395          self()(k+1, r, b, w);
%o A382395          b+=1<<k; if(!bitand(w,b<<k), self()(k+1, r+1, b, w + (b<<k)));
%o A382395          )
%o A382395    );
%o A382395    recurse(1,0,0,0);
%o A382395    count;
%o A382395 }
%Y A382395 Cf. A143823, A143824 (maximum size of set), A325879, A377410, A382396, A382398.
%K A382395 nonn
%O A382395 0,4
%A A382395 _Andrew Howroyd_, Mar 23 2025