cp's OEIS Frontend

A377410 Maximum sum of a subset of {1..n} such that every pair of distinct elements has a different difference.

%I A377410 #21 Mar 24 2025 18:22:26
%S A377410 0,1,3,5,8,11,14,17,21,25,29,33,37,42,47,52,57,62,67,72,78,84,90,96,
%T A377410 102,108,114,120,126,132,138,144,151,158,165,172,179,186,193,200,207,
%U A377410 215,223,231,239,247,255,263,271,279,287,295,303,311,319,327,335,343,351,360,369
%N A377410 Maximum sum of a subset of {1..n} such that every pair of distinct elements has a different difference.
%C A377410 Also the maximum sum of a 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 maximum sum of a Sidon set whose elements are <= n.
%H A377410 Wikipedia, <a href="https://en.wikipedia.org/wiki/Sidon_sequence">Sidon sequence</a>.
%H A377410 <a href="/index/Go#Golomb">Index entries for sequences related to Golomb rulers</a>.
%e A377410 a(0) = 0 = sum of {}.
%e A377410 a(1) = 1 = sum of {1}.
%e A377410 a(2) = 3 = sum of {1,2}.
%e A377410 a(3) = 5 = sum of {2,3}.
%e A377410 a(4) = 8 = sum of {1,3,4}.
%e A377410 a(5) = 11 = sum of {2,4,5}.
%e A377410 a(12) = 37 = sum of {6,8,11,12} or {5,9,11,12}.
%e A377410 a(20) = 78 = sum of {2,8,12,17,19,20}.
%e A377410 See also the examples in A143823.
%o A377410 (PARI)
%o A377410 a(n)={
%o A377410    my(recurse(k,b,w)=
%o A377410       if(k > n, 0,
%o A377410          my(s=self()(k+1, b, w));
%o A377410          b+=1<<k; if(!bitand(w,b<<k), s=max(s, k+self()(k+1, b, w + (b<<k))));
%o A377410          s)
%o A377410    );
%o A377410    recurse(1,0,0);
%o A377410 }
%o A377410 (Python)
%o A377410 def a(n):
%o A377410     def recurse(k, b, w):
%o A377410         if k > n: return 0
%o A377410         s = recurse(k+1, b, w)
%o A377410         b += (1<<k)
%o A377410         if not w & (b<<k): s = max(s, k+recurse(k+1, b, w+(b<<k)))
%o A377410         return s
%o A377410     return recurse(1, 0, 0)
%o A377410 print([a(n) for n in range(40)]) # _Michael S. Branicky_, Oct 27 2024 after _Andrew Howroyd_
%Y A377410 Cf. A143823, A143824 (maximum size of set), A377419.
%K A377410 nonn
%O A377410 0,3
%A A377410 _Andrew Howroyd_, Oct 27 2024
%E A377410 Name edited by _Andrew Howroyd_, Mar 24 2025