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

%I #17 Apr 11 2021 23:51:13

%S 1,2,4,8,16,28,56,100,200,364,728,1232,2464,4592,8296,15920,31840,

%T 55952,111904,195712,362336,697360,1394720,2334112,4668224,9095392,

%U 17225312,31242784,62485568,106668608,213337216,392606528,755131840,1491146912,2727555424,4947175712

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

%C First differs from A308542 at a(12) = 1232, A308542(12) = 1184.

%C If this sequence counts product-free sets, A308542 counts product-closed sets.

%H Fausto A. C. Cariboni, <a href="/A326116/b326116.txt">Table of n, a(n) for n = 1..47</a>

%F For n > 0, a(n) = A326117(n) - 1.

%e The a(6) = 28 subsets:

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

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

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

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

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

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

%e {3,6} {3,4,6}

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

%e {4,6} {4,5,6}

%e {5,6}

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

%o (PARI)

%o a(n)={

%o my(recurse(k, ep)=

%o if(k > n, 1,

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

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

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

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

%o );

%o t);

%o );

%o recurse(2, 2);

%o } \\ _Andrew Howroyd_, Aug 25 2019

%Y Cf. A007865, A051026, A103580, A196724, A326020, A326023, A326076, A326078, A326079, A326081, A326117, A308542.

%K nonn

%O 1,2

%A _Gus Wiseman_, Jun 06 2019

%E Terms a(21)-a(36) from _Andrew Howroyd_, Aug 25 2019