cp's OEIS Frontend

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

%I A377419 #18 Mar 24 2025 18:22:32
%S A377419 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 A377419 34,35,36,41,41,46,48,50,52,52,53,56,56,59,59,61,63,65,68,71,71,75,81,
%U A377419 83,84,86,87,88,89,90,91,92,93,95,95,98,98,98,105,112,118,121,121,124
%N A377419 Minimum sum of a maximal subset of {1..n} such that every pair of distinct elements has a different difference.
%C A377419 Also the minimum sum of a maximal subset of {1..n} such that every unordered pair of (not necessarily distinct) elements has a different sum. In other words, a(n) is the minimum sum of a maximal Sidon set of {1..n}.
%H A377419 Wikipedia, <a href="https://en.wikipedia.org/wiki/Sidon_sequence">Sidon sequence</a>.
%H A377419 <a href="/index/Go#Golomb">Index entries for sequences related to Golomb rulers</a>.
%e A377419 a(0) = 0 = sum of {}.
%e A377419 a(1) = 1 = sum of {1}.
%e A377419 a(2) = 3 = sum of {1,2}.
%e A377419 a(3) = 3 = sum of {1,2}.
%e A377419 a(4) = 5 = sum of {2,3}.
%e A377419 a(5) = 7 = sum of {1,2,4}.
%e A377419 a(12) = 15 = sum of {1,2,5,7} or {1,2,4,8}.
%e A377419 a(20) = 28 = sum of {2,5,10,11} or {1,2,4,8,13}.
%e A377419 See also the examples in A325879.
%o A377419 (PARI)
%o A377419 a(n)={
%o A377419   my(ismaxl(b,w)=for(k=1, n, if(!bittest(b,k) && !bitand(w,bitor(b,1<<k)<<k), return(0))); 1);
%o A377419   my(recurse(k,b,w)=
%o A377419       if(k > n, if(ismaxl(b,w),0,n^2),
%o A377419          my(s=self()(k+1, b,w));
%o A377419          b+=1<<k; if(!bitand(w,b<<k), s=min(s, k+self()(k+1, b, w + (b<<k))));
%o A377419          s);
%o A377419   );
%o A377419   recurse(1,0,0);
%o A377419 }
%Y A377419 Cf. A325879, A377410 (maximum sum).
%K A377419 nonn
%O A377419 0,3
%A A377419 _Andrew Howroyd_, Oct 27 2024
%E A377419 Name edited by _Andrew Howroyd_, Mar 24 2025