A370582 - OEIS

%I #24 Feb 26 2024 22:44:34

%S 1,1,2,4,6,12,20,40,52,72,116,232,320,640,1020,1528,1792,3584,4552,

%T 9104,12240,17840,27896,55792,67584,83968,130656,150240,198528,397056,

%U 507984,1015968,1115616,1579168,2438544,3259680,3730368,7460736,11494656,16145952,19078464,38156928

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

%F a(p) = 2 * a(p-1) for prime p. - _David A. Corneth_, Feb 25 2024

%F a(n) = 2^n - A370583(n).

%e The a(0) = 1 through a(6) = 20 subsets:

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

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

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

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

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

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

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

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

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

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

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

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

%e                                       {4,5}

%e                                       {4,6}

%e                                       {5,6}

%e                                       {2,3,5}

%e                                       {2,5,6}

%e                                       {3,4,5}

%e                                       {3,5,6}

%e                                       {4,5,6}

%t Table[Length[Select[Subsets[Range[n]],Length[Select[Tuples[If[#==1,{},First/@FactorInteger[#]]&/@#],UnsameQ@@#&]]>0&]],{n,0,10}]

%Y The version for set-systems is A367902, ranks A367906, unlabeled A368095.

%Y The complement for set-systems is A367903, ranks A367907, unlabeled A368094.

%Y For unlabeled multiset partitions we have A368098, complement A368097.

%Y Multisets of this type are ranked by A368100, complement A355529.

%Y For divisors instead of factors we have A368110, complement A355740.

%Y The version for factorizations is A368414, complement A368413.

%Y The complement is counted by A370583.

%Y For a unique choice we have A370584.

%Y The maximal case is A370585.

%Y Partial sums of A370586, complement A370587.

%Y The version for partitions is A370592, complement A370593.

%Y For binary indices instead of factors we have A370636, complement A370637.

%Y A006530 gives greatest prime factor, least A020639.

%Y A027746 lists prime factors, A112798 indices, length A001222.

%Y A307984 counts Q-bases of logarithms of positive integers.

%Y A355741 counts choices of a prime factor of each prime index.

%Y Cf. A000040, A000720, A001055, A001414, A003963, A005117, A045778, A133686, A355739, A355744, A355745, A367905.

%K nonn

%O 0,3

%A _Gus Wiseman_, Feb 25 2024

%E a(19) from _David A. Corneth_, Feb 25 2024

%E a(20)-a(41) from _Alois P. Heinz_, Feb 25 2024