login
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.
29

%I #46 Nov 22 2023 22:13:28

%S 1,1,2,3,6,10,20,37,73,139,275,533,1059,2075,4126,8134,16194,32058,

%T 63910,126932,253252,503933,1006056,2004838,4004124,7987149,15957964,

%U 31854676,63660327,127141415,254136782,507750109,1015059238,2028564292,4055812657,8107052520

%N 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 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 From _Steven Finch_, Mar 15 2009: (Start)

%C Such sets S are called additive 2-bases for {0,1,2,...,n}.

%C 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 Martin Fuller, <a href="/A066062/b066062.txt">Table of n, a(n) for n = 0..65</a>

%H S. R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009. [Cached copy, with permission of the author]

%H 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 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 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 a(n) = 2*a(n-1) - A158449(n) [adapted from A164097]. - _Martin Fuller_, Sep 13 2023

%F a(n) >= A001405(n). - _Michael Chu_, Oct 15 2023

%e 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 a[n_] := Module[{},

%t T = Range[0, n];

%t ST = Subsets[T, {Floor[n^(2/3)], n+1}];

%t selQ[S_] := Intersection[T, Total /@ Tuples[S, {2}]] == T;

%t SST = Select[ST, selQ]; min = Min[Length /@ SST];

%t SST // Length

%t ];

%t Table[an = a[n]; Print["a(", n, ") = ", an, " min = ", min]; an, {n, 0, 24}] (* _Jean-François Alcover_, Nov 05 2018 *)

%o (Python)

%o def sums(s): return set((si+sj) for i, si in enumerate(s) for sj in s[i:])

%o def b(i, n, s):

%o if sums(s) >= set(range(n+1)): return 2**(n+1-i)

%o if i > n: return 0

%o return b(i+1, n, s) + b(i+1, n, s+[i])

%o def a(n): return b(0, n, [])

%o print([a(n) for n in range(15)]) # _Michael S. Branicky_, Jan 15 2022

%o (C) See Martin Fuller link in A158449

%Y Cf. A008929, A066063, A158449, A164047.

%Y Cf. A158291. - _Steven Finch_, Mar 15 2009

%K nonn

%O 0,3

%A _John W. Layman_, Dec 01 2001

%E a(27)-a(30) from _Michael S. Branicky_, Jan 15 2022

%E a(31) onwards from _Martin Fuller_, Sep 13 2023