[go: up one dir, main page]

login
Search: a370637 -id:a370637
     Sort: relevance | references | number | modified | created      Format: long | short | data
Number of non-condensed integer factorizations of n into unordered factors > 1.
+10
31
0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0
OFFSET
1,32
COMMENTS
A multiset is condensed iff it is possible to choose a different divisor of each element.
EXAMPLE
The a(96) = 4 factorizations: (2*2*2*2*2*3), (2*2*2*2*6), (2*2*2*3*4), (2*2*2*12).
MATHEMATICA
facs[n_]:=If[n<=1, {{}}, Join @@ Table[Map[Prepend[#, d]&, Select[facs[n/d], Min @@ #>=d&]], {d, Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], Length[Select[Tuples[Divisors /@ #], UnsameQ@@#&]]==0&]], {n, 100}]
CROSSREFS
Partitions not of this type are counted by A239312, ranks A368110.
Factors instead of divisors: A368413, complement A368414, unique A370645.
Partitions of this type are counted by A370320, ranks A355740.
Subsets of this type: A370583 and A370637, complement A370582 and A370636.
The complement is counted by A370814, partitions A370592, ranks A368100.
For a unique choice we have A370815, partitions A370595, ranks A370810.
A000005 counts divisors.
A001055 counts factorizations, strict A045778.
A355731 counts choices of a divisor of each prime index, firsts A355732.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 04 2024
STATUS
approved
Number of condensed integer factorizations of n into unordered factors > 1.
+10
29
1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 2, 2, 1, 6, 2, 2, 2, 4, 1, 5, 1, 5, 2, 2, 2, 8, 1, 2, 2, 6, 1, 5, 1, 4, 4, 2, 1, 10, 2, 4, 2, 4, 1, 6, 2, 6, 2, 2, 1, 11, 1, 2, 4, 7, 2, 5, 1, 4, 2, 5, 1, 14, 1, 2, 4, 4, 2, 5, 1, 10, 4, 2, 1, 11, 2
OFFSET
1,4
COMMENTS
A multiset is condensed iff it is possible to choose a different divisor of each element.
EXAMPLE
The a(36) = 7 factorizations: (2*2*9), (2*3*6), (2*18), (3*3*4), (3*12), (4*9), (6*6), (36).
MATHEMATICA
facs[n_]:=If[n<=1, {{}}, Join @@ Table[Map[Prepend[#, d]&, Select[facs[n/d], Min @@ #>=d&]], {d, Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], Length[Select[Tuples[Divisors /@ #], UnsameQ@@#&]]>0&]], {n, 100}]
CROSSREFS
Partitions of this type are counted by A239312, ranks A368110.
Factors instead of divisors: A368414, complement A368413, unique A370645.
Partitions not of this type are counted by A370320, ranks A355740.
Subsets of this type: A370582 and A370636, complement A370583 and A370637.
The complement is counted by A370813, partitions A370593, ranks A355529.
For a unique choice we have A370815, partitions A370595, ranks A370810.
A000005 counts divisors.
A001055 counts factorizations, strict A045778.
A355731 counts choices of a divisor of each prime index, firsts A355732.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 04 2024
STATUS
approved
Number of subsets of {1..n} such that it is possible to choose a different binary index of each element.
+10
27
1, 2, 4, 7, 14, 24, 39, 61, 122, 203, 315, 469, 676, 952, 1307, 1771, 3542, 5708, 8432, 11877, 16123, 21415, 27835, 35757, 45343, 57010, 70778, 87384, 106479, 129304, 155802, 187223, 374446, 588130, 835800, 1124981, 1456282, 1841361, 2281772, 2791896, 3367162
OFFSET
0,2
COMMENTS
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
FORMULA
a(2^n - 1) = A367902(n).
Partial sums of A370639.
EXAMPLE
The a(0) = 1 through a(4) = 14 subsets:
{} {} {} {} {}
{1} {1} {1} {1}
{2} {2} {2}
{1,2} {3} {3}
{1,2} {4}
{1,3} {1,2}
{2,3} {1,3}
{1,4}
{2,3}
{2,4}
{3,4}
{1,2,4}
{1,3,4}
{2,3,4}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[Select[Subsets[Range[n]], Select[Tuples[bpe/@#], UnsameQ@@#&]!={}&]], {n, 0, 10}]
CROSSREFS
Simple graphs of this type are counted by A133686, covering A367869.
Unlabeled graphs of this type are counted by A134964, complement A140637.
Simple graphs not of this type are counted by A367867, covering A367868.
Set systems of this type are counted by A367902, ranks A367906.
Set systems not of this type are counted by A367903, ranks A367907.
Set systems uniquely of this type are counted by A367904, ranks A367908.
Unlabeled multiset partitions of this type are A368098, complement A368097.
A version for MM-numbers of multisets is A368100, complement A355529.
Factorizations are counted by A368414/A370814, complement A368413/A370813.
For prime indices we have A370582, differences A370586.
The complement for prime indices is A370583, differences A370587.
The complement is A370637, differences A370589, without ones A370643.
The case of a unique choice is A370638, maxima A370640, differences A370641.
First differences are A370639.
The minimal case of the complement is A370642, without ones A370644.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A058891 counts set-systems, A003465 covering, A323818 connected.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A326031 gives weight of the set-system with BII-number n.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 08 2024
EXTENSIONS
a(19)-a(40) from Alois P. Heinz, Mar 09 2024
STATUS
approved
Number of subsets of {1..n} such that it is not possible to choose a different prime factor of each element.
+10
25
0, 1, 2, 4, 10, 20, 44, 88, 204, 440, 908, 1816, 3776, 7552, 15364, 31240, 63744, 127488, 257592, 515184, 1036336, 2079312, 4166408, 8332816, 16709632, 33470464, 66978208, 134067488, 268236928, 536473856, 1073233840, 2146467680, 4293851680, 8588355424, 17177430640
OFFSET
0,3
FORMULA
a(n) = 2^n - A370582(n).
EXAMPLE
The a(0) = 0 through a(5) = 20 subsets:
. {1} {1} {1} {1} {1}
{1,2} {1,2} {1,2} {1,2}
{1,3} {1,3} {1,3}
{1,2,3} {1,4} {1,4}
{2,4} {1,5}
{1,2,3} {2,4}
{1,2,4} {1,2,3}
{1,3,4} {1,2,4}
{2,3,4} {1,2,5}
{1,2,3,4} {1,3,4}
{1,3,5}
{1,4,5}
{2,3,4}
{2,4,5}
{1,2,3,4}
{1,2,3,5}
{1,2,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], Length[Select[Tuples[If[#==1, {}, First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]==0&]], {n, 0, 10}]
CROSSREFS
Multisets of this type are ranked by A355529, complement A368100.
For divisors instead of factors we have A355740, complement A368110.
The complement for set-systems is A367902, ranks A367906, unlabeled A368095.
The version for set-systems is A367903, ranks A367907, unlabeled A368094.
For non-isomorphic multiset partitions we have A368097, complement A368098.
The version for factorizations is A368413, complement A368414.
The complement is counted by A370582.
For a unique choice we have A370584.
Partial sums of A370587, complement A370586.
The minimal case is A370591.
The version for partitions is A370593, complement A370592.
For binary indices instead of factors we have A370637, complement A370636.
A006530 gives greatest prime factor, least A020639.
A027746 lists prime factors, A112798 indices, length A001222.
A355741 counts choices of a prime factor of each prime index.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Feb 26 2024
EXTENSIONS
a(19)-a(34) from Alois P. Heinz, Feb 27 2024
STATUS
approved
Number of maximal subsets of {1..n} such that it is possible to choose a different prime factor of each element.
+10
22
1, 1, 1, 1, 2, 2, 5, 5, 7, 11, 25, 25, 38, 38, 84, 150, 178, 178, 235, 235, 341, 579, 1235, 1235
OFFSET
0,5
COMMENTS
First differs from A307984 at a(21) = 579, A307984(21) = 578. The difference is due to the set {10,11,13,14,15,17,19,21}, which is not a basis because log(10) + log(21) = log(14) + log(15).
Also length-pi(n) subsets of {1..n} such that it is possible to choose a different prime factor of each element.
EXAMPLE
The a(0) = 1 through a(8) = 7 subsets:
{} {} {2} {2,3} {2,3} {2,3,5} {2,3,5} {2,3,5,7} {2,3,5,7}
{3,4} {3,4,5} {2,5,6} {2,5,6,7} {2,5,6,7}
{3,4,5} {3,4,5,7} {3,4,5,7}
{3,5,6} {3,5,6,7} {3,5,6,7}
{4,5,6} {4,5,6,7} {3,5,7,8}
{4,5,6,7}
{5,6,7,8}
MATHEMATICA
Table[Length[Select[Subsets[Range[n], {PrimePi[n]}], Length[Select[Tuples[If[#==1, {}, First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]>0&]], {n, 0, 10}]
CROSSREFS
Multisets of this type are ranked by A368100, complement A355529.
Factorizations of this type are counted by A368414, complement A368413.
The version for set-systems is A368601, max of A367902 (complement A367903).
This is the maximal case of A370582, complement A370583, cf. A370584.
A different kind of maximality is A370586, complement A370587.
The case containing n is A370590, complement A370591.
Partitions of this type (choosable) are A370592, complement A370593.
For binary indices instead of factors we have A370640, cf. A370636, 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.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Feb 26 2024
STATUS
approved
Number of subsets of {1..n} such that it is possible to choose a different prime factor of each element.
+10
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.
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
Number of subsets of {1..n} such that only one set can be obtained by choosing a different prime factor of each element.
+10
21
1, 1, 2, 4, 6, 12, 18, 36, 48, 68, 104, 208, 284, 568, 888, 1296, 1548, 3096, 3968
OFFSET
0,3
COMMENTS
For example, the only choice of a different prime factor of each element of (4,5,6) is (2,5,3).
EXAMPLE
The a(0) = 1 through a(6) = 18 subsets:
{} {} {} {} {} {} {}
{2} {2} {2} {2} {2}
{3} {3} {3} {3}
{2,3} {4} {4} {4}
{2,3} {5} {5}
{3,4} {2,3} {2,3}
{2,5} {2,5}
{3,4} {2,6}
{3,5} {3,4}
{4,5} {3,5}
{2,3,5} {3,6}
{3,4,5} {4,5}
{4,6}
{2,3,5}
{2,5,6}
{3,4,5}
{3,5,6}
{4,5,6}
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], Length[Union[Sort/@Select[Tuples[If[#==1, {}, First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]]==1&]], {n, 0, 10}]
CROSSREFS
For divisors instead of factors we have A051026, cf. A368110, A355740.
The version for set-systems is A367904, ranks A367908.
Multisets of this type are ranked by A368101, cf. A368100, A355529.
For existence we have A370582, differences A370586.
For nonexistence we have A370583, differences A370587.
Maximal sets of this type are counted by A370585.
The version for partitions is A370594, cf. A370592, A370593.
For binary indices instead of factors we have A370638, cf. A370636, A370637.
The version for factorizations is A370645, cf. A368414, A368413.
For unlabeled multiset partitions we have A370646, cf. A368098, A368097.
A006530 gives greatest prime factor, least A020639.
A027746 lists prime factors, A112798 indices, length A001222.
A355741 counts ways to choose a prime factor of each prime index.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Feb 26 2024
STATUS
approved
Number of integer partitions of n such that only one set can be obtained by choosing a different prime factor of each part.
+10
16
1, 0, 1, 1, 1, 2, 0, 3, 3, 4, 3, 4, 5, 5, 8, 10, 11, 7, 14, 13, 19, 23, 24, 20, 30, 33, 40, 47, 49, 55, 53, 72, 80, 90, 92, 110, 110, 132, 154, 169, 180, 201, 218, 246, 281, 302, 323, 348, 396, 433, 482, 530, 584, 618, 670, 754, 823, 903, 980, 1047, 1137
OFFSET
0,6
EXAMPLE
The partition (10,6,4) has unique choice (5,3,2) so is counted under a(20).
The a(0) = 1 through a(12) = 5 partitions:
() . (2) (3) (4) (5) . (7) (8) (9) (6,4) (11) (6,6)
(3,2) (4,3) (5,3) (5,4) (7,3) (7,4) (7,5)
(5,2) (6,2) (6,3) (5,3,2) (8,3) (10,2)
(7,2) (9,2) (5,4,3)
(7,3,2)
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], Length[Union[Sort/@Select[Tuples[If[#==1, {}, First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]]==1&]], {n, 0, 30}]
CROSSREFS
The version for set-systems is A367904, ranks A367908.
Multisets of this type are ranked by A368101, cf. A368100, A355529.
The version for subsets is A370584, cf. A370582, A370583, A370586, A370587.
Maximal sets of this type are counted by A370585.
For existence we have A370592.
For nonexistence we have A370593.
For divisors instead of factors we have A370595.
For subsets and binary indices we have A370638, cf. A370636, A370637.
The version for factorizations is A370645, cf. A368414, A368413.
These partitions have ranks A370647.
A006530 gives greatest prime factor, least A020639.
A027746 lists prime factors, A112798 indices, length A001222.
A355741 counts ways to choose a prime factor of each prime index.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Feb 29 2024
STATUS
approved
Number of subsets of {1..n} such that a unique set can be obtained by choosing a different binary index of each element.
+10
15
1, 2, 4, 6, 12, 19, 30, 45, 90, 147, 230, 343, 504, 716, 994, 1352, 2704, 4349, 6469
OFFSET
0,2
COMMENTS
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
FORMULA
a(2^n - 1) = A370818(n).
EXAMPLE
The set {3,4} has binary indices {{1,2},{3}}, with two choices {1,3}, {2,3}, so is not counted under a(4).
The a(0) = 1 through a(5) = 19 subsets:
{} {} {} {} {} {}
{1} {1} {1} {1} {1}
{2} {2} {2} {2}
{1,2} {1,2} {4} {4}
{1,3} {1,2} {1,2}
{2,3} {1,3} {1,3}
{1,4} {1,4}
{2,3} {1,5}
{2,4} {2,3}
{1,2,4} {2,4}
{1,3,4} {4,5}
{2,3,4} {1,2,4}
{1,2,5}
{1,3,4}
{1,3,5}
{2,3,4}
{2,3,5}
{2,4,5}
{3,4,5}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[Select[Subsets[Range[n]], Length[Union[Sort /@ Select[Tuples[bpe/@#], UnsameQ@@#&]]]==1&]], {n, 0, 10}]
CROSSREFS
Set systems of this type are counted by A367904, ranks A367908.
A version for MM-numbers of multisets is A368101.
For prime indices we have A370584.
This is the unique version of A370636, complement A370637.
The maximal case is A370640, differences A370641.
Factorizations of this type are counted by A370645.
The case A370818 is the restriction to A000225.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A058891 counts set-systems, A003465 covering, A323818 connected.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Mar 09 2024
STATUS
approved
Number of maximal subsets of {1..n} such that it is possible to choose a different binary index of each element.
+10
12
1, 1, 1, 3, 3, 8, 17, 32, 32, 77, 144, 242, 383, 580, 843, 1201, 1201, 2694, 4614, 7096, 10219, 14186, 19070, 25207, 32791, 42160
OFFSET
0,4
COMMENTS
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
Also choices of A029837(n) elements of {1..n} such that it is possible to choose a different binary index of each.
EXAMPLE
The a(0) = 1 through a(6) = 17 subsets:
{} {1} {1,2} {1,2} {1,2,4} {1,2,4} {1,2,4}
{1,3} {1,3,4} {1,2,5} {1,2,5}
{2,3} {2,3,4} {1,3,4} {1,2,6}
{1,3,5} {1,3,4}
{2,3,4} {1,3,5}
{2,3,5} {1,3,6}
{2,4,5} {1,4,6}
{3,4,5} {1,5,6}
{2,3,4}
{2,3,5}
{2,3,6}
{2,4,5}
{2,5,6}
{3,4,5}
{3,4,6}
{3,5,6}
{4,5,6}
The a(0) = 1 through a(6) = 17 set-systems:
{1} {1}{2} {1}{2} {1}{2}{3} {1}{2}{3} {1}{2}{3}
{1}{12} {1}{12}{3} {1}{12}{3} {1}{12}{3}
{2}{12} {2}{12}{3} {1}{2}{13} {1}{2}{13}
{2}{12}{3} {1}{2}{23}
{2}{3}{13} {1}{3}{23}
{1}{12}{13} {2}{12}{3}
{12}{3}{13} {2}{3}{13}
{2}{12}{13} {1}{12}{13}
{1}{12}{23}
{1}{13}{23}
{12}{3}{13}
{12}{3}{23}
{2}{12}{13}
{2}{12}{23}
{2}{13}{23}
{3}{13}{23}
{12}{13}{23}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[Select[Subsets[Range[n], {IntegerLength[n, 2]}], Select[Tuples[bpe/@#], UnsameQ@@#&]!={}&]], {n, 0, 10}]
CROSSREFS
Dominated by A357812.
The version for set-systems is A368601, max of A367902 (complement A367903).
For prime indices we have A370585, with n A370590, see also A370591.
This is the maximal case of A370636 (complement A370637).
The case of a unique choice is A370638.
The case containing n is A370641, non-maximal A370639.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A058891 counts set-systems, A003465 covering, A323818 connected.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A307984 counts Q-bases of logarithms of positive integers.
A355741 counts choices of a prime factor of each prime index.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Mar 10 2024
STATUS
approved

Search completed in 0.089 seconds