A328187 -id:A328187 - 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 *)

A356606 Number of strict integer partitions of n where all parts have neighbors.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 1, 2, 1, 2, 3, 2, 2, 5, 2, 4, 5, 5, 4, 8, 5, 7, 9, 8, 8, 13, 10, 11, 16, 13, 15, 20, 18, 18, 27, 21, 26, 31, 30, 30, 43, 34, 42, 49, 48, 48, 65, 56, 65, 76, 74, 77, 97, 88, 98, 117, 111, 119, 143, 137, 146, 175, 165, 182, 208

Offset: 0

Gus Wiseman, Aug 24 2022

nonn

A part x has a neighbor if either x - 1 or x + 1 is a part.

			The a(n) partitions for n = 0, 1, 3, 9, 15, 18, 20, 24 (A = 10, B = 11):
  ()  .  (21)  (54)   (87)     (765)    (7643)   (987)
               (432)  (654)    (6543)   (8732)   (8754)
                      (54321)  (7632)   (9821)   (9843)
                               (8721)   (65432)  (A932)
                               (65421)           (BA21)
                                                 (87432)
                                                 (87621)
                                                 (765321)

Alois P. Heinz, Table of n, a(n) for n = 0..5000 (first 301 terms from John Tyler Rascoe)
John Tyler Rascoe, Python program

This is the strict case of A355393 and A355394.
The complement is counted by A356607, non-strict A356235 and A356236.
A000041 counts integer partitions, strict A000009.
A000837 counts relatively prime partitions, ranked by A289509.
A007690 counts partitions with no singletons, complement A183558.
Cf. A137921, A325160, A328171, A328172, A328187, A328220, A328221, A356237.

Table[Length[Select[IntegerPartitions[n], Function[ptn,UnsameQ@@ptn&&And@@Table[MemberQ[ptn,x-1]||MemberQ[ptn,x+1],{x,Union[ptn]}]]]],{n,0,30}]

Python
```
# see linked program
```

G.f.: 1 + Sum_{i>0} A(x,i), where A(x,i) = x^((2*i)+1) * G(x,i+1) for i > 0, is the g.f. for partitions of this kind with least part i, and G(x,k) = 1 + x^(k+1) * G(x,k+1) + Sum_{m>=0} x^(2*(k+m)+5) * G(x,m+k+3). - John Tyler Rascoe, Feb 16 2024

A356607 Number of strict integer partitions of n with at least one neighborless part.

Original entry on oeis.org

0, 1, 1, 1, 2, 2, 3, 4, 6, 6, 9, 11, 13, 17, 20, 24, 30, 36, 41, 52, 60, 71, 84, 100, 114, 137, 158, 183, 214, 248, 283, 330, 379, 432, 499, 570, 648, 742, 846, 955, 1092, 1234, 1395, 1580, 1786, 2005, 2270, 2548, 2861, 3216, 3610, 4032, 4526, 5055, 5642, 6304, 7031, 7820, 8720, 9694

Offset: 0

Gus Wiseman, Aug 26 2022

nonn

A part x is neighborless if neither x - 1 nor x + 1 are parts.

			The a(0) = 0 through a(9) = 6 partitions:
  .  (1)  (2)  (3)  (4)   (5)   (6)   (7)    (8)    (9)
                    (31)  (41)  (42)  (52)   (53)   (63)
                                (51)  (61)   (62)   (72)
                                      (421)  (71)   (81)
                                             (431)  (531)
                                             (521)  (621)

Alois P. Heinz, Table of n, a(n) for n = 0..5000 (first 101 terms from Lucas A. Brown)
Lucas A. Brown, A356607.py

This is the strict case of A356235 and A356236.
The complement is counted by A356606, non-strict A355393 and A355394.
A000041 counts integer partitions, strict A000009.
A000837 counts relatively prime partitions, ranked by A289509.
A007690 counts partitions with no singletons, complement A183558.
Cf. A073492, A137921, A325160, A328171, A328172, A328187, A328220, A328221.

Table[Length[Select[IntegerPartitions[n],Function[ptn,UnsameQ@@ptn&&Or@@Table[!MemberQ[ptn,x-1]&&!MemberQ[ptn,x+1],{x,Union[ptn]}]]]],{n,0,30}]

