A051424 -id:A051424 - cp's OEIS frontend

A355737 Number of ways to choose a sequence of divisors, one of each prime index of n (with multiplicity), such that the result has no common divisor > 1.

0, 1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 2, 1, 3, 4, 1, 1, 4, 1, 2, 4, 2, 1, 2, 3, 4, 7, 3, 1, 4, 1, 1, 4, 2, 6, 4, 1, 4, 6, 2, 1, 6, 1, 2, 8, 3, 1, 2, 5, 4, 4, 4, 1, 8, 4, 3, 5, 4, 1, 4, 1, 2, 10, 1, 6, 4, 1, 2, 6, 6, 1, 4, 1, 6, 8, 4, 6, 8, 1, 2, 15, 2, 1, 6, 4, 4

Offset: 1

Gus Wiseman, Jul 17 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(2) = 1 through a(18) = 4 choices:
  1  1  11  1  11  1  111  11  11  1  111  1  11  11  1111  1  111
               12          12  13     112     12  13           112
                           21                 14  21           121
                                                  23           122

Wikipedia, Coprime integers.

Dominated by A355731, firsts A355732, primes A355741, prime-powers A355742.
For weakly increasing instead of coprime we have A355735, primes A355745.
Positions of first appearances are A355738.
For strict instead of coprime we have A355739, zeros A355740.
A000005 counts divisors.
A001221 counts distinct prime factors, with sum A001414.
A001222 counts prime factors with multiplicity.
A003963 multiplies together the prime indices of n.
A056239 adds up prime indices, row sums of A112798.
A120383 lists numbers divisible by all of their prime indices.
A289508 gives GCD of prime indices.
A289509 ranks relatively prime partitions, odd A302697, squarefree A302796.
A324850 lists numbers divisible by the product of their prime indices.
Cf. A000720, A007359, A051424, A076610, A289507, A296150, A302696, A302698, A355733, A355744, A355748.

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

A337462 Number of pairwise coprime compositions of n, where a singleton is not considered coprime unless it is (1).

Original entry on oeis.org

1, 1, 1, 3, 6, 12, 21, 37, 62, 100, 159, 253, 402, 634, 983, 1491, 2224, 3280, 4813, 7043, 10270, 14888, 21415, 30585, 43400, 61204, 85747, 119295, 164834, 226422, 309663, 422301, 574826, 781236, 1060181, 1436367, 1942588, 2622078, 3531151, 4742315, 6348410

Offset: 0

Gus Wiseman, Sep 18 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

			The a(1) = 1 through a(5) = 12 compositions:
  (1)  (1,1)  (1,2)    (1,3)      (1,4)
              (2,1)    (3,1)      (2,3)
              (1,1,1)  (1,1,2)    (3,2)
                       (1,2,1)    (4,1)
                       (2,1,1)    (1,1,3)
                       (1,1,1,1)  (1,3,1)
                                  (3,1,1)
                                  (1,1,1,2)
                                  (1,1,2,1)
                                  (1,2,1,1)
                                  (2,1,1,1)
                                  (1,1,1,1,1)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..500

A000740 counts the relatively prime instead of pairwise coprime version.
A101268 considers all singletons to be coprime, with strict case A337562.
A327516 is the unordered version.
A333227 ranks these compositions, with complement A335239.
A337461 counts these compositions of length 3.
A337561 is the strict case.
A051424 counts pairwise coprime or singleton partitions.
A101268 counts pairwise coprime or singleton compositions.
A178472 counts compositions with a common factor.
A305713 counts strict pairwise coprime partitions.
A328673 counts pairwise non-coprime partitions.
A333228 ranks compositions whose distinct parts are pairwise coprime.
A337667 counts pairwise non-coprime compositions.
Cf. A001523, A007360, A087087, A220377, A302569, A307719, A326675, A335235, A335238, A337664.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],#=={}||CoprimeQ@@#&]],{n,0,10}]

For n > 1, a(n) = A101268(n) - 1.

A335235 Numbers k such that the k-th composition in standard order (A066099) is pairwise coprime, where a singleton is always considered coprime.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33, 35, 37, 38, 39, 41, 44, 47, 48, 49, 50, 51, 52, 55, 56, 57, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 71, 72, 75, 77, 78, 79, 80, 83, 89, 92, 95, 96, 97

