|
%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
|
