login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 29
1, 1, 2, 3, 6, 10, 20, 37, 73, 139, 275, 533, 1059, 2075, 4126, 8134, 16194, 32058, 63910, 126932, 253252, 503933, 1006056, 2004838, 4004124, 7987149, 15957964, 31854676, 63660327, 127141415, 254136782, 507750109, 1015059238, 2028564292, 4055812657, 8107052520 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
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.
From Steven Finch, Mar 15 2009: (Start)
Such sets S are called additive 2-bases for {0,1,2,...,n}.
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)
LINKS
S. R. Finch, Monoids of natural numbers, March 17, 2009. [Cached copy, with permission of the author]
G. Grekos, L. Haddad, C. Helou, and J. Pihko, On the Erdos-Turán conjecture, J. Number Theory 102 (2003), no. 2, 339-352.
J. Marzuola and A. Miller, Counting numerical sets with no small atoms, arXiv:0805.3493 [math.CO], 2008. - Steven Finch, Mar 15 2009
J. Marzuola and A. Miller, Counting numerical sets with no small atoms, J. Combin. Theory A 117 (6) (2010) 650-667.
FORMULA
a(n) = 2*a(n-1) - A158449(n) [adapted from A164097]. - Martin Fuller, Sep 13 2023
a(n) >= A001405(n). - Michael Chu, Oct 15 2023
EXAMPLE
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.
MATHEMATICA
a[n_] := Module[{},
T = Range[0, n];
ST = Subsets[T, {Floor[n^(2/3)], n+1}];
selQ[S_] := Intersection[T, Total /@ Tuples[S, {2}]] == T;
SST = Select[ST, selQ]; min = Min[Length /@ SST];
SST // Length
];
Table[an = a[n]; Print["a(", n, ") = ", an, " min = ", min]; an, {n, 0, 24}] (* Jean-François Alcover, Nov 05 2018 *)
PROG
(Python)
def sums(s): return set((si+sj) for i, si in enumerate(s) for sj in s[i:])
def b(i, n, s):
if sums(s) >= set(range(n+1)): return 2**(n+1-i)
if i > n: return 0
return b(i+1, n, s) + b(i+1, n, s+[i])
def a(n): return b(0, n, [])
print([a(n) for n in range(15)]) # Michael S. Branicky, Jan 15 2022
(C) See Martin Fuller link in A158449
CROSSREFS
Cf. A158291. - Steven Finch, Mar 15 2009
Sequence in context: A222855 A171682 A008929 * A164047 A158291 A045690
KEYWORD
nonn
AUTHOR
John W. Layman, Dec 01 2001
EXTENSIONS
a(27)-a(30) from Michael S. Branicky, Jan 15 2022
a(31) onwards from Martin Fuller, Sep 13 2023
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 12:26 EDT 2024. Contains 371254 sequences. (Running on oeis4.)