login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of subsets of {1..n} containing no sums or products of distinct elements.
3

%I #14 Apr 10 2021 15:07:42

%S 1,2,3,5,9,15,25,41,68,109,179,284,443,681,1062,1587,2440,3638,5443,

%T 8021,11953,17273,25578,37001,53953,77429,113063,160636,232928,330775,

%U 475380,672056,967831,1359743,1952235,2743363,3918401,5495993,7856134,10984547,15669741

%N Number of subsets of {1..n} containing no sums or products of distinct elements.

%H Fausto A. C. Cariboni, <a href="/A326024/b326024.txt">Table of n, a(n) for n = 0..80</a>

%e The a(0) = 1 through a(5) = 15 subsets:

%e {} {} {} {} {} {}

%e {1} {1} {1} {1} {1}

%e {2} {2} {2} {2}

%e {3} {3} {3}

%e {2,3} {4} {4}

%e {2,3} {5}

%e {2,4} {2,3}

%e {3,4} {2,4}

%e {2,3,4} {2,5}

%e {3,4}

%e {3,5}

%e {4,5}

%e {2,3,4}

%e {2,4,5}

%e {3,4,5}

%t Table[Length[Select[Subsets[Range[n]],Intersection[#,Union[Plus@@@Subsets[#,{2,n}],Times@@@Subsets[#,{2,n}]]]=={}&]],{n,0,10}]

%o (PARI)

%o a(n)={

%o my(recurse(k, es, ep)=

%o if(k > n, 1,

%o my(t = self()(k + 1, es, ep));

%o if(!bittest(es,k) && !bittest(ep,k),

%o es = bitor(es, bitand((2<<n)-1, es << k));

%o forstep(i=n\k, 1, -1, if(bittest(ep,i), ep=bitor(ep,1<<(k*i))));

%o t += self()(k + 1, es, ep);

%o );

%o t);

%o );

%o 1 + if(n, recurse(2, 1, 2));

%o } \\ _Andrew Howroyd_, Aug 25 2019

%Y Subsets without sums of distinct elements are A151897.

%Y Subsets without products of distinct elements are A326117.

%Y Maximal subsets without sums or products of distinct elements are A326025.

%Y Subsets with sums (and products) are A326083.

%Y Sum-free and product-free subsets are A326495.

%Y Cf. A007865, A051026, A121269, A325710, A326076, A326489, A326497, A326498.

%K nonn

%O 0,2

%A _Gus Wiseman_, Jul 09 2019

%E Terms a(16)-a(40) from _Andrew Howroyd_, Aug 25 2019