A377419 - OEIS

%I #13 Nov 21 2024 08:39:26

%S 0,1,3,3,5,7,7,7,10,10,13,15,15,15,17,17,19,19,23,24,28,29,30,30,33,

%T 34,35,36,41,41,46,48,50,52,52,53,56,56,59,59,61,63,65,68,71,71,75,81,

%U 83,84,86,87,88,89,90,91,92,93,95,95,98,98,98,105,112,118,121,121,124

%N Minimum sum of a maximal subset of {1..n} such that every unordered pair of (not necessarily distinct) elements has a different sum.

%C In other words, a(n) is the minimum sum of a maximal Sidon set of {1..n}.

%C a(n) is also the minimum sum of a maximal subset of {1..n} such that every pair of distinct elements has a distinct difference.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Sidon_sequence">Sidon sequence</a>.

%H <a href="/index/Go#Golomb">Index entries for sequences related to Golomb rulers</a>.

%e a(0) = 0 = sum of {}.

%e a(1) = 1 = sum of {1}.

%e a(2) = 3 = sum of {1,2}.

%e a(3) = 3 = sum of {1,2}.

%e a(4) = 5 = sum of {2,3}.

%e a(5) = 7 = sum of {1,2,4}.

%e a(12) = 15 = sum of {1,2,5,7} or {1,2,4,8}.

%e a(20) = 28 = sum of {2,5,10,11} or {1,2,4,8,13}.

%e See also the examples in A325879.

%o (PARI)

%o a(n)={

%o   my(ismaxl(b,w)=for(k=1, n, if(!bittest(b,k) && !bitand(w,bitor(b,1<<k)<<k), return(0))); 1);

%o   my(recurse(k,b,w)=

%o       if(k > n, if(ismaxl(b,w),0,n^2),

%o          my(s=self()(k+1, b,w));

%o          b+=1<<k; if(!bitand(w,b<<k), s=min(s, k+self()(k+1, b, w + (b<<k))));

%o          s);

%o   );

%o   recurse(1,0,0);

%o }

%Y Cf. A325879, A377410 (maximum sum).

%K nonn

%O 0,3

%A _Andrew Howroyd_, Oct 27 2024