A100953 -id:A100953 - cp's OEIS frontend

A319149 Number of superperiodic integer partitions of n.

1, 1, 1, 2, 1, 3, 1, 3, 2, 3, 1, 6, 1, 3, 3, 5, 1, 7, 1, 7, 3, 3, 1, 13, 2, 3, 4, 9, 1, 13, 1, 11, 3, 3, 3, 23, 1, 3, 3, 20, 1, 17, 1, 16, 9, 3, 1, 38, 2, 9, 3, 23, 1, 25, 3, 36, 3, 3, 1, 71, 1, 3, 11, 49, 3, 31, 1, 52, 3, 19

Offset: 1

Gus Wiseman, Sep 12 2018

nonn

An integer partition is superperiodic if either it consists of a single part equal to 1 or its parts have a common divisor > 1 and its multiset of multiplicities is itself superperiodic. For example, (8,8,6,6,4,4,4,4,2,2,2,2) has multiplicities (4,4,2,2) with multiplicities (2,2) with multiplicities (2) with multiplicities (1). The first four of these partitions are periodic and the last is (1), so (8,8,6,6,4,4,4,4,2,2,2,2) is superperiodic.

			The a(24) = 11 superperiodic partitions:
  (24)
  (12,12)
  (8,8,8)
  (9,9,3,3)
  (8,8,4,4)
  (6,6,6,6)
  (10,10,2,2)
  (6,6,6,2,2,2)
  (6,6,4,4,2,2)
  (4,4,4,4,4,4)
  (4,4,4,4,2,2,2,2)
  (3,3,3,3,3,3,3,3)
  (2,2,2,2,2,2,2,2,2,2,2,2)

Cf. A000041, A000837, A018783, A024994, A047966, A098859, A100953, A181819, A182857, A304660, A305563, A317245, A317256, A319151, A319152, A319157.

wotperQ[m_]:=Or[m=={1},And[GCD@@m>1,wotperQ[Sort[Length/@Split[Sort[m]]]]]];
Table[Length[Select[IntegerPartitions[n],wotperQ]],{n,30}]

A318728 Number of cyclic compositions (necklaces of positive integers) summing to n that have only one part or whose adjacent parts (including the last with first) are coprime.

Original entry on oeis.org

1, 2, 3, 4, 6, 9, 13, 22, 34, 58, 95, 168, 280, 492, 853, 1508, 2648, 4715, 8350, 14924, 26643, 47794, 85779, 154475, 278323, 502716, 908913, 1646206, 2984547, 5418653, 9847190, 17916001, 32625618, 59470540, 108493150, 198094483, 361965239, 661891580, 1211162271

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(7) = 13 cyclic compositions with adjacent parts coprime:
  7,
  16, 25, 34,
  115,
  1114, 1213, 1132, 1123,
  11113, 11212,
  111112,
  1111111.

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

Cf. A000740, A000837, A008965, A059966, A100953, A167606, A296302, A318726, A318727, A328597.

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

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, (n > 1) + sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 27 2019

a(n) = A328597(n) + 1 for n > 1. - Andrew Howroyd, Oct 27 2019

Terms a(21) and beyond from Andrew Howroyd, Sep 08 2018

Name corrected by Gus Wiseman, Nov 04 2019

A320813 Number of non-isomorphic multiset partitions of an aperiodic multiset of weight n such that there are no singletons and all parts are themselves aperiodic multisets.

Original entry on oeis.org

1, 0, 1, 2, 5, 13, 33, 104, 293, 938, 2892

Offset: 0

Gus Wiseman, Nov 08 2018

Also the number of nonnegative integer matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, in which (1) the row sums are all > 1, (2) the positive entries in each row are relatively prime, and (3) the column-sums are relatively prime.
A multiset is aperiodic if its multiplicities are relatively prime.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(2) = 1 through a(5) = 13 multiset partitions:
  {{1,2}}  {{1,2,2}}  {{1,2,2,2}}    {{1,1,2,2,2}}
           {{1,2,3}}  {{1,2,3,3}}    {{1,2,2,2,2}}
                      {{1,2,3,4}}    {{1,2,2,3,3}}
                      {{1,2},{3,4}}  {{1,2,3,3,3}}
                      {{1,3},{2,3}}  {{1,2,3,4,4}}
                                     {{1,2,3,4,5}}
                                     {{1,2},{1,2,2}}
                                     {{1,2},{2,3,3}}
                                     {{1,2},{3,4,4}}
                                     {{1,2},{3,4,5}}
                                     {{1,3},{2,3,3}}
                                     {{1,4},{2,3,4}}
                                     {{2,3},{1,2,3}}

