A328188 -id:A328188 - cp's OEIS frontend

A328171 Number of (necessarily strict) integer partitions of n with no two consecutive parts divisible.

1, 1, 1, 1, 1, 2, 1, 3, 2, 4, 4, 5, 4, 9, 9, 10, 12, 14, 16, 20, 23, 29, 34, 38, 41, 51, 60, 66, 78, 89, 103, 119, 137, 157, 180, 201, 229, 261, 298, 338, 379, 431, 486, 547, 618, 694, 783, 876, 986, 1103, 1241, 1387, 1551, 1728, 1932, 2148, 2395, 2664, 2963

Offset: 0

Gus Wiseman, Oct 11 2019

nonn

			The a(1) = 1 through a(15) = 10 partitions (A..F = 10..15):
  1  2  3  4  5   6  7   8   9    A    B   C    D    E     F
              32     43  53  54   64   65  75   76   86    87
                     52      72   73   74  543  85   95    96
                             432  532  83  732  94   A4    B4
                                       92       A3   B3    D2
                                                B2   653   654
                                                643  743   753
                                                652  752   852
                                                832  5432  A32
                                                           6432

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

The complement is counted by A328221.
The Heinz numbers of these partitions are A328603.
Partitions whose pairs of consecutive parts are relatively prime are A328172, with strict case A328188.
Partitions with no pair of consecutive parts relatively prime are A328187, with strict case A328220.
Numbers without consecutive divisible proper divisors are A328028.
Cf. A000837, A018783, A328026, A328161, A328189, A328194, A328195.

Table[Length[Select[IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;Divisible[x,y]]&]],{n,0,30}]

A178470 Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 5, 1, 8, 4, 17, 3, 38, 5, 67, 25, 132, 27, 290, 54, 547, 163, 1086, 255, 2277, 530, 4416, 1267, 8850, 2314, 18151, 4737, 35799, 10499, 71776, 20501, 145471, 41934, 289695, 89030, 581117, 178424, 1171545, 365619, 2342563, 761051, 4699711

Offset: 0

Franklin T. Adams-Watters, May 28 2010

nonn

A178472(n) is a lower bound for a(n). This bound is exact for n = 2..10 and 12, but falls behind thereafter.

a(0) = 1 vacuously for the empty composition. One could take a(1) = 0, on the theory that each composition is followed by infinitely many 0's, and thus the 1 is not relatively prime to its neighbor; but this definition seems simpler.

			The three compositions for 11 are <11>, <2,6,3> and <3,6,2>.
From _Gus Wiseman_, Nov 19 2019: (Start)
The a(1) = 1 through a(11) = 3 compositions (A = 10, B = 11):
  1  2  3  4   5  6    7  8     9    A      B
           22     24      26    36   28     263
                  33      44    63   46     362
                  42      62    333  55
                  222     224        64
                          242        82
                          422        226
                          2222       244
                                     262
                                     424
                                     442
                                     622
                                     2224
                                     2242
                                     2422
                                     4222
                                     22222
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000

The case of partitions is A328187, with Heinz numbers A328336.
Partitions with all pairs of consecutive parts relatively prime are A328172.
Compositions without consecutive divisible parts are A328460 (one way) or A328508 (both ways).
Cf. A000837, A003242, A018783, A167606, A178471, A178472, A328171, A328188, A328220.

b:= proc(n, h) option remember; `if`(n=0, 1,
      add(`if`(h=1 or igcd(j, h)>1, b(n-j, j), 0), j=2..n))
    end:
a:= n-> `if`(n=1, 1, b(n, 1)):
seq(a(n), n=0..60);  # Alois P. Heinz, Oct 23 2011

b[n_, h_] := b[n, h] = If[n == 0, 1, Sum [If[h == 1 || GCD[j, h] > 1, b[n - j, j], 0], {j, 2, n}]]; a[n_] := If[n == 1, 1, b[n, 1]]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Oct 29 2015, after Alois P. Heinz *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]==1]&]],{n,0,20}] (* Gus Wiseman, Nov 19 2019 *)

am(n)=local(r);r=matrix(n,n,i,j,i==j);for(i=2,n,for(j=1,i-1,for(k=1,j,if(gcd(i-j,k)>1,r[i,i-j]+=r[j,k]))));r
al(n)=local(m);m=am(n);vector(n,i,sum(j=1,i,m[i,j]))

A328172 Number of integer partitions of n with all pairs of consecutive parts relatively prime.

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 7, 10, 12, 16, 19, 24, 28, 36, 43, 51, 62, 74, 87, 104, 122, 143, 169, 195, 227, 260, 302, 346, 397, 455, 521, 599, 686, 780, 889, 1001, 1138, 1286, 1454, 1638, 1846, 2076, 2330, 2614, 2929, 3280, 3666, 4093, 4565, 5085, 5667, 6300, 7002

Offset: 0

Gus Wiseman, Oct 12 2019

nonn

Except for any number of 1's, these partitions must be strict. The fully strict case is A328188.

Partitions with no consecutive pair of parts relatively prime are A328187, with strict case A328220.

			The a(1) = 1 through a(8) = 12 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (31)    (32)     (51)      (43)       (53)
             (111)  (211)   (41)     (321)     (52)       (71)
                    (1111)  (311)    (411)     (61)       (431)
                            (2111)   (3111)    (511)      (521)
                            (11111)  (21111)   (3211)     (611)
                                     (111111)  (4111)     (5111)
                                               (31111)    (32111)
                                               (211111)   (41111)
                                               (1111111)  (311111)
                                                          (2111111)
                                                          (11111111)

Alois P. Heinz, Table of n, a(n) for n = 0..1000

The case of compositions is A167606.
The strict case is A328188.
The Heinz numbers of these partitions are given by A328335.
Cf. A000837, A018783, A178470, A328028, A328170, A328171, A328187, A328188 A328220.

b:= proc(n, i, s) option remember; `if`(n=0 or i=1, 1,
      `if`(andmap(j-> igcd(i, j)=1, s), b(n-i, min(n-i, i-1),
           numtheory[factorset](i)), 0)+b(n, i-1, s))
    end:
a:= n-> b(n$2, {}):
seq(a(n), n=0..60);  # Alois P. Heinz, Oct 13 2019

Table[Length[Select[IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]>1]&]],{n,0,30}]
(* Second program: *)
b[n_, i_, s_] := b[n, i, s] = If[n == 0 || i == 1, 1,
     If[AllTrue[s, GCD[i, #] == 1&], b[n - i, Min[n - i, i - 1],
     FactorInteger[i][[All, 1]]], 0] + b[n, i - 1, s]];
a[n_] := b[n, n, {}];
a /@ Range[0, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

A328187 Number of integer partitions of n with no pair of consecutive parts relatively prime.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 14, 1, 16, 9, 22, 3, 38, 4, 46, 19, 58, 9, 94, 18, 106, 41, 144, 28, 221, 37, 246, 92, 318, 87, 465, 95, 530, 198, 693, 169, 963, 220, 1108, 424, 1383, 381, 1899, 492, 2216, 815, 2732, 799, 3644, 1041, 4231, 1585, 5194, 1608

Offset: 0

Gus Wiseman, Oct 12 2019

nonn

			The a(1) = 1 through a(15) = 9 partitions (A..F = 10..15):
  1  2  3  4   5  6    7  8     9    A      B  C       D  E        F
           22     33      44    63   55        66         77       96
                  42      62    333  64        84         86       A5
                  222     422        82        93         A4       C3
                          2222       442       A2         C2       555
                                     622       444        644      663
                                     4222      633        662      933
                                     22222     642        842      6333
                                               822        A22      33333
                                               3333       4442
                                               4422       6422
                                               6222       8222
                                               42222      44222
                                               222222     62222
                                                          422222
                                                          2222222

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

The Heinz numbers of these partitions are given by A328336.
The case of compositions is A178470.
The strict case is A328220.
Partitions with all pairs of consecutive parts relatively prime are A328172.
Cf. A000837, A018783, A328028, A328170, A328171, A328188.

Table[Length[Select[IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]==1]&]],{n,0,30}]

A328335 Numbers whose consecutive prime indices are relatively prime.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 23, 24, 26, 28, 29, 30, 31, 32, 33, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 48, 51, 52, 53, 55, 56, 58, 59, 60, 61, 62, 64, 66, 67, 68, 69, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86, 88

Offset: 1

Gus Wiseman, Oct 14 2019

nonn

First differs from A302569 in having 105, which has prime indices {2, 3, 4}.
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 Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), so these are Heinz numbers of partitions whose consecutive parts are relatively prime (A328172).

			The sequence of terms together with their prime indices begins:
   1: {}
   2: {1}
   3: {2}
   4: {1,1}
   5: {3}
   6: {1,2}
   7: {4}
   8: {1,1,1}
  10: {1,3}
  11: {5}
  12: {1,1,2}
  13: {6}
  14: {1,4}
  15: {2,3}
  16: {1,1,1,1}
  17: {7}
  19: {8}
  20: {1,1,3}
  22: {1,5}
  23: {9}

A superset of A302569.
Numbers whose prime indices are relatively prime are A289509.
Numbers with no consecutive prime indices relatively prime are A328336.
Cf. A000837, A056239, A112798, A281116, A289508, A318981, A328168, A328169, A328172, A328187, A328188, A328220.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],!MatchQ[primeMS[#],{_,x_,y_,_}/;GCD[x,y]>1]&]

A328220 Number of strict integer partitions of n with no pair of consecutive parts relatively prime.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 3, 1, 5, 1, 5, 4, 6, 3, 10, 3, 11, 7, 12, 3, 19, 5, 18, 12, 23, 9, 36, 11, 33, 21, 40, 20, 58, 19, 58, 35, 70, 31, 98, 36, 101, 65, 112, 56, 155, 64, 164, 97, 188, 88, 250, 112, 256, 157, 293, 145, 392, 163, 399, 241, 461, 242

Offset: 0

Gus Wiseman, Oct 14 2019

nonn

			The a(2) = 1 through a(20) = 11 partitions (A..K = 10..20):
  2  3  4  5  6   7  8   9   A   B  C    D  E    F   G    H    I    J    K
              42     62  63  64     84      86   96  A6   863  A8   964  C8
                             82     93      A4   A5  C4   962  C6   A63  E6
                                    A2      C2   C3  E2        E4        F5
                                    642     842      862       F3        G4
                                                     A42       G2        I2
                                                               864       A64
                                                               963       A82
                                                               A62       C62
                                                               C42       E42
                                                                         8642

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

The non-strict case is A328187.
Partitions with all consecutive parts relatively prime are A328172, with strict case A328188.
Strict partitions with relatively prime parts are A078374.
Partitions with no consecutive divisibilities are A328171.
Cf. A000837, A018783, A070211, A289509, A318980, A325545, A328170, A328221, A328335, A328336.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]==1]&]],{n,0,30}]

A328336 Numbers with no consecutive prime indices relatively prime.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 11, 13, 17, 19, 21, 23, 25, 27, 29, 31, 37, 39, 41, 43, 47, 49, 53, 57, 59, 61, 63, 65, 67, 71, 73, 79, 81, 83, 87, 89, 91, 97, 101, 103, 107, 109, 111, 113, 115, 117, 121, 125, 127, 129, 131, 133, 137, 139, 147, 149, 151, 157, 159, 163, 167

Offset: 1

Gus Wiseman, Oct 14 2019

nonn

First differs from A318978 in having 897, with prime indices {2, 6, 9}.
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 Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), so these are Heinz numbers of partitions no consecutive parts relatively prime (A328187).
Besides the initial 1 this differs from A305078: 47541=897*prime(16) is in A305078 but not in this set. - Andrey Zabolotskiy, Nov 13 2019

			The sequence of terms together with their prime indices begins:
   1: {}
   2: {1}
   3: {2}
   5: {3}
   7: {4}
   9: {2,2}
  11: {5}
  13: {6}
  17: {7}
  19: {8}
  21: {2,4}
  23: {9}
  25: {3,3}
  27: {2,2,2}
  29: {10}
  31: {11}
  37: {12}
  39: {2,6}
  41: {13}
  43: {14}

Numbers with consecutive prime indices relatively prime are A328335.
Strict partitions with no consecutive parts relatively prime are A328220.
Numbers with relatively prime prime indices are A289509.
Cf. A000837, A056239, A078374, A112798, A281116, A289508, A318981, A328168, A328169, A328172, A328187, A328188.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],!MatchQ[primeMS[#],{_,x_,y_,_}/;GCD[x,y]==1]&]

A328221 Number of integer partitions of n with at least one pair of consecutive divisible parts.

Original entry on oeis.org

0, 0, 1, 2, 4, 5, 10, 12, 20, 26, 38, 51, 73, 92, 126, 166, 219, 283, 369, 470, 604, 763, 968, 1217, 1534, 1907, 2376, 2944, 3640, 4476, 5501, 6723, 8212, 9986, 12130, 14682, 17748, 21376, 25717, 30847, 36959, 44152, 52688, 62714, 74557, 88440, 104775, 123878

Offset: 0

Gus Wiseman, Oct 15 2019

nonn

Includes all non-strict partitions.

			The a(2) = 1 through a(8) = 20 partitions:
  (11)  (21)   (22)    (41)     (33)      (61)       (44)
        (111)  (31)    (221)    (42)      (322)      (62)
               (211)   (311)    (51)      (331)      (71)
               (1111)  (2111)   (222)     (421)      (332)
                       (11111)  (321)     (511)      (422)
                                (411)     (2221)     (431)
                                (2211)    (3211)     (521)
                                (3111)    (4111)     (611)
                                (21111)   (22111)    (2222)
                                (111111)  (31111)    (3221)
                                          (211111)   (3311)
                                          (1111111)  (4211)
                                                     (5111)
                                                     (22211)
                                                     (32111)
                                                     (41111)
                                                     (221111)
                                                     (311111)
                                                     (2111111)
                                                     (11111111)

The complement is counted by A328171.
Partitions whose consecutive parts are relatively prime are A328172.
Partitions with no pair of consecutive parts relatively prime are A328187.
Numbers without consecutive divisible proper divisors are A328028.
Cf. A000837, A018783, A328026, A328161, A328188, A328189, A328194, A328220.

Table[Length[Select[IntegerPartitions[n],MatchQ[#,{_,x_,y_,_}/;Divisible[x,y]]&]],{n,0,30}]

A328602 Number of necklace compositions of n where no pair of circularly adjacent parts is relatively prime.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 16, 1, 20, 9, 35, 2, 69, 3, 111, 24, 190, 13, 384, 31, 646, 102, 1212, 113, 2348, 227, 4254, 613, 7993, 976, 15459, 1915, 28825, 4357, 54988, 7868, 105826, 15760, 201115, 33376, 385590, 63974, 744446, 128224, 1428047, 262914, 2754037

Offset: 1

Gus Wiseman, Oct 25 2019

nonn

A necklace composition of n (A008965) is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.

Circularity means the last part is followed by the first.

			The a(2) = 1 through a(10) = 8 necklace compositions:
  (2)  (3)  (4)    (5)  (6)      (7)  (8)        (9)      (10)
            (2,2)       (2,4)         (2,6)      (3,6)    (2,8)
                        (3,3)         (4,4)      (3,3,3)  (4,6)
                        (2,2,2)       (2,2,4)             (5,5)
                                      (2,2,2,2)           (2,2,6)
                                                          (2,4,4)
                                                          (2,2,2,4)
                                                          (2,2,2,2,2)
The a(19) = 3 necklace compositions are: (19), (3,6,4,6), (2,2,6,3,6).

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

The non-necklace, non-circular version is A178470.
The version for indivisibility (rather than co-primality) is A328600.
The circularly coprime (as opposed to anti-coprime) version is A328597.
Partitions with no consecutive parts relatively prime are A328187.
Cf. A000031, A000740, A008965, A032153, A318728, A318729, A318748, A328172, A328188, A328220, A328335, A328336, A328601, A328609.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&And@@Not/@CoprimeQ@@@Partition[#,2,1,1]&]],{n,10}]

b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q,]}
seq(n)={my(v=sum(k=1, n, k*b(n, k, (i,j)->gcd(i,j)<>1))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 26 2019

Terms a(26) and beyond from Andrew Howroyd, Oct 26 2019

cp's OEIS Frontend

A328171 Number of (necessarily strict) integer partitions of n with no two consecutive parts divisible.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A178470 Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A328172 Number of integer partitions of n with all pairs of consecutive parts relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A328187 Number of integer partitions of n with no pair of consecutive parts relatively prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A328335 Numbers whose consecutive prime indices are relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A328220 Number of strict integer partitions of n with no pair of consecutive parts relatively prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A328336 Numbers with no consecutive prime indices relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A328221 Number of integer partitions of n with at least one pair of consecutive divisible parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A328602 Number of necklace compositions of n where no pair of circularly adjacent parts is relatively prime.

Views