Offset: 1

Gus Wiseman, May 28 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence together with the corresponding compositions begins:
   1: (1)          20: (2,3)          48: (1,5)
   2: (2)          23: (2,1,1,1)      49: (1,4,1)
   3: (1,1)        24: (1,4)          50: (1,3,2)
   4: (3)          25: (1,3,1)        51: (1,3,1,1)
   5: (2,1)        27: (1,2,1,1)      52: (1,2,3)
   6: (1,2)        28: (1,1,3)        55: (1,2,1,1,1)
   7: (1,1,1)      29: (1,1,2,1)      56: (1,1,4)
   8: (4)          30: (1,1,1,2)      57: (1,1,3,1)
   9: (3,1)        31: (1,1,1,1,1)    59: (1,1,2,1,1)
  11: (2,1,1)      32: (6)            60: (1,1,1,3)
  12: (1,3)        33: (5,1)          61: (1,1,1,2,1)
  13: (1,2,1)      35: (4,1,1)        62: (1,1,1,1,2)
  14: (1,1,2)      37: (3,2,1)        63: (1,1,1,1,1,1)
  15: (1,1,1,1)    38: (3,1,2)        64: (7)
  16: (5)          39: (3,1,1,1)      65: (6,1)
  17: (4,1)        41: (2,3,1)        66: (5,2)
  18: (3,2)        44: (2,1,3)        67: (5,1,1)
  19: (3,1,1)      47: (2,1,1,1,1)    68: (4,3)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

The version counting partitions is A051424, with strict case A007360.
The version for binary indices is A087087.
The version counting compositions is A101268.
The version for prime indices is A302569.
The case without singletons is A333227.
The complement is A335236.
Numbers whose binary indices are pairwise coprime are A326675.
Coprime partitions are counted by A327516.
All of the following pertain to compositions in standard order:
- Length is A000120.
- The parts are row k of A066099.
- Sum is A070939.
- Product is A124758.
- Reverse is A228351
- GCD is A326674.
- Heinz number is A333219.
- LCM is A333226.
Cf. A048793, A272919, A291166, A302569, A335236, A335237, A335238, A335239, A335240.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],Length[stc[#]]==1||CoprimeQ@@stc[#]&]

A302797 Squarefree numbers whose prime indices are pairwise coprime. Heinz numbers of strict integer partitions with pairwise coprime parts.

Original entry on oeis.org

1, 2, 6, 10, 14, 15, 22, 26, 30, 33, 34, 35, 38, 46, 51, 55, 58, 62, 66, 69, 70, 74, 77, 82, 85, 86, 93, 94, 95, 102, 106, 110, 118, 119, 122, 123, 134, 138, 141, 142, 143, 145, 146, 154, 155, 158, 161, 165, 166, 170, 177, 178, 186, 187, 190, 194, 201, 202

Offset: 1

Gus Wiseman, Apr 13 2018

nonn

A prime index of n is a number m such that prime(m) divides n. Two or more numbers are coprime if no pair of them has a common divisor other than 1. A single number is not considered coprime unless it is equal to 1.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			Sequence of terms together with their sets of prime indices begins:
01 : {}
02 : {1}
06 : {1,2}
10 : {1,3}
14 : {1,4}
15 : {2,3}
22 : {1,5}
26 : {1,6}
30 : {1,2,3}
33 : {2,5}
34 : {1,7}
35 : {3,4}
38 : {1,8}
46 : {1,9}
51 : {2,7}
55 : {3,5}
58 : {1,10}
62 : {1,11}
66 : {1,2,5}
69 : {2,9}
70 : {1,3,4}

Cf. A001222, A003963, A005117, A007359, A051424, A056239, A275024, A289509, A302242, A302505, A302696, A302697, A302698, A302796, A302798.

Select[Range[100],Or[#===1,SquareFreeQ[#]&&CoprimeQ@@PrimePi/@FactorInteger[#][[All,1]]]&]

A337605 Number of unordered triples of distinct positive integers summing to n, any two of which have a common divisor > 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 0, 4, 0, 4, 1, 5, 0, 9, 0, 8, 3, 10, 0, 17, 1, 14, 5, 16, 1, 25, 1, 21, 8, 26, 2, 37, 1, 30, 15, 33, 2, 49, 2, 44, 16, 44, 2, 64, 6, 54, 21, 56, 3, 87, 5, 65, 30, 70, 9, 101, 5, 80, 34, 98, 6, 121, 6, 96, 52

Offset: 0

Gus Wiseman, Sep 20 2020

nonn

			The a(n) triples for n = 12, 16, 18, 22, 27, 55:
  (6,4,2)  (8,6,2)   (8,6,4)   (10,8,4)  (12,9,6)  (28,21,6)
           (10,4,2)  (9,6,3)   (12,6,4)  (15,9,3)  (30,20,5)
                     (10,6,2)  (12,8,2)  (18,6,3)  (35,15,5)
                     (12,4,2)  (14,6,2)            (40,10,5)
                               (16,4,2)            (25,20,10)
                                                   (30,15,10)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..10000

A014612 intersected with A318719 ranks these partitions.
A220377 is the coprime instead of non-coprime version.
A318717 counts these partitions of any length, ranked by A318719.
A337599 is the non-strict version.
A337604 is the ordered non-strict version.
A337605*6 is the ordered version.
A023023 counts relatively prime 3-part partitions
A051424 counts pairwise coprime or singleton partitions.
A200976 and A328673 count pairwise non-coprime partitions.
A307719 counts pairwise coprime 3-part partitions.
A327516 counts pairwise coprime partitions, with strict case A305713.
Cf. A000217, A001399, A014612, A082024, A178472, A220377, A284825, A337461, A337561, A337667.

stabQ[u_,Q_]:=Array[#1==#2||!Q[u[[#1]],u[[#2]]]&,{Length[u],Length[u]},1,And];
Table[Length[Select[IntegerPartitions[n,{3}],UnsameQ@@#&&stabQ[#,CoprimeQ]&]],{n,0,100}]

A304709 Number of integer partitions of n whose distinct parts are pairwise coprime.

Original entry on oeis.org

1, 1, 2, 3, 6, 7, 13, 16, 23, 29, 42, 49, 69, 83, 102, 126, 161, 191, 239, 281, 336, 402, 484, 566, 672, 787, 919, 1067, 1251, 1449, 1684, 1934, 2223, 2554, 2920, 3341, 3821, 4344, 4928, 5586, 6334, 7163, 8091, 9100, 10228, 11492, 12902, 14449, 16167, 18058

Offset: 1

Gus Wiseman, May 17 2018

nonn

Two parts are coprime if they have no common divisor greater than 1. For partitions of length 1 note that (1) is coprime but (x) is not coprime for x > 1.

			The a(6) = 7 integer partitions of 6 whose distinct parts are pairwise coprime are (51), (411), (321), (3111), (2211), (21111), (111111).

Andrew Howroyd, Table of n, a(n) for n = 1..500

Cf. A000005, A007359, A007360, A018783, A051424, A078374, A101268, A289508, A289509, A302569, A302696, A302698, A302796, A302797, A304711, A304712.

Table[Select[IntegerPartitions[n],CoprimeQ@@Union[#]&]//Length,{n,20}]

lista(nn)={local(Cache=Map());
  my(excl=vector(nn, n, sum(i=1, n-1, if(gcd(i,n)>1, 2^(n-i)))));
  my(c(n, m, b)=
     if(n==0, 1,
        while(m>n || bittest(b,0), m--; b>>=1);
        my(hk=[n, m, b], z);
        if(!mapisdefined(Cache, hk, &z),
          z = if(m, self()(n, m-1, b>>1) + self()(n-m, m, bitor(b, excl[m])), 0);
          mapput(Cache, hk, z)); z));
  my(a(n)=c(n, n, 0) + 1 - numdiv(n));
  for(n=1, nn, print1(a(n), ", "))
} \\ Andrew Howroyd, Nov 02 2019

a(n) = A304712(n) + 1 - A000005(n). - Andrew Howroyd, Nov 02 2019

A337604 Number of ordered triples of positive integers summing to n, any two of which have a common divisor > 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 0, 3, 1, 6, 0, 13, 0, 15, 7, 21, 0, 37, 0, 39, 16, 45, 0, 73, 6, 66, 28, 81, 0, 130, 6, 105, 46, 120, 21, 181, 6, 153, 67, 189, 12, 262, 6, 213, 118, 231, 12, 337, 21, 306, 121, 303, 12, 433, 57, 369, 154, 378, 18, 583, 30, 435, 217, 465

Offset: 0

Gus Wiseman, Sep 20 2020

nonn

The first relatively prime triple (15,10,6) is counted under a(31).

			The a(6) = 1 through a(15) = 7 triples (empty columns indicated by dots, A = 10):
  222  .  224  333  226  .  228  .  22A  339
          242       244     246     248  366
          422       262     264     266  393
                    424     282     284  555
                    442     336     2A2  636
                    622     363     428  663
                            426     446  933
                            444     464
                            462     482
                            624     626
                            633     644
                            642     662
                            822     824
                                    842
                                    A22

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..10000

A014311 intersected with A337666 ranks these compositions.
A337667 counts these compositions of any length.
A335402 lists the positions of zeros.
A337461 is the coprime instead of non-coprime version.
A337599 is the unordered version, with strict case A337605.
A337605*6 is the strict version.
A000741 counts relatively prime 3-part compositions.
A101268 counts pairwise coprime or singleton compositions.
A200976 and A328673 count pairwise non-relatively prime partitions.
A307719 counts pairwise coprime 3-part partitions.
A318717 counts pairwise non-coprime strict partitions.
A333227 ranks pairwise coprime compositions.
Cf. A000217, A001399, A014612, A051424, A082024, A178472, A220377, A284825, A305713, A327516, A333228, A337561.

stabQ[u_,Q_]:=Array[#1==#2||!Q[u[[#1]],u[[#2]]]&,{Length[u],Length[u]},1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{3}],stabQ[#,CoprimeQ]&]],{n,0,100}]

A302697 Odd numbers whose prime indices are relatively prime. Heinz numbers of integer partitions with no 1's and with relatively prime parts.

Original entry on oeis.org

15, 33, 35, 45, 51, 55, 69, 75, 77, 85, 93, 95, 99, 105, 119, 123, 135, 141, 143, 145, 153, 155, 161, 165, 175, 177, 187, 195, 201, 205, 207, 209, 215, 217, 219, 221, 225, 231, 245, 249, 253, 255, 265, 275, 279, 285, 287, 291, 295, 297, 309, 315, 323, 327, 329

Offset: 1

Gus Wiseman, Apr 11 2018

nonn

A prime index of n is a number m such that prime(m) divides n.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			Sequence of integer partitions with no 1's and with relatively prime parts begins:
015: (3,2)
033: (5,2)
035: (4,3)
045: (3,2,2)
051: (7,2)
055: (5,3)
069: (9,2)
075: (3,3,2)
077: (5,4)
085: (7,3)
093: (11,2)
095: (8,3)
099: (5,2,2)
105: (4,3,2)
119: (7,4)
123: (13,2)
135: (3,2,2,2)

Cf. A000837, A000961, A001222, A005117, A007359, A051424, A076078, A101268, A275024, A285572, A289509, A298748, A302568, A302569, A302696, A302698.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1,200,2],GCD@@primeMS[#]===1&]

A324753 Number of integer partitions of n containing all prime indices of their parts.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 5, 7, 8, 14, 16, 23, 29, 40, 49, 66, 81, 109, 133, 172, 211, 274, 332, 419, 511, 640, 775, 965, 1165, 1434, 1730, 2109, 2530, 3083, 3683, 4447, 5308, 6375, 7573, 9062, 10730, 12786, 15104, 17909, 21095, 24937, 29284, 34488, 40421, 47450

Offset: 0

Gus Wiseman, Mar 16 2019

nonn

These could be described as transitive integer partitions.

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(1) = 1 through a(8) = 8 integer partitions:
  (1)  (11)  (21)   (211)   (41)     (321)     (421)      (3221)
             (111)  (1111)  (221)    (411)     (2221)     (4211)
                            (2111)   (2211)    (3211)     (22211)
                            (11111)  (21111)   (4111)     (32111)
                                     (111111)  (22111)    (41111)
                                               (211111)   (221111)
                                               (1111111)  (2111111)
                                                          (11111111)

The subset version is A324736. The strict case is A324748. The Heinz number version is A290822. An infinite version is A324698.
Cf. A000720, A000837, A001462, A007097, A051424, A112798, A276625, A279861, A290689, A290760.
Cf. A324697, A324737.

Table[Length[Select[IntegerPartitions[n],SubsetQ[#,PrimePi/@First/@Join@@FactorInteger/@DeleteCases[#,1]]&]],{n,0,30}]

A335238 Numbers k such that the distinct parts of the k-th composition in standard order (A066099) are not pairwise coprime, where a singleton is not coprime unless it is (1).

Original entry on oeis.org

0, 2, 4, 8, 10, 16, 32, 34, 36, 40, 42, 64, 69, 70, 81, 88, 98, 104, 128, 130, 136, 138, 139, 141, 142, 160, 162, 163, 168, 170, 177, 184, 197, 198, 209, 216, 226, 232, 256, 260, 261, 262, 274, 276, 277, 278, 279, 282, 283, 285, 286, 288, 290, 292, 296, 321

Offset: 1

Gus Wiseman, May 28 2020

nonn

We use the Mathematica definition for CoprimeQ, so a singleton is not considered coprime unless it is (1).

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence together with the corresponding compositions begins:
    0: ()          88: (2,1,4)      177: (2,1,4,1)
    2: (2)         98: (1,4,2)      184: (2,1,1,4)
    4: (3)        104: (1,2,4)      197: (1,4,2,1)
    8: (4)        128: (8)          198: (1,4,1,2)
   10: (2,2)      130: (6,2)        209: (1,2,4,1)
   16: (5)        136: (4,4)        216: (1,2,1,4)
   32: (6)        138: (4,2,2)      226: (1,1,4,2)
   34: (4,2)      139: (4,2,1,1)    232: (1,1,2,4)
   36: (3,3)      141: (4,1,2,1)    256: (9)
   40: (2,4)      142: (4,1,1,2)    260: (6,3)
   42: (2,2,2)    160: (2,6)        261: (6,2,1)
   64: (7)        162: (2,4,2)      262: (6,1,2)
   69: (4,2,1)    163: (2,4,1,1)    274: (4,3,2)
   70: (4,1,2)    168: (2,2,4)      276: (4,2,3)
   81: (2,4,1)    170: (2,2,2,2)    277: (4,2,2,1)

The complement is A333228.
Not ignoring repeated parts gives A335239.
Singleton or pairwise coprime partitions are counted by A051424.
Singleton or pairwise coprime sets are ranked by A087087.
Coprime partitions are counted by A327516.
Non-coprime partitions are counted by A335240.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Product is A124758.
- Reverse is A228351
- GCD is A326674.
- Heinz number is A333219.
- LCM is A333226.
- Coprime compositions are A333227.
- Compositions whose distinct parts are coprime are A333228.
- Number of distinct parts is A334028.
Cf. A007360, A048793, A101268, A291166, A302569, A326675, A335235, A335236, A335237.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],!CoprimeQ@@Union[stc[#]]&]

cp's OEIS Frontend

A355737 Number of ways to choose a sequence of divisors, one of each prime index of n (with multiplicity), such that the result has no common divisor > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A337462 Number of pairwise coprime compositions of n, where a singleton is not considered coprime unless it is (1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A335235 Numbers k such that the k-th composition in standard order (A066099) is pairwise coprime, where a singleton is always considered coprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A302797 Squarefree numbers whose prime indices are pairwise coprime. Heinz numbers of strict integer partitions with pairwise coprime parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A337605 Number of unordered triples of distinct positive integers summing to n, any two of which have a common divisor > 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A304709 Number of integer partitions of n whose distinct parts are pairwise coprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A337604 Number of ordered triples of positive integers summing to n, any two of which have a common divisor > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A302697 Odd numbers whose prime indices are relatively prime. Heinz numbers of integer partitions with no 1's and with relatively prime parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs