login
A370582
Number of subsets of {1..n} such that it is possible to choose a different prime factor of each element.
21
1, 1, 2, 4, 6, 12, 20, 40, 52, 72, 116, 232, 320, 640, 1020, 1528, 1792, 3584, 4552, 9104, 12240, 17840, 27896, 55792, 67584, 83968, 130656, 150240, 198528, 397056, 507984, 1015968, 1115616, 1579168, 2438544, 3259680, 3730368, 7460736, 11494656, 16145952, 19078464, 38156928
OFFSET
0,3
FORMULA
a(p) = 2 * a(p-1) for prime p. - David A. Corneth, Feb 25 2024
a(n) = 2^n - A370583(n).
EXAMPLE
The a(0) = 1 through a(6) = 20 subsets:
{} {} {} {} {} {} {}
{2} {2} {2} {2} {2}
{3} {3} {3} {3}
{2,3} {4} {4} {4}
{2,3} {5} {5}
{3,4} {2,3} {6}
{2,5} {2,3}
{3,4} {2,5}
{3,5} {2,6}
{4,5} {3,4}
{2,3,5} {3,5}
{3,4,5} {3,6}
{4,5}
{4,6}
{5,6}
{2,3,5}
{2,5,6}
{3,4,5}
{3,5,6}
{4,5,6}
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], Length[Select[Tuples[If[#==1, {}, First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]>0&]], {n, 0, 10}]
CROSSREFS
The version for set-systems is A367902, ranks A367906, unlabeled A368095.
The complement for set-systems is A367903, ranks A367907, unlabeled A368094.
For unlabeled multiset partitions we have A368098, complement A368097.
Multisets of this type are ranked by A368100, complement A355529.
For divisors instead of factors we have A368110, complement A355740.
The version for factorizations is A368414, complement A368413.
The complement is counted by A370583.
For a unique choice we have A370584.
The maximal case is A370585.
Partial sums of A370586, complement A370587.
The version for partitions is A370592, complement A370593.
For binary indices instead of factors we have A370636, complement A370637.
A006530 gives greatest prime factor, least A020639.
A027746 lists prime factors, A112798 indices, length A001222.
A307984 counts Q-bases of logarithms of positive integers.
A355741 counts choices of a prime factor of each prime index.
Sequence in context: A078025 A178901 A164146 * A279245 A090906 A047141
KEYWORD
nonn
AUTHOR
Gus Wiseman, Feb 25 2024
EXTENSIONS
a(19) from David A. Corneth, Feb 25 2024
a(20)-a(41) from Alois P. Heinz, Feb 25 2024
STATUS
approved