cp's OEIS Frontend

A326076 Number of subsets of {1..n} containing all of their integer products <= n.

%I A326076 #13 Aug 30 2019 21:46:51
%S A326076 1,2,4,8,12,24,44,88,152,232,444,888,1576,3152,6136,11480,17112,34224,
%T A326076 63504,127008,232352,442208,876944,1753888,3138848,4895328,9739152,
%U A326076 18141840,34044720,68089440,123846624,247693248,469397440,924014144,1845676384,3469128224,5182711584
%N A326076 Number of subsets of {1..n} containing all of their integer products <= n.
%C A326076 The strict case is A326081.
%F A326076 a(n) = 2*A326114(n) for n > 0. - _Andrew Howroyd_, Aug 30 2019
%e A326076 The a(0) = 1 through a(4) = 12 sets:
%e A326076   {}  {}   {}     {}       {}
%e A326076       {1}  {1}    {1}      {1}
%e A326076            {2}    {2}      {3}
%e A326076            {1,2}  {3}      {4}
%e A326076                   {1,2}    {1,3}
%e A326076                   {1,3}    {1,4}
%e A326076                   {2,3}    {2,4}
%e A326076                   {1,2,3}  {3,4}
%e A326076                            {1,2,4}
%e A326076                            {1,3,4}
%e A326076                            {2,3,4}
%e A326076                            {1,2,3,4}
%e A326076 The a(6) = 44 sets:
%e A326076   {}  {1}  {1,3}  {1,2,4}  {1,2,4,5}  {1,2,3,4,6}  {1,2,3,4,5,6}
%e A326076       {3}  {1,4}  {1,3,4}  {1,2,4,6}  {1,2,4,5,6}
%e A326076       {4}  {1,5}  {1,3,5}  {1,3,4,5}  {1,3,4,5,6}
%e A326076       {5}  {1,6}  {1,3,6}  {1,3,4,6}  {2,3,4,5,6}
%e A326076       {6}  {2,4}  {1,4,5}  {1,3,5,6}
%e A326076            {3,4}  {1,4,6}  {1,4,5,6}
%e A326076            {3,5}  {1,5,6}  {2,3,4,6}
%e A326076            {3,6}  {2,4,5}  {2,4,5,6}
%e A326076            {4,5}  {2,4,6}  {3,4,5,6}
%e A326076            {4,6}  {3,4,5}
%e A326076            {5,6}  {3,4,6}
%e A326076                   {3,5,6}
%e A326076                   {4,5,6}
%t A326076 Table[Length[Select[Subsets[Range[n]],SubsetQ[#,Select[Times@@@Tuples[#,2],#<=n&]]&]],{n,0,10}]
%o A326076 (PARI)
%o A326076 a(n)={
%o A326076     my(lim=vector(n, k, sqrtint(k)));
%o A326076     my(accept(b, k)=for(i=2, lim[k], if(k%i ==0 && bittest(b, i) && bittest(b, k/i), return(0))); 1);
%o A326076     my(recurse(k, b)=
%o A326076       my(m=1);
%o A326076       for(j=max(2*k, n\2+1), min(2*k+1, n), if(accept(b, j), m*=2));
%o A326076       k++;
%o A326076       m*if(k > n\2, 1, self()(k, b + (1<<k)) + if(accept(b, k), self()(k, b)))
%o A326076    );
%o A326076    recurse(0, 0);
%o A326076 } \\ _Andrew Howroyd_, Aug 30 2019
%Y A326076 Cf. A007865, A051026, A103580, A196724, A326020, A326023, A326078, A326079, A326081.
%K A326076 nonn
%O A326076 0,2
%A A326076 _Gus Wiseman_, Jun 05 2019
%E A326076 a(16)-a(30) from _Andrew Howroyd_, Aug 16 2019
%E A326076 Terms a(31) and beyond from _Andrew Howroyd_, Aug 30 2019