A355739 -id:A355739 - cp's OEIS frontend

A367912 Number of multisets that can be obtained by choosing a binary index of each binary index of n.

1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 3, 3, 3, 3, 5, 5, 5, 5, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 8, 8, 8, 8

Offset: 0

Gus Wiseman, Dec 12 2023

nonn

A binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion. For example, 18 has reversed binary expansion (0,1,0,0,1) and binary indices {2,5}.

The run-lengths are all 4 or 8.

			The binary indices of binary indices of 52 are {{1,2},{1,3},{2,3}}, with multiset choices {1,1,2}, {1,1,3}, {1,2,2}, {1,2,3}, {1,3,3}, {2,2,3}, {2,3,3}, so a(52) = 7.

Positions of ones are A253317.
The version for multisets and divisors is A355733, for sequences A355731.
The version for multisets is A355744, for sequences A355741.
For a sequence of distinct choices we have A367905, firsts A367910.
Positions of first appearances are A367913, sorted A367915.
Choosing a sequence instead of multiset gives A368109, firsts A368111.
Choosing a set instead of multiset gives A368183, firsts A368184.
A048793 lists binary indices, length A000120, sum A029931.
A058891 counts set-systems, covering A003465, connected A323818.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
Cf. A072639, A309326, A326031, A326702, A326753, A355735, A355739, A355740, A355745, A367771, A367906.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]],1];
Table[Length[Union[Sort/@Tuples[bpe/@bpe[n]]]], {n,0,100}]

A370802 Positive integers with as many prime factors (A001222) as distinct divisors of prime indices (A370820).

Original entry on oeis.org

1, 2, 6, 9, 10, 22, 25, 28, 30, 34, 42, 45, 62, 63, 66, 75, 82, 92, 98, 99, 102, 104, 110, 118, 121, 134, 140, 147, 152, 153, 156, 166, 170, 186, 210, 218, 228, 230, 232, 234, 246, 254, 260, 275, 276, 279, 289, 308, 310, 314, 315, 330, 342, 343, 344, 348, 350

Offset: 1

Gus Wiseman, Mar 14 2024

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

All squarefree terms are even.

			The prime indices of 1617 are {2,4,4,5}, with distinct divisors {1,2,4,5}, so 1617 is in the sequence.
The terms together with their prime indices begin:
    1: {}
    2: {1}
    6: {1,2}
    9: {2,2}
   10: {1,3}
   22: {1,5}
   25: {3,3}
   28: {1,1,4}
   30: {1,2,3}
   34: {1,7}
   42: {1,2,4}
   45: {2,2,3}
   62: {1,11}
   63: {2,2,4}
   66: {1,2,5}
   75: {2,3,3}
   82: {1,13}
   92: {1,1,9}
   98: {1,4,4}
   99: {2,2,5}
  102: {1,2,7}
  104: {1,1,1,6}

For factors instead of divisors on the RHS we have A319899.
A version for binary indices is A367917.
For (greater than) instead of (equal) we have A370348, counted by A371171.
The RHS is A370820, for prime factors instead of divisors A303975.
Partitions of this type are counted by A371130, strict A371128.
For divisors instead of factors on LHS we have A371165, counted by A371172.
For only distinct prime factors on LHS we have A371177, counted by A371178.
Other inequalities: A371166, A371167, A371169, A371170.
A000005 counts divisors.
A001221 counts distinct prime factors.
A027746 lists prime factors, A112798 indices, length A001222.
A239312 counts divisor-choosable partitions, ranks A368110.
A355731 counts choices of a divisor of each prime index, firsts A355732.
A370320 counts non-divisor-choosable partitions, ranks A355740.
Cf. A000792, A003963, A355529, A355737, A355739, A355741, A368100, A370808, A370813, A370814, A371127.

Select[Range[100],PrimeOmega[#]==Length[Union @@ Divisors/@PrimePi/@First/@If[#==1,{},FactorInteger[#]]]&]

A001222(a(n)) = A370820(a(n)).

A370584 Number of subsets of {1..n} such that only one set can be obtained by choosing a different prime factor of each element.

Original entry on oeis.org

1, 1, 2, 4, 6, 12, 18, 36, 48, 68, 104, 208, 284, 568, 888, 1296, 1548, 3096, 3968, 7936, 10736, 15440, 24008, 48016, 58848, 73680, 114368, 132608, 176240, 352480, 449824, 899648, 994976, 1399968, 2160720, 2859584, 3296048, 6592096, 10156672, 14214576, 16892352

Offset: 0

Gus Wiseman, Feb 26 2024

nonn

For example, the only choice of a different prime factor of each element of (4,5,6) is (2,5,3).

			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}

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.
Cf. A000040, A000720, A003963, A005117, A045778, A133686, A307984, A355739, A355744, A355745, A367905.

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

More terms from Jinyuan Wang, Mar 28 2025

A367769 Number of finite sets of nonempty non-singleton subsets of {1..n} contradicting a strict version of the axiom of choice.

Original entry on oeis.org

0, 0, 0, 1, 1490, 67027582, 144115188036455750, 1329227995784915872903806998967001298, 226156424291633194186662080095093570025917938800079226639565284090686126876

Offset: 0

Gus Wiseman, Dec 05 2023

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

Includes all set-systems with more edges than covered vertices, but this condition is not sufficient.

			The a(3) = 1 set-system is: {{1,2},{1,3},{2,3},{1,2,3}}.

Wikipedia, Axiom of choice.

Set-systems without singletons are counted by A016031, covering A323816.
The complement is A367770, with singletons allowed A367902 (ranks A367906).
The version for simple graphs is A367867, covering A367868.
The version allowing singletons and empty edges is A367901.
The version allowing singletons is A367903, ranks A367907.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems.
Cf. A007716, A092918, A102896, A283877, A306445, A326031, A355739, A355740, A355741, A367904, A367905.

Table[Length[Select[Subsets[Select[Subsets[Range[n]], Length[#]>1&]], Select[Tuples[#], UnsameQ@@#&]=={}&]], {n,0,3}]

a(n) = 2^(2^n-n-1) - A367770(n) = A016031(n+1) - A367770(n). - Christian Sievers, Jul 28 2024

a(6)-a(8) from Christian Sievers, Jul 28 2024

A370637 Number of subsets of {1..n} such that it is not possible to choose a different binary index of each element.

Original entry on oeis.org

0, 0, 0, 1, 2, 8, 25, 67, 134, 309, 709, 1579, 3420, 7240, 15077, 30997, 61994, 125364, 253712, 512411, 1032453, 2075737, 4166469, 8352851, 16731873, 33497422, 67038086, 134130344, 268328977, 536741608, 1073586022, 2147296425, 4294592850, 8589346462, 17179033384

Offset: 0

Gus Wiseman, Mar 08 2024

nonn

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.

			The a(0) = 0 through a(5) = 8 subsets:
  .  .  .  {1,2,3}  {1,2,3}    {1,2,3}
                    {1,2,3,4}  {1,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}

Wikipedia, Axiom of choice.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

Simple graphs not of this type are counted by A133686, covering A367869.
Unlabeled graphs of this type are counted by A140637, complement A134964.
Simple graphs of this type are counted by A367867, covering A367868.
Set systems not of this type are counted by A367902, ranks A367906.
Set systems of this type are counted by A367903, ranks A367907.
Set systems uniquely not of this type are counted by A367904, ranks A367908.
Unlabeled multiset partitions of this type are A368097, complement A368098.
A version for MM-numbers of multisets is A355529, complement A368100.
Factorizations are counted by A368413/A370813, complement A368414/A370814.
The complement for prime indices is A370582, differences A370586.
For prime indices we have A370583, differences A370587.
First differences are A370589.
The complement is counted by A370636, differences A370639.
The case without ones is A370643.
The version for a unique choice is A370638, maxima A370640, diffs A370641.
The minimal case 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.
Cf. A000612, A072639, A355739, A355740, A367772, A367905, A367909, A367912, A368094, A368095, A368109.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Table[Length[Select[Subsets[Range[n]], Select[Tuples[bpe/@#],UnsameQ@@#&]=={}&]],{n,0,10}]

a(2^n - 1) = A367903(n).

Partial sums of A370589.

a(21)-a(34) from Alois P. Heinz, Mar 09 2024

A370348 Numbers k such that there are fewer divisors of prime indices of k than there are prime indices of k.

Original entry on oeis.org

4, 8, 12, 16, 18, 20, 24, 27, 32, 36, 40, 44, 48, 50, 54, 56, 60, 64, 68, 72, 80, 81, 84, 88, 90, 96, 100, 108, 112, 120, 124, 125, 126, 128, 132, 135, 136, 144, 150, 160, 162, 164, 168, 176, 180, 184, 189, 192, 196, 198, 200, 204, 208, 216, 220, 224, 225, 236, 240, 242, 243, 248, 250, 252, 256

Offset: 1

Robert Israel, Feb 15 2024

nonn

No multiple of a term is a term of A368110.

			a(5) = 18 is a term because the prime indices of 18 = 2 * 3^2 are 1,2,2, and there are 3 of these but only 2 divisors of prime indices, namely 1 and 2.

Robert Israel, Table of n, a(n) for n = 1..10000

The LHS is A370820, firsts A371131.
The version for equality is A370802, counted by A371130, strict A371128.
For submultisets instead of parts on the RHS we get A371167.
The opposite version is A371168, counted by A371173.
The weak version is A371169.
The complement is A371170.
Partitions of this type are counted by A371171.
A000005 counts divisors.
A001221 counts distinct prime factors.
A027746 lists prime factors, indices A112798, length A001222.
A355731 counts choices of a divisor of each prime index, firsts A355732.
Cf. A003963, A239312, A303975, A319899, A355529, A355739, A370808, A371127.

filter:= proc(n) uses numtheory; local F,D,t;
   F:= map(t -> [pi(t[1]),t[2]], ifactors(n)[2]);
   D:= `union`(seq(divisors(t[1]), t = F));
   nops(D) < add(t[2], t = F)
end proc:
select(filter, [$1..300]);

filter[n_] := Module[{F, d},
    F = {PrimePi[#[[1]]], #[[2]]}& /@ FactorInteger[n];
    d = Union[Flatten[Divisors /@ F[[All, 1]]]];
    Length[d] < Total[F[[All, 2]]]];
Select[Range[300], filter] (* Jean-François Alcover, Mar 08 2024, after Maple code *)

A370803 Number of integer partitions of n such that more than one set can be obtained by choosing a different divisor of each part.

Original entry on oeis.org

0, 0, 1, 1, 1, 3, 2, 4, 5, 7, 10, 11, 15, 18, 25, 28, 39, 45, 59, 66, 83, 101, 123, 150, 176, 213, 252, 301, 352, 426, 497, 589, 684, 802, 939, 1095, 1270, 1480, 1718, 1985, 2289, 2645, 3056, 3489, 4019, 4590, 5289, 6014, 6877, 7817, 8955, 10134, 11551, 13085

Offset: 0

Gus Wiseman, Mar 03 2024

nonn

			The partition (6,4,4,1) has two choices, namely {1,2,4,6} and {1,2,3,4}, so is counted under a(15).
The a(0) = 0 through a(13) = 18 partitions (A..D = 10..13):
  .  .  2   3   4   5    6    7    8     9     A     B     C     D
                    32   42   43   44    54    64    65    66    76
                    41        52   53    63    73    74    75    85
                              61   62    72    82    83    84    94
                                   431   81    91    92    93    A3
                                         432   433   A1    A2    B2
                                         621   532   443   543   C1
                                               541   542   633   544
                                               622   632   642   643
                                               631   641   651   652
                                                     821   732   661
                                                           741   742
                                                           822   832
                                                           831   841
                                                           921   922
                                                                 A21
                                                                 5431
                                                                 6421

Including partitions with one choice gives A239312, complement A370320.
For a unique choice we have A370595, ranks A370810.
These partitions have ranks A370811.
A000005 counts divisors.
A000041 counts integer partitions, strict A000009.
A027746 lists prime factors, A112798 indices, length A001222.
A355731 counts choices of a divisor of each prime index, firsts A355732.
A355733 counts divisor-choices of prime indices.
A355741, A355744, A355745 choose prime factors of prime indices.
A370592 counts factor-choosable partitions, ranks A368100.
A370593 counts non-factor-choosable partitions, ranks A355529.
Cf. A355739, A368110, A370594, A370804, A370805, A370808, A370814.

Table[Length[Select[IntegerPartitions[n],Length[Union[Sort /@ Select[Tuples[Divisors/@#],UnsameQ@@#&]]]>1&]],{n,0,30}]

a(n) = A239312(n) - A370595(n). - Jinyuan Wang, Feb 14 2025

More terms from Jinyuan Wang, Feb 14 2025

A367770 Number of sets of nonempty non-singleton subsets of {1..n} satisfying a strict version of the axiom of choice.

Original entry on oeis.org

1, 1, 2, 15, 558, 81282, 39400122, 61313343278, 309674769204452

Offset: 0

Gus Wiseman, Dec 05 2023

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

Excludes all set-systems with more edges than covered vertices, but this condition is not sufficient.

			The a(3) = 15 set-systems:
  {}
  {{1,2}}
  {{1,3}}
  {{2,3}}
  {{1,2,3}}
  {{1,2},{1,3}}
  {{1,2},{2,3}}
  {{1,2},{1,2,3}}
  {{1,3},{2,3}}
  {{1,3},{1,2,3}}
  {{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,2,3}}
  {{1,2},{2,3},{1,2,3}}
  {{1,3},{2,3},{1,2,3}}

Wikipedia, Axiom of choice.

Set-systems without singletons are counted by A016031, covering A323816.
The version for simple graphs is A133686, covering A367869.
The complement is counted by A367769.
The complement allowing singletons and empty sets is A367901.
Allowing singletons gives A367902, ranks A367906.
The complement allowing singletons is A367903, ranks A367907.
These set-systems have ranks A367906 /\ A326781.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A059201, A083323, A092918, A102896, A283877, A305000, A306445, A355739, A355740, A367904, A367905.

Table[Length[Select[Subsets[Select[Subsets[Range[n]], Length[#]>1&]], Select[Tuples[#], UnsameQ@@#&]!={}&]],{n,0,3}]

a(6)-a(8) from Christian Sievers, Jul 28 2024

A355735 Number of ways to choose a divisor of each prime index of n (taken in weakly increasing order) such that the result is weakly increasing.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 3, 2, 2, 2, 4, 3, 3, 1, 2, 3, 4, 2, 5, 2, 3, 2, 3, 4, 4, 3, 4, 3, 2, 1, 3, 2, 4, 3, 6, 4, 7, 2, 2, 5, 4, 2, 4, 3, 4, 2, 6, 3, 3, 4, 5, 4, 3, 3, 7, 4, 2, 3, 6, 2, 7, 1, 6, 3, 2, 2, 5, 4, 6, 3, 4, 6, 4, 4, 4, 7, 4, 2, 5, 2, 2, 5, 3, 4, 7

Offset: 1

Gus Wiseman, Jul 16 2022

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The a(15) = 3 ways are: (1,1), (1,3), (2,3).
The a(18) = 3 ways are: (1,1,1), (1,1,2), (1,2,2).
The a(2) = 1 through a(19) = 4 ways:
  1  1  11  1  11  1  111  11  11  1  111  1  11  11  1111  1  111  1
     2      3  12  2       12  13  5  112  2  12  13        7  112  2
                   4       22              3  14  23           122  4
                                           6                        8

Wikipedia, Cartesian product.

Allowing any choice of divisors gives A355731, firsts A355732.
Choosing a multiset instead of sequence gives A355733, firsts A355734.
Positions of first appearances are A355736.
Choosing only prime divisors gives A355745, variations A355741, A355744.
The reverse version is A355749.
A000005 counts divisors.
A001414 adds up distinct prime divisors, counted by A001221.
A003963 multiplies together the prime indices of n.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A061395 selects the maximum prime index.
A120383 lists numbers divisible by all of their prime indices.
A324850 lists numbers divisible by the product of their prime indices.
Cf. A000720, A076610, A316524, A335433, A335448, A340827, A340852, A344616, A355737, A355739, A355740, A355742.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Select[Tuples[Divisors/@primeMS[n]],LessEqual@@#&]],{n,100}]

A370586 Number of subsets of {1..n} containing n such that it is possible to choose a different prime factor of each element (choosable).

Original entry on oeis.org

0, 0, 1, 2, 2, 6, 8, 20, 12, 20, 44, 116, 88, 320, 380, 508, 264, 1792, 968, 4552, 3136, 5600, 10056, 27896, 11792, 16384, 46688, 19584, 48288, 198528, 110928, 507984, 99648, 463552, 859376, 821136, 470688, 3730368, 4033920, 4651296, 2932512, 19078464

Offset: 0

Gus Wiseman, Feb 26 2024

nonn

			The a(0) = 0 through a(7) = 20 subsets:
  .  .  {2}  {3}    {4}    {5}      {6}      {7}
             {2,3}  {3,4}  {2,5}    {2,6}    {2,7}
                           {3,5}    {3,6}    {3,7}
                           {4,5}    {4,6}    {4,7}
                           {2,3,5}  {5,6}    {5,7}
                           {3,4,5}  {2,5,6}  {6,7}
                                    {3,5,6}  {2,3,7}
                                    {4,5,6}  {2,5,7}
                                             {2,6,7}
                                             {3,4,7}
                                             {3,5,7}
                                             {3,6,7}
                                             {4,5,7}
                                             {4,6,7}
                                             {5,6,7}
                                             {2,3,5,7}
                                             {2,5,6,7}
                                             {3,4,5,7}
                                             {3,5,6,7}
                                             {4,5,6,7}

First differences of A370582, complement A370583, cf. A370584.
Maximal choosable sets are counted by A370585.
The complement is counted by A370587.
For a unique choice we have A370588.
For binary indices instead of prime factors we have A370639.
A006530 gives greatest prime factor, least A020639.
A027746 lists prime factors, indices A112798, length A001222.
A355741 counts choices of a prime factor of each prime index.
A367902 counts choosable set-systems, ranks A367906, unlabeled A368095.
A367903 counts non-choosable set-systems, ranks A367907, unlabeled A368094.
A368098 counts choosable unlabeled multiset partitions, complement A368097.
A368100 ranks choosable multisets, complement A355529.
A368414 counts choosable factorizations, complement A368413.
A370592 counts choosable partitions, complement A370593.
Cf. A000040, A000720, A005117, A045778, A133686, A355739, A355744, A355745, A367771, A367905, A370636.

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

a(19)-a(41) from Alois P. Heinz, Feb 27 2024

cp's OEIS Frontend

A367912 Number of multisets that can be obtained by choosing a binary index of each binary index of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A370802 Positive integers with as many prime factors (A001222) as distinct divisors of prime indices (A370820).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A370584 Number of subsets of {1..n} such that only one set can be obtained by choosing a different prime factor of each element.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A367769 Number of finite sets of nonempty non-singleton subsets of {1..n} contradicting a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A370637 Number of subsets of {1..n} such that it is not possible to choose a different binary index of each element.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A370348 Numbers k such that there are fewer divisors of prime indices of k than there are prime indices of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A370803 Number of integer partitions of n such that more than one set can be obtained by choosing a different divisor of each part.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A367770 Number of sets of nonempty non-singleton subsets of {1..n} satisfying a strict version of the axiom of choice.

Views

Author

Keywords

Comments