a(31)-a(59) from Lucas A. Brown, Sep 09 2022

A355394 Number of integer partitions of n such that, for all parts x, x - 1 or x + 1 is also a part.

Original entry on oeis.org

1, 0, 0, 1, 1, 3, 3, 6, 6, 10, 11, 16, 18, 25, 30, 38, 47, 59, 74, 90, 112, 136, 171, 203, 253, 299, 372, 438, 536, 631, 767, 900, 1085, 1271, 1521, 1774, 2112, 2463, 2910, 3389, 3977, 4627, 5408, 6276, 7304, 8459, 9808, 11338, 13099, 15112, 17404, 20044, 23018, 26450, 30299, 34746, 39711, 45452, 51832

Offset: 0

Gus Wiseman, Aug 26 2022

nonn

These are partitions without a neighborless part, where a part x is neighborless if neither x - 1 nor x + 1 are parts. The first counted partition that does not cover an interval is (5,4,2,1).

			The a(0) = 1 through a(9) = 11 partitions:
  ()  .  .  (21)  (211)  (32)    (321)    (43)      (332)      (54)
                         (221)   (2211)   (322)     (3221)     (432)
                         (2111)  (21111)  (2221)    (22211)    (3222)
                                          (3211)    (32111)    (3321)
                                          (22111)   (221111)   (22221)
                                          (211111)  (2111111)  (32211)
                                                               (222111)
                                                               (321111)
                                                               (2211111)
                                                               (21111111)

Lucas A. Brown, Table of n, a(n) for n = 0..100
Lucas A. Brown, A355394.py

The singleton case is A355393, complement A356235.
The complement is counted by A356236, ranked by A356734.
The strict case is A356606, complement A356607.
These partitions are ranked by A356736.
A000041 counts integer partitions, strict A000009.
A000837 counts relatively prime partitions, ranked by A289509.
A007690 counts partitions with no singletons, complement A183558.
Cf. A066312, A073491, A077855, A328171, A328172, A328187, A328221, A356233, A356237.

Table[Length[Select[IntegerPartitions[n],Function[ptn,!Or@@Table[!MemberQ[ptn,x-1]&&!MemberQ[ptn,x+1],{x,Union[ptn]}]]]],{n,0,30}]

a(n) = A000041(n) - A356236(n).

a(31)-a(59) from Lucas A. Brown, Sep 04 2022

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]&]

A355393 Number of integer partitions of n such that, for all parts x of multiplicity 1, either x - 1 or x + 1 is also a part.

Original entry on oeis.org

1, 0, 1, 2, 3, 4, 6, 7, 10, 14, 17, 23, 32, 39, 51, 67, 83, 105, 134, 165, 206, 256, 312, 385, 475, 573, 697, 849, 1021, 1231, 1483, 1771, 2121, 2534, 3007, 3575, 4245, 5008, 5914, 6979, 8198, 9626, 11292, 13201, 15430, 18010, 20960, 24389, 28346, 32855, 38066

Offset: 0

Gus Wiseman, Aug 26 2022

nonn

These are partitions without a neighborless singleton, where a part x is neighborless if neither x - 1 nor x + 1 are parts, and a singleton if it appears only once.

			The a(0) = 1 through a(8) = 10 partitions:
  ()  .  (11)  (21)   (22)    (32)     (33)      (43)       (44)
               (111)  (211)   (221)    (222)     (322)      (332)
                      (1111)  (2111)   (321)     (2221)     (2222)
                              (11111)  (2211)    (3211)     (3221)
                                       (21111)   (22111)    (3311)
                                       (111111)  (211111)   (22211)
                                                 (1111111)  (32111)
                                                            (221111)
                                                            (2111111)
                                                            (11111111)

This is the singleton case of A355394, complement A356236.
The complement is counted by A356235.
These partitions are ranked by the complement of A356237.
The strict case is A356606, complement A356607.
A000041 counts integer partitions, strict A000009.
A000837 counts relatively prime partitions, ranked by A289509.
A007690 counts partitions with no singletons, complement A183558.
Cf. A073491, A325160, A328171, A328172, A328187, A328220, A356233.

