A328171 -id:A328171 - cp's OEIS frontend

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

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

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

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

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).

A087086 Primitive sets of integers, each subset mapped onto a unique binary integer, values here shown in decimal.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 12, 16, 18, 20, 22, 24, 28, 32, 40, 48, 56, 64, 66, 68, 70, 72, 76, 80, 82, 84, 86, 88, 92, 96, 104, 112, 120, 128, 132, 144, 148, 160, 176, 192, 196, 208, 212, 224, 240, 256, 258, 264, 272, 274, 280, 288, 296, 304, 312, 320, 322, 328, 336, 338, 344

Offset: 0

Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 14 2003

A primitive set of integers has no pair of elements one of which divides the other. Each element i in a subset contributes 2^(i-1) to the binary value for that subset. The integers missing from the sequence correspond to nonprimitive subsets.

			a(10)=22 since the 10th primitive set counting from 0 is {5,3,2}, which maps onto 10110 binary = 22 decimal.
From _Gus Wiseman_, Oct 31 2019: (Start)
The sequence of terms together with their binary expansions and binary indices begins:
   0:       0 ~ {}
   1:       1 ~ {1}
   2:      10 ~ {2}
   4:     100 ~ {3}
   6:     110 ~ {2,3}
   8:    1000 ~ {4}
  12:    1100 ~ {3,4}
  16:   10000 ~ {5}
  18:   10010 ~ {2,5}
  20:   10100 ~ {3,5}
  22:   10110 ~ {2,3,5}
  24:   11000 ~ {4,5}
  28:   11100 ~ {3,4,5}
(End)

Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication

A051026 gives the number of primitive subsets of the integers 1 to n.
The version for prime indices (rather than binary indices) is A316476.
The relatively prime case is A328671.
Partitions with no consecutive divisible parts are A328171.
Compositions without consecutive divisible parts are A328460.
A ranking of antichains is A326704.
Cf. A000120, A048793, A070939, A285572, A285573, A303362, A304713, A305148, A328593.

stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[0,100],stableQ[Join@@Position[Reverse[IntegerDigits[#,2]],1],Divisible]&] (* Gus Wiseman, Oct 31 2019 *)

cp's OEIS Frontend

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

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

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

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author