cp's OEIS Frontend

A370583 Number of subsets of {1..n} such that it is not possible to choose a different prime factor of each element.

%I A370583 #9 Feb 27 2024 14:25:39
%S A370583 0,1,2,4,10,20,44,88,204,440,908,1816,3776,7552,15364,31240,63744,
%T A370583 127488,257592,515184,1036336,2079312,4166408,8332816,16709632,
%U A370583 33470464,66978208,134067488,268236928,536473856,1073233840,2146467680,4293851680,8588355424,17177430640
%N A370583 Number of subsets of {1..n} such that it is not possible to choose a different prime factor of each element.
%F A370583 a(n) = 2^n - A370582(n).
%e A370583 The a(0) = 0 through a(5) = 20 subsets:
%e A370583   .  {1}  {1}    {1}      {1}        {1}
%e A370583           {1,2}  {1,2}    {1,2}      {1,2}
%e A370583                  {1,3}    {1,3}      {1,3}
%e A370583                  {1,2,3}  {1,4}      {1,4}
%e A370583                           {2,4}      {1,5}
%e A370583                           {1,2,3}    {2,4}
%e A370583                           {1,2,4}    {1,2,3}
%e A370583                           {1,3,4}    {1,2,4}
%e A370583                           {2,3,4}    {1,2,5}
%e A370583                           {1,2,3,4}  {1,3,4}
%e A370583                                      {1,3,5}
%e A370583                                      {1,4,5}
%e A370583                                      {2,3,4}
%e A370583                                      {2,4,5}
%e A370583                                      {1,2,3,4}
%e A370583                                      {1,2,3,5}
%e A370583                                      {1,2,4,5}
%e A370583                                      {1,3,4,5}
%e A370583                                      {2,3,4,5}
%e A370583                                      {1,2,3,4,5}
%t A370583 Table[Length[Select[Subsets[Range[n]], Length[Select[Tuples[If[#==1,{},First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]==0&]],{n,0,10}]
%Y A370583 Multisets of this type are ranked by A355529, complement A368100.
%Y A370583 For divisors instead of factors we have A355740, complement A368110.
%Y A370583 The complement for set-systems is A367902, ranks A367906, unlabeled A368095.
%Y A370583 The version for set-systems is A367903, ranks A367907, unlabeled A368094.
%Y A370583 For non-isomorphic multiset partitions we have A368097, complement A368098.
%Y A370583 The version for factorizations is A368413, complement A368414.
%Y A370583 The complement is counted by A370582.
%Y A370583 For a unique choice we have A370584.
%Y A370583 Partial sums of A370587, complement A370586.
%Y A370583 The minimal case is A370591.
%Y A370583 The version for partitions is A370593, complement A370592.
%Y A370583 For binary indices instead of factors we have A370637, complement A370636.
%Y A370583 A006530 gives greatest prime factor, least A020639.
%Y A370583 A027746 lists prime factors, A112798 indices, length A001222.
%Y A370583 A355741 counts choices of a prime factor of each prime index.
%Y A370583 Cf. A000040, A000720, A001055, A001414, A003963, A005117, A045778, A355739, A355745, A367867, A367905, A368187.
%K A370583 nonn
%O A370583 0,3
%A A370583 _Gus Wiseman_, Feb 26 2024
%E A370583 a(19)-a(34) from _Alois P. Heinz_, Feb 27 2024