cp's OEIS Frontend

A066062 Number of subsets S of T={0,1,2,...,n} such that each element of T is the sum of two (not necessarily distinct) elements of S.

%I A066062 #46 Nov 22 2023 22:13:28
%S A066062 1,1,2,3,6,10,20,37,73,139,275,533,1059,2075,4126,8134,16194,32058,
%T A066062 63910,126932,253252,503933,1006056,2004838,4004124,7987149,15957964,
%U A066062 31854676,63660327,127141415,254136782,507750109,1015059238,2028564292,4055812657,8107052520
%N A066062 Number of subsets S of T={0,1,2,...,n} such that each element of T is the sum of two (not necessarily distinct) elements of S.
%C A066062 This sequence may be equivalent to A008929, but has a somewhat different definition. The size of the smallest subset counted by this sequence, for a given n, is given in A066063.
%C A066062 From _Steven Finch_, Mar 15 2009: (Start)
%C A066062 Such sets S are called additive 2-bases for {0,1,2,...,n}.
%C A066062 a(n) is also the number of symmetric numerical sets S with atom monoid A(S) equal to {0, 2n+2, 2n+3, 2n+4, 2n+5, ...}. (End)
%H A066062 Martin Fuller, <a href="/A066062/b066062.txt">Table of n, a(n) for n = 0..65</a>
%H A066062 S. R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009. [Cached copy, with permission of the author]
%H A066062 G. Grekos, L. Haddad, C. Helou, and J. Pihko, <a href="http://dx.doi.org/10.1016/S0022-314X(03)00108-2">On the Erdos-Turán conjecture</a>, J. Number Theory 102 (2003), no. 2, 339-352.
%H A066062 J. Marzuola and A. Miller, <a href="http://arxiv.org/abs/0805.3493">Counting numerical sets with no small atoms</a>, arXiv:0805.3493 [math.CO], 2008. - _Steven Finch_, Mar 15 2009
%H A066062 J. Marzuola and A. Miller, <a href="https://doi.org/10.1016/j.jcta.2010.03.002">Counting numerical sets with no small atoms</a>, J. Combin. Theory A 117 (6) (2010) 650-667.
%F A066062 a(n) = 2*a(n-1) - A158449(n) [adapted from A164097]. - _Martin Fuller_, Sep 13 2023
%F A066062 a(n) >= A001405(n). - _Michael Chu_, Oct 15 2023
%e A066062 For n=2, the definition obviously requires that S contain both 0 and 1. The only subsets of {0,1,2} that do this are {0,1} and {0,1,2}. For both of these, we have 0=0+0, 1=0+1, 2=1+1, so a(2)=2.
%t A066062 a[n_] := Module[{},
%t A066062   T = Range[0, n];
%t A066062   ST = Subsets[T, {Floor[n^(2/3)], n+1}];
%t A066062   selQ[S_] := Intersection[T, Total /@ Tuples[S, {2}]] == T;
%t A066062   SST = Select[ST, selQ]; min = Min[Length /@ SST];
%t A066062   SST // Length
%t A066062 ];
%t A066062 Table[an = a[n]; Print["a(", n, ") = ", an, " min = ", min]; an, {n, 0, 24}] (* _Jean-François Alcover_, Nov 05 2018 *)
%o A066062 (Python)
%o A066062 def sums(s): return set((si+sj) for i, si in enumerate(s) for sj in s[i:])
%o A066062 def b(i, n, s):
%o A066062     if sums(s) >= set(range(n+1)): return 2**(n+1-i)
%o A066062     if i > n: return 0
%o A066062     return b(i+1, n, s) + b(i+1, n, s+[i])
%o A066062 def a(n): return b(0, n, [])
%o A066062 print([a(n) for n in range(15)]) # _Michael S. Branicky_, Jan 15 2022
%o A066062 (C) See Martin Fuller link in A158449
%Y A066062 Cf. A008929, A066063, A158449, A164047.
%Y A066062 Cf. A158291. - _Steven Finch_, Mar 15 2009
%K A066062 nonn
%O A066062 0,3
%A A066062 _John W. Layman_, Dec 01 2001
%E A066062 a(27)-a(30) from _Michael S. Branicky_, Jan 15 2022
%E A066062 a(31) onwards from _Martin Fuller_, Sep 13 2023