This is the case of A320804 where the underlying multiset is aperiodic.

Cf. A000740, A000837, A007716, A007916, A100953, A301700, A302545, A303386, A303546, A303707, A303708, A320797-A320813, A321283, A321390.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]&/@sps[Range[n]]],{s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
aperQ[m_]:=Length[m]==0||GCD@@Length/@Split[Sort[m]]==1;
Table[Length[Union[brute /@ Select[mpm[n],And[Min@@Length/@#>1,aperQ[Join@@#]&&And@@aperQ /@ #]&]]],{n,0,7}] (* Gus Wiseman, Jan 19 2024 *)

Definition corrected by Gus Wiseman, Jan 19 2024

A303708 Number of aperiodic factorizations of n using elements of A007916 (numbers that are not perfect powers).

Original entry on oeis.org

0, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 3, 1, 2, 2, 0, 1, 3, 1, 3, 2, 2, 1, 4, 0, 2, 0, 3, 1, 5, 1, 0, 2, 2, 2, 3, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 5, 0, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 0, 2, 5, 1, 3, 2, 5, 1, 8, 1, 2, 3, 3, 2, 5, 1, 5, 0, 2, 1, 9, 2, 2, 2, 4, 1, 9, 2

Offset: 1

Gus Wiseman, Apr 29 2018

nonn

An aperiodic factorization of n is a finite multiset of positive integers greater than 1 whose product is n and whose multiplicities are relatively prime.

The positions of zeros in this sequence are the prime powers A000961.

			The a(144) = 8 aperiodic factorizations are (2*2*2*3*6), (2*2*2*18), (2*2*3*12), (2*3*24), (2*6*12), (2*72), (3*48) and (6*24). Missing from this list are (12*12), (2*2*6*6) and (2*2*2*2*3*3).

Cf. A000740, A000837, A001055, A001597, A007716, A007916, A052409, A052410, A100953, A275870, A281116, A301700, A303386, A303431, A303546, A303551, A303707, A303709, A303710.

radQ[n_]:=Or[n===1,GCD@@FactorInteger[n][[All,2]]===1];
facsr[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facsr[n/d],Min@@#>=d&]],{d,Select[Rest[Divisors[n]],radQ]}]];
Table[Length[Select[facsr[n],GCD@@Length/@Split[#]===1&]],{n,100}]

a(n) = Sum_{d in A007916, d|A052409(n)} mu(d) * A303707(n^(1/d)).

A319055 Maximum product of an integer partition of n with relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 6, 6, 12, 18, 24, 36, 54, 72, 108, 162, 216, 324, 486, 648, 972, 1458, 1944, 2916, 4374, 5832, 8748, 13122, 17496, 26244, 39366, 52488, 78732, 118098, 157464, 236196, 354294, 472392, 708588, 1062882, 1417176, 2125764, 3188646, 4251528, 6377292

Offset: 1

Gus Wiseman, Sep 09 2018

nonn

After a(7), this appears to be the same as A319054.

Cf. A000740, A000792, A000793, A000837, A001414, A007916, A100953, A281116, A289508, A289509, A296302, A319054, A319057.

Table[Max[Times@@@Select[IntegerPartitions[n],GCD@@#==1&]],{n,20}]

A303547 Number of non-isomorphic periodic multiset partitions of weight n.

Original entry on oeis.org

0, 1, 1, 4, 1, 13, 1, 33, 10, 94, 1, 327, 1, 913, 100, 3017, 1, 10233, 1, 34236, 919, 119372, 1, 432234, 91, 1574227, 9945, 5916177, 1, 22734231, 1, 89003059, 119378, 356058543, 1000, 1453509039, 1, 6044132797, 1574233, 25612601420, 1, 110509543144, 1, 485161348076

Offset: 1

Gus Wiseman, Apr 26 2018

nonn

A multiset is periodic if its multiplicities have a common divisor greater than 1. For this sequence neither the parts nor their multiset union are required to be periodic, only the multiset of parts.

			Non-isomorphic representatives of the a(4) = 4 multiset partitions are {{1,1},{1,1}}, {{1,2},{1,2}}, {{1},{1},{1},{1}}, {{1},{1},{2},{2}}.

Cf. A000740, A000837, A001055, A007716, A007916, A049311, A100953, A255906, A269134, A275024, A293993, A301700, A303386, A303431, A303546.

a(n) = 1 if n is prime.

a(n) = A007716(n) - A303546(n).

More terms from Jinyuan Wang, Jun 21 2020

A318731 Number of relatively prime Lyndon compositions (aperiodic necklaces of positive integers) with sum n.

Original entry on oeis.org

1, 0, 1, 2, 5, 7, 17, 27, 54, 93, 185, 324, 629, 1143, 2175, 4050, 7709, 14469, 27593, 52276, 99839, 190371, 364721, 698508, 1342170, 2580165, 4970952, 9585232, 18512789, 35787985, 69273665, 134211600, 260300799, 505278705, 981706783

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(6) = 7 relatively prime Lyndon compositions are 15, 114, 132, 123, 1113, 1122, 11112.
The a(7) = 17 relatively prime Lyndon compositions:
  16, 25, 34,
  115, 142, 124, 133, 223,
  1114, 1213, 1132, 1123, 1222,
  11113, 11212, 11122,
  111112.

Cf. A000740, A000837, A008965, A059966, A100953, A296302.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],LyndonQ[#]&&GCD@@#==1&]],{n,10}]

Moebius transform of A059966. Second Moebius transform of A008965.

A318748 Number of integer compositions of n that have only one part or whose consecutive parts are coprime and the last and first part are also coprime.

Original entry on oeis.org

1, 1, 2, 4, 7, 13, 24, 43, 82, 151, 285, 535, 1005, 1883, 3533, 6631, 12460, 23407, 43952, 82538, 154999, 291088, 546674, 1026687, 1928118, 3621017, 6800300, 12771086, 23984329, 45042959, 84591339, 158863807, 298348613, 560303342, 1052258402, 1976157510

Offset: 0

Gus Wiseman, Sep 02 2018

nonn

			The a(5) = 13 compositions with adjacent parts coprime:
  (5)
  (41) (14) (32) (23)
  (311) (131) (113)
  (2111) (1211) (1121) (1112)
  (11111)
Missing from this list are (221), (212), and (122).

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

Cf. A000740, A008965, A059966, A100953, A167606, A296302, A318726, A318727, A318728, A318745, A328609.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Or[Length[#]==1,And@@CoprimeQ@@@Partition[#,2,1,1]]&]],{n,20}]

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)={concat([1], vector(n, i, i > 1) + sum(k=1, n, b(n, k, (i, j)->gcd(i, j)==1)))} \\ Andrew Howroyd, Nov 01 2019

a(n) = A328609(n) + 1 for n > 1. - Andrew Howroyd, Nov 01 2019

a(21)-a(35) from Alois P. Heinz, Sep 02 2018

Name corrected by Gus Wiseman, Nov 04 2019

A321283 Number of non-isomorphic multiset partitions of weight n in which the part sizes are relatively prime.

Original entry on oeis.org

1, 1, 2, 7, 21, 84, 214, 895, 2607, 9591, 31134, 119313, 400950, 1574123, 5706112, 22572991, 86933012, 356058243, 1427784135, 6044132304, 25342935667, 110414556330, 481712291885, 2166488898387, 9784077216457, 45369658599779, 211869746691055, 1011161497851296, 4871413403219085

Offset: 0

Gus Wiseman, Nov 06 2018

nonn

Also the number of nonnegative integer matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, in which the row sums are relatively prime.
Also the number of non-isomorphic multiset partitions of weight n in which the multiset union of the parts is aperiodic, where a multiset is aperiodic if its multiplicities are relatively prime.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions with relatively prime part-sizes:
  {{1}}  {{1},{1}}  {{1},{1,1}}    {{1},{1,1,1}}
         {{1},{2}}  {{1},{2,2}}    {{1},{1,2,2}}
                    {{1},{2,3}}    {{1},{2,2,2}}
                    {{2},{1,2}}    {{1},{2,3,3}}
                    {{1},{1},{1}}  {{1},{2,3,4}}
                    {{1},{2},{2}}  {{2},{1,2,2}}
                    {{1},{2},{3}}  {{3},{1,2,3}}
                                   {{1},{1},{1,1}}
                                   {{1},{1},{2,2}}
                                   {{1},{1},{2,3}}
                                   {{1},{2},{1,2}}
                                   {{1},{2},{2,2}}
                                   {{1},{2},{3,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{1},{1},{1}}
                                   {{1},{1},{2},{2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}
Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions with aperiodic multiset union:
  {{1}}  {{1,2}}    {{1,2,2}}      {{1,2,2,2}}
         {{1},{2}}  {{1,2,3}}      {{1,2,3,3}}
                    {{1},{2,2}}    {{1,2,3,4}}
                    {{1},{2,3}}    {{1},{2,2,2}}
                    {{2},{1,2}}    {{1,2},{2,2}}
                    {{1},{2},{2}}  {{1},{2,3,3}}
                    {{1},{2},{3}}  {{1,2},{3,3}}
                                   {{1},{2,3,4}}
                                   {{1,2},{3,4}}
                                   {{1,3},{2,3}}
                                   {{2},{1,2,2}}
                                   {{3},{1,2,3}}
                                   {{1},{1},{2,3}}
                                   {{1},{2},{2,2}}
                                   {{1},{2},{3,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

Cf. A000740, A000837, A007716, A007916, A100953, A301700, A303386, A303431, A303546, A303547, A320800-A320810.

\\ See links in A339645 for combinatorial species functions.
seq(n)={my(A=symGroupSeries(n)); NumUnlabeledObjsSeq(sCartProd(sExp(A), 1 + sum(d=1, n, moebius(d) * (-1 + sExp(O(x*x^n) + sum(i=1, n\d, polcoef(A,i*d)*x^(i*d)))) )))} \\ Andrew Howroyd, Jan 17 2023

\\ faster self contained program.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={EulerT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k))}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, my(u=vector(n, t, K(q, t, n\t))); s+=permcount(q)*polcoef(sum(d=1, n, moebius(d)*exp(sum(t=1, n\d, sum(i=1, n\(t*d), u[t][i*d]*x^(i*d*t))/t, O(x*x^n)) )), n)); s/n!)} \\ Andrew Howroyd, Jan 17 2023

a(n) = A007716(n) - A320810(n). - Andrew Howroyd, Jan 17 2023

Terms a(11) and beyond from Andrew Howroyd, Jan 17 2023

A300275 G.f.: 1 + Sum_{n>=1} a(n)*x^n/(1 - x^n) = Product_{n>=1} 1/(1 - x^n)^n.

Original entry on oeis.org

1, 2, 5, 10, 23, 40, 85, 147, 276, 474, 858, 1421, 2484, 4079, 6850, 11137, 18333, 29277, 47329, 74768, 118703, 185614, 290782, 449568, 696009, 1066258, 1632376, 2479057, 3759611, 5661568, 8512308, 12722132, 18974109, 28157619, 41690937, 61453929, 90379783

Offset: 1

Ilya Gutkovskiy, Mar 01 2018

nonn

Moebius transform of A000219.
From Gus Wiseman, Jan 21 2019: (Start)
Also the number of plane partitions of n with relatively prime entries. For example, the a(4) = 10 plane partitions are:
  31   211   1111
.
  3   21   11   111
  1   1    11   1
.
  2   11
  1   1
  1   1
.
  1
  1
  1
  1
Also the number of plane partitions of n whose multiset of rows is aperiodic, meaning its multiplicities are relatively prime. For example, the a(4) = 10 plane partitions are:
  4   31   22   211   1111
.
  3   21   111
  1   1    1
.
  2   11
  1   1
  1   1
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Transforms

Cf. A000219, A000837, A078374, A300274, A300276, A300277, A300278.

Cf. A100953, A303546, A320802, A323584, A323585, A323587.

with(numtheory):
b:= proc(n) option remember; `if`(n=0, 1, add(
      b(n-j)*sigma[2](j), j=1..n)/n)
    end:
a:= n-> add(b(d)*mobius(n/d), d=divisors(n)):
seq(a(n), n=1..40);  # Alois P. Heinz, Jun 21 2018

nn = 37; f[x_] := 1 + Sum[a[n] x^n/(1 - x^n), {n, 1, nn}]; sol = SolveAlways[0 == Series[f[x] - Product[1/(1 - x^n)^n, {n, 1, nn}], {x, 0, nn}], x]; Table[a[n], {n, 1, nn}] /. sol // Flatten
s[n_] := SeriesCoefficient[Product[1/(1 - x^k)^k, {k, 1, n}], {x, 0, n}]; a[n_] := Sum[MoebiusMu[n/d] s[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 37}]

a(n) = Sum_{d|n} mu(n/d)*A000219(d).

cp's OEIS Frontend

A319149 Number of superperiodic integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A318728 Number of cyclic compositions (necklaces of positive integers) summing to n that have only one part or whose adjacent parts (including the last with first) are coprime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A320813 Number of non-isomorphic multiset partitions of an aperiodic multiset of weight n such that there are no singletons and all parts are themselves aperiodic multisets.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A303708 Number of aperiodic factorizations of n using elements of A007916 (numbers that are not perfect powers).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A319055 Maximum product of an integer partition of n with relatively prime parts.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A303547 Number of non-isomorphic periodic multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A318731 Number of relatively prime Lyndon compositions (aperiodic necklaces of positive integers) with sum n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A318748 Number of integer compositions of n that have only one part or whose consecutive parts are coprime and the last and first part are also coprime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions