cp's OEIS Frontend

A326116 Number of subsets of {2..n} containing no products of two or more distinct elements.

%I A326116 #19 May 10 2025 14:42:41
%S A326116 1,2,4,8,16,28,56,100,200,364,728,1232,2464,4592,8296,15920,31840,
%T A326116 55952,111904,195712,362336,697360,1394720,2334112,4668224,9095392,
%U A326116 17225312,31242784,62485568,106668608,213337216,392606528,755131840,1491146912,2727555424,4947175712
%N A326116 Number of subsets of {2..n} containing no products of two or more distinct elements.
%C A326116 First differs from A308542 at a(12) = 1232, A308542(12) = 1184.
%C A326116 If this sequence counts product-free sets, A308542 counts product-closed sets.
%H A326116 Fausto A. C. Cariboni, <a href="/A326116/b326116.txt">Table of n, a(n) for n = 1..47</a>
%H A326116 P. J. Cameron and P. Erdős, <a href="https://www.researchgate.net/publication/247043302_On_the_number_of_sets_of_integers_with_various_properties">On the number of integers with various properties</a>, in R. A. Mullin, ed., Number Theory: Proc. First Conf. of Canad. Number Theory Assoc. Conf., Banff, De Gruyter, Berlin, 1990, pp. 61-79.
%F A326116 For n > 0, a(n) = A326117(n) - 1.
%e A326116 The a(6) = 28 subsets:
%e A326116   {}  {2}  {2,3}  {2,3,4}  {2,3,4,5}
%e A326116       {3}  {2,4}  {2,3,5}  {2,4,5,6}
%e A326116       {4}  {2,5}  {2,4,5}  {3,4,5,6}
%e A326116       {5}  {2,6}  {2,4,6}
%e A326116       {6}  {3,4}  {2,5,6}
%e A326116            {3,5}  {3,4,5}
%e A326116            {3,6}  {3,4,6}
%e A326116            {4,5}  {3,5,6}
%e A326116            {4,6}  {4,5,6}
%e A326116            {5,6}
%t A326116 Table[Length[Select[Subsets[Range[2,n]],Intersection[#,Select[Times@@@Subsets[#,{2}],#<=n&]]=={}&]],{n,10}]
%o A326116 (PARI)
%o A326116 a(n)={
%o A326116    my(recurse(k, ep)=
%o A326116     if(k > n, 1,
%o A326116       my(t = self()(k + 1, ep));
%o A326116       if(!bittest(ep,k),
%o A326116          forstep(i=n\k, 1, -1, if(bittest(ep,i), ep=bitor(ep,1<<(k*i))));
%o A326116          t += self()(k + 1, ep);
%o A326116       );
%o A326116       t);
%o A326116    );
%o A326116    recurse(2, 2);
%o A326116 } \\ _Andrew Howroyd_, Aug 25 2019
%Y A326116 Cf. A007865, A051026, A103580, A196724, A326020, A326023, A326076, A326078, A326079, A326081, A326117, A308542.
%K A326116 nonn
%O A326116 1,2
%A A326116 _Gus Wiseman_, Jun 06 2019
%E A326116 Terms a(21)-a(36) from _Andrew Howroyd_, Aug 25 2019