login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A326024
Number of subsets of {1..n} containing no sums or products of distinct elements.
3
1, 2, 3, 5, 9, 15, 25, 41, 68, 109, 179, 284, 443, 681, 1062, 1587, 2440, 3638, 5443, 8021, 11953, 17273, 25578, 37001, 53953, 77429, 113063, 160636, 232928, 330775, 475380, 672056, 967831, 1359743, 1952235, 2743363, 3918401, 5495993, 7856134, 10984547, 15669741
OFFSET
0,2
LINKS
Fausto A. C. Cariboni, Table of n, a(n) for n = 0..80
EXAMPLE
The a(0) = 1 through a(5) = 15 subsets:
{} {} {} {} {} {}
{1} {1} {1} {1} {1}
{2} {2} {2} {2}
{3} {3} {3}
{2,3} {4} {4}
{2,3} {5}
{2,4} {2,3}
{3,4} {2,4}
{2,3,4} {2,5}
{3,4}
{3,5}
{4,5}
{2,3,4}
{2,4,5}
{3,4,5}
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], Intersection[#, Union[Plus@@@Subsets[#, {2, n}], Times@@@Subsets[#, {2, n}]]]=={}&]], {n, 0, 10}]
PROG
(PARI)
a(n)={
my(recurse(k, es, ep)=
if(k > n, 1,
my(t = self()(k + 1, es, ep));
if(!bittest(es, k) && !bittest(ep, k),
es = bitor(es, bitand((2<<n)-1, es << k));
forstep(i=n\k, 1, -1, if(bittest(ep, i), ep=bitor(ep, 1<<(k*i))));
t += self()(k + 1, es, ep);
);
t);
);
1 + if(n, recurse(2, 1, 2));
} \\ Andrew Howroyd, Aug 25 2019
CROSSREFS
Subsets without sums of distinct elements are A151897.
Subsets without products of distinct elements are A326117.
Maximal subsets without sums or products of distinct elements are A326025.
Subsets with sums (and products) are A326083.
Sum-free and product-free subsets are A326495.
Sequence in context: A323475 A097083 A268709 * A200047 A147877 A003476
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jul 09 2019
EXTENSIONS
Terms a(16)-a(40) from Andrew Howroyd, Aug 25 2019
STATUS
approved