Table[Length[Select[IntegerPartitions[n],Function[ptn,!Or@@Table[Count[ptn,x]==1&&!MemberQ[ptn,x-1]&&!MemberQ[ptn,x+1],{x,Union[ptn]}]]]],{n,0,30}]

A356235 Number of integer partitions of n with a neighborless singleton.

Original entry on oeis.org

0, 1, 1, 1, 2, 3, 5, 8, 12, 16, 25, 33, 45, 62, 84, 109, 148, 192, 251, 325, 421, 536, 690, 870, 1100, 1385, 1739, 2161, 2697, 3334, 4121, 5071, 6228, 7609, 9303, 11308, 13732, 16629, 20101, 24206, 29140, 34957, 41882, 50060, 59745, 71124, 84598, 100365

Offset: 0

Gus Wiseman, Aug 23 2022

nonn

A part x is neighborless if neither x - 1 nor x + 1 are parts, and a singleton if it appears only once. Examples of partitions with a neighborless singleton are: (3), (3,1), (3,1,1), (3,3,1). Examples of partitions without a neighborless singleton are: (3,3,1,1), (4,3,1,1), (3,2,1), (2,1), (3,3).

			The a(1) = 1 through a(8) = 12 partitions:
  (1)  (2)  (3)  (4)   (5)    (6)     (7)      (8)
                 (31)  (41)   (42)    (52)     (53)
                       (311)  (51)    (61)     (62)
                              (411)   (331)    (71)
                              (3111)  (421)    (422)
                                      (511)    (431)
                                      (4111)   (521)
                                      (31111)  (611)
                                               (4211)
                                               (5111)
                                               (41111)
                                               (311111)

The complement is counted by A355393.
This is the singleton case of A356236, complement A355394.
These partitions are ranked by A356237.
The strict case is A356607, complement A356606.
A000041 counts integer partitions, strict A000009.
A000837 counts relatively prime partitions, ranked by A289509.
A007690 counts partitions with no singletons, complement A183558.
Cf. A066205, A325160, A328171, A328172, A328187, A328221, A356233.

Table[Length[Select[IntegerPartitions[n],Min@@Length/@Split[Reverse[#],#1>=#2-1&]==1&]],{n,0,30}]

A356236 Number of integer partitions of n with a neighborless part.

Original entry on oeis.org

0, 1, 2, 2, 4, 4, 8, 9, 16, 20, 31, 40, 59, 76, 105, 138, 184, 238, 311, 400, 515, 656, 831, 1052, 1322, 1659, 2064, 2572, 3182, 3934, 4837, 5942, 7264, 8872, 10789, 13109, 15865, 19174, 23105, 27796, 33361, 39956, 47766, 56985, 67871, 80675, 95750, 113416

Offset: 0

Gus Wiseman, Aug 24 2022

nonn

A part x of a partition is neighborless if neither x - 1 nor x + 1 are parts.

			The a(1) = 1 through a(8) = 9 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (111)  (22)    (41)     (33)      (52)
                    (31)    (311)    (42)      (61)
                    (1111)  (11111)  (51)      (331)
                                     (222)     (421)
                                     (411)     (511)
                                     (3111)    (4111)
                                     (111111)  (31111)
                                               (1111111)

The complement is counted by A355394, singleton case A355393.
The singleton case is A356235, ranked by A356237.
The strict case is A356607, complement A356606.
These partitions are ranked by the complement of A356736.
A000041 counts integer partitions, strict A000009.
A000837 counts relatively prime partitions, ranked by A289509.
A007690 counts partitions with no singletons, complement A183558.
Cf. A066205, A112798, A319630, A325160, A328171, A328172, A328187, A328221.

Table[Length[Select[IntegerPartitions[n],Function[ptn,Or@@Table[!MemberQ[ptn,x-1]&&!MemberQ[ptn,x+1],{x,Union[ptn]}]]]],{n,0,30}]

a(n) = A000041(n) - A355394(n).

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

A356606 Number of strict integer partitions of n where all parts have neighbors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A356607 Number of strict integer partitions of n with at least one neighborless part.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A355394 Number of integer partitions of n such that, for all parts x, x - 1 or x + 1 is also a part.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A328335 Numbers whose consecutive prime indices are relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A355393 Number of integer partitions of n such that, for all parts x of multiplicity 1, either x - 1 or x + 1 is also a part.

Views

Author