A100953 -id:A100953 - cp's OEIS frontend

A000837 Number of partitions of n into relatively prime parts. Also aperiodic partitions.

1, 1, 1, 2, 3, 6, 7, 14, 17, 27, 34, 55, 63, 100, 119, 167, 209, 296, 347, 489, 582, 775, 945, 1254, 1481, 1951, 2334, 2980, 3580, 4564, 5386, 6841, 8118, 10085, 12012, 14862, 17526, 21636, 25524, 31082, 36694, 44582, 52255, 63260, 74170, 88931, 104302

Offset: 0

N. J. A. Sloane

Starting (1, 1, 2, 3, 6, 7, 14, ...), = row sums of triangle A137585. - Gary W. Adamson, Jan 27 2008
Triangle A168532 has aerated variants of this sequence in each column starting with offset 1, row sums = A000041. -  Gary W. Adamson, Nov 28 2009
A partition is aperiodic iff its multiplicities are relatively prime, i.e., its Heinz number (A215366) is not a perfect power (A007916). - Gus Wiseman, Dec 19 2017
This sequence is monotonically increasing; each partition of n-1 can have a part of size 1 added to it to get a partition counted in a(n). - Franklin T. Adams-Watters, Jul 24 2020

			Of the 11 partitions of 6, we must exclude 6, 4+2, 3+3 and 2+2+2, so a(6) = 11 - 4 = 7.
For n=6, 2+2+1+1 is periodic because it can be written 2*(2+1), similarly 1+1+1+1+1+1, 3+3 and 2+2+2.
The a(6) = 7 partitions into relatively prime parts are (51), (411), (321), (3111), (2211), (21111), (111111). The a(6) = 7 aperiodic partitions are (6), (51), (42), (411), (321), (3111), (21111). - _Gus Wiseman_, Dec 19 2017

H. W. Gould, personal communication.

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000 (terms 0..1000 from T. D. Noe)
Mohamed El Bachraoui, On the Parity of p(n,3) and p_psi(n,3), Contributions to Discrete Mathematics, Vol. 5.2 (2010).
Wolfdieter Lang, Cantor's List of Real Algebraic Numbers of Heights 1 to 7, arXiv:2307.10645 [math.NT], 2023.
Mircea Merca and Maxie D. Schmidt, Generating Special Arithmetic Functions by Lambert Series Factorizations, arXiv:1706.00393 [math.NT], 2017. See Remark 3.4.
N. J. A. Sloane, Transforms

Cf. A000041, A018783.

Cf. A000740, A007916, A047968, A055892, A100953, A137585, A168532, A281116.

p[n_] := IntegerPartitions[n]; l[n_] := Length[p[n]]; g[n_, j_] := Apply[GCD, Part[p[n], j]]; h[n_] := Table[g[n, j], {j, 1, l[n]}]; Join[{1}, Table[Count[h[n], 1], {n, 1, 20}]]
(* Clark Kimberling, Mar 09 2012 *)
a[0] = 1; a[n_] := Sum[ MoebiusMu[n/d] * PartitionsP[d], {d, Divisors[n]}]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Oct 03 2013 *)

N=66; x='x+O('x^N); gf=2+sum(n=1,N, (1/eta(x^n))*moebius(n)); Vec(gf) \\ Joerg Arndt, May 11 2013

print1("1, "); for(n=1,46,my(s=0);forpart(X=n,s+=gcd(X)==1);print1(s,", ")) \\ Hugo Pfoertner, Mar 27 2020

from sympy import npartitions, mobius, divisors
def a(n): return 1 if n==0 else sum(mobius(n//d)*npartitions(d) for d in divisors(n)) # Indranil Ghosh, Apr 26 2017

Möbius transform of A000041. - Christian G. Bower, Jun 11 2000
Product_{n>0} 1/(1-q^n) = 1 + Sum_{n>0} a(n)*q^n/(1-q^n). - Mamuka Jibladze, Nov 14 2015
a(n) ~ exp(Pi*sqrt(2*n/3)) / (4*n*sqrt(3)). - Vaclav Kotesovec, Jan 28 2019
a(n) <= p(n) <= a(n+1), where p(n) is the number of partitions of n (A000041). - Franklin T. Adams-Watters, Jul 24 2020

Corrected and extended by David W. Wilson, Aug 15 1996

Additional name from Christian G. Bower, Jun 11 2000

A047968 a(n) = Sum_{d|n} p(d), where p(d) = A000041 = number of partitions of d.

Original entry on oeis.org

1, 3, 4, 8, 8, 17, 16, 30, 34, 52, 57, 99, 102, 153, 187, 261, 298, 432, 491, 684, 811, 1061, 1256, 1696, 1966, 2540, 3044, 3876, 4566, 5846, 6843, 8610, 10203, 12610, 14906, 18491, 21638, 26508, 31290, 38044, 44584, 54133, 63262, 76241

Offset: 1

N. J. A. Sloane, Dec 11 1999

nonn

Inverse Moebius transform of A000041.
Row sums of triangle A137587. - Gary W. Adamson, Jan 27 2008
Row sums of triangle A168021. - Omar E. Pol, Nov 20 2009
Row sums of triangle A168017. Row sums of triangle A168018. - Omar E. Pol, Nov 25 2009
Sum of the partition numbers of the divisors of n. - Omar E. Pol, Feb 25 2014
Conjecture: for n > 6, a(n) is strictly increasing. - Franklin T. Adams-Watters, Apr 19 2014
Number of constant multiset partitions of multisets spanning an initial interval of positive integers with multiplicities an integer partition of n. - Gus Wiseman, Sep 16 2018

			For n = 10 the divisors of 10 are 1, 2, 5, 10, hence the partition numbers of the divisors of 10 are 1, 2, 7, 42, so a(10) = 1 + 2 + 7 + 42 = 52. - _Omar E. Pol_, Feb 26 2014
From _Gus Wiseman_, Sep 16 2018: (Start)
The a(6) = 17 constant multiset partitions:
  (111111)  (111)(111)    (11)(11)(11)  (1)(1)(1)(1)(1)(1)
  (111222)  (12)(12)(12)
  (111122)  (112)(112)
  (112233)  (123)(123)
  (111112)
  (111123)
  (111223)
  (111234)
  (112234)
  (112345)
  (123456)
(End)

T. D. Noe, Table of n, a(n) for n=1..1000
N. J. A. Sloane, Transforms

Cf. A000041, A000837, A047966, A055893, A137587, A003606 (Euler transform).

Cf. A002033, A003238, A018783, A034729, A052409, A078392, A100953, A319162.

with(combinat): with(numtheory): a := proc(n) c := 0: l := sort(convert(divisors(n), list)): for i from 1 to nops(l) do c := c+numbpart(l[i]) od: RETURN(c): end: for j from 1 to 60 do printf(`%d, `, a(j)) od: # Zerinvary Lajos, Apr 14 2007

a[n_] := Sum[ PartitionsP[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 44}] (* Jean-François Alcover, Oct 03 2013 *)

G.f.: Sum_{k>0} (-1+1/Product_{i>0} (1-z^(k*i))). - Vladeta Jovovic, Jun 22 2003
G.f.: sum(n>0,A000041(n)*x^n/(1-x^n)). - Mircea Merca, Feb 24 2014.
a(n) = A168111(n) + A000041(n). - Omar E. Pol, Feb 26 2014
a(n) = Sum_{y is a partition of n} A000005(GCD(y)). - Gus Wiseman, Sep 16 2018

A303386 Number of aperiodic factorizations of n > 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 4, 2, 2, 1, 7, 1, 2, 2, 4, 1, 5, 1, 6, 2, 2, 2, 7, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 12, 1, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11, 1, 2, 4, 7, 2, 5, 1, 4, 2, 5, 1, 16, 1, 2, 4, 4, 2, 5, 1, 12, 3, 2, 1, 11, 2, 2, 2, 7, 1, 11, 2, 4, 2, 2, 2, 19, 1, 4, 4, 7, 1, 5, 1, 7, 5

Offset: 2

Gus Wiseman, Apr 23 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 a(36) = 7 aperiodic factorizations are (2*2*9), (2*3*6), (2*18), (3*3*4), (3*12), (4*9), and (36). Missing from this list are (2*2*3*3) and (6*6).

Antti Karttunen, Table of n, a(n) for n = 2..65537

Cf. A000740, a(2^n) = A000837(n), A001055, A007716, A007916, A045778, A052409, A052410, A100953, A162247, A275024, A275870, A281113, A281116, A301700, A302242, A303431.

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

A001055(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1)&&(d<=m), s += A001055(n/d, d))); (s));
A052409(n) = { my(k=ispower(n)); if(k, k, n>1); }; \\ From A052409
A303386(n) = if(1==n,n,my(r); sumdiv(A052409(n),d, ispower(n,d,&r); moebius(d)*A001055(r))); \\ Antti Karttunen, Sep 25 2018

a(n) = Sum_{d|A052409(n)} mu(d) * A001055(n^(1/d)), where mu = A008683.

More terms from Antti Karttunen, Sep 25 2018

A301700 Number of aperiodic rooted trees with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 4, 10, 21, 52, 120, 290, 697, 1713, 4200, 10446, 26053, 65473, 165257, 419357, 1068239, 2732509, 7013242, 18059960, 46641983, 120790324, 313593621, 816046050, 2128101601, 5560829666, 14557746453, 38177226541, 100281484375, 263815322761, 695027102020

Offset: 1

Gus Wiseman, Apr 23 2018

nonn

An unlabeled rooted tree is aperiodic if the multiset of branches of the root is an aperiodic multiset, meaning it has relatively prime multiplicities, and each branch is also aperiodic.

			The a(6) = 10 aperiodic trees are (((((o))))), (((o(o)))), ((o((o)))), ((oo(o))), (o(((o)))), (o(o(o))), ((o)((o))), (oo((o))), (o(o)(o)), (ooo(o)).

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

Cf. A000081, A000740, A000837, A001678, A003238, A004111, A007716, A007916, A100953, A276625, A284639, A290689, A298422, A303386, A303431.

arut[n_]:=arut[n]=If[n===1,{{}},Join@@Function[c,Select[Union[Sort/@Tuples[arut/@c]],GCD@@Length/@Split[#]===1&]]/@IntegerPartitions[n-1]];
Table[Length[arut[n]],{n,20}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
MoebiusT(v)={vector(#v, n, sumdiv(n,d,moebius(n/d)*v[d]))}
seq(n)={my(v=[1]); for(n=2, n, v=concat([1], MoebiusT(EulerT(v)))); v} \\ Andrew Howroyd, Sep 01 2018

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

A305148 Number of integer partitions of n whose distinct parts are pairwise indivisible.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 12, 12, 17, 20, 22, 28, 35, 39, 48, 55, 65, 79, 90, 105, 121, 143, 166, 190, 219, 254, 290, 332, 382, 436, 493, 567, 637, 729, 824, 931, 1052, 1186, 1334, 1504, 1691, 1894, 2123, 2380, 2664, 2968, 3319, 3704, 4119, 4586, 5110

Offset: 0

Gus Wiseman, May 26 2018

nonn

			The a(9) = 7 integer partitions are (9), (72), (54), (522), (333), (3222), (111111111).

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..360 (terms 0..300 from Alois P. Heinz)

Cf. A000837, A001055, A001970, A007359, A007716, A051424, A078374, A100953, A285572, A285573, A302696, A303362, A305079, A305149, A305150.

Table[Length[Select[IntegerPartitions[n],Select[Tuples[Union[#],2],UnsameQ@@#&&Divisible@@#&]=={}&]],{n,20}]

More terms from Alois P. Heinz, May 26 2018

A303546 Number of non-isomorphic aperiodic multiset partitions of weight n.

Original entry on oeis.org

1, 3, 9, 29, 90, 285, 909, 2984, 9935, 34113, 119368, 428923, 1574223, 5915235, 22699730, 89000042, 356058539, 1453069854, 6044132793, 25612564200, 110503626702, 485161228675, 2166488899641, 9835209480533, 45370059225227

Offset: 1

Gus Wiseman, Apr 26 2018

nonn

A multiset is aperiodic if its multiplicities are relatively prime. For this sequence neither the parts nor their multiset union are required to be aperiodic, only the multiset of parts.

			Non-isomorphic representatives of the a(3) = 9 aperiodic multiset partitions are:
  {{1,1,1}}, {{1,2,2}}, {{1,2,3}},
  {{1},{1,1}}, {{1},{2,2}}, {{1},{2,3}}, {{2},{1,2}},
  {{1},{2},{2}}, {{1},{2},{3}}.

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

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

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

A296302 Number of aperiodic compositions of n with relatively prime parts. Number of compositions of n with relatively prime parts and relatively prime run-lengths.

Original entry on oeis.org

1, 0, 2, 5, 14, 24, 62, 114, 249, 480, 1022, 1978, 4094, 8064, 16348, 32520, 65534, 130512, 262142, 523270, 1048444, 2095104, 4194302, 8384316, 16777185, 33546240, 67108356, 134201398, 268435454, 536837136, 1073741822, 2147418240, 4294965244, 8589803520

Offset: 1

Gus Wiseman, Dec 11 2017

nonn

			The a(6) = 24 aperiodic compositions with relatively prime parts are:
(15), (51),
(114), (123), (132), (141), (213), (231), (312), (321), (411),
(1113), (1122), (1131), (1221), (1311), (2112), (2211), (3111),
(11112), (11121), (11211), (12111), (21111).

Robert G. Wilson v, Table of n, a(n) for n = 1..1000

Cf. A000005, A000740, A000837, A007427, A008683, A008965, A059966, A060223, A100953, A228369, A281013.

Table[DivisorSum[n,Function[d,MoebiusMu[n/d]*DivisorSum[d,MoebiusMu[#]*2^(d/#-1)&]]],{n,20}]

a = mu * mu * c, where * is Dirichlet convolution and c(n) = 2^(n-1).

A298748 Heinz numbers of aperiodic (relatively prime multiplicities) integer partitions with relatively prime parts.

Original entry on oeis.org

2, 6, 10, 12, 14, 15, 18, 20, 22, 24, 26, 28, 30, 33, 34, 35, 38, 40, 42, 44, 45, 46, 48, 50, 51, 52, 54, 55, 56, 58, 60, 62, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 84, 85, 86, 88, 90, 92, 93, 94, 95, 96, 98, 99, 102, 104, 105, 106, 108, 110, 112, 114

Offset: 1

Gus Wiseman, Mar 01 2018

nonn

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

			Sequence of partitions begins: (1), (21), (31), (211), (41), (32), (221), (311), (51), (2111), (61), (411), (321), (52), (71), (43), (81), (3111), (421), (511), (322), (91), (21111), (331), (72), (611), (2221), (53), (4111).

Cf. A000740, A000837, A007916, A052410, A064989, A100953, A289508, A289509, A296302, A300272.

Select[Range[100],With[{t=Transpose[FactorInteger[#]]},And[GCD@@PrimePi/@t[[1]]===1,GCD@@t[[2]]===1]]&] (* Gus Wiseman, Apr 14 2018 *)

A316888 Heinz numbers of aperiodic integer partitions into relatively prime parts whose reciprocal sum is 1.

Original entry on oeis.org

2, 195, 3185, 6475, 10527, 16401, 20445, 20535, 21045, 25365, 46155, 164255, 171941, 218855, 228085, 267883, 312785, 333925, 333935, 335405, 343735, 355355, 414295, 442975, 474513, 527425, 549575, 607475, 633777, 691041, 711321, 722425, 753865, 804837, 822783

Offset: 1

Gus Wiseman, Jul 16 2018

nonn

The reciprocal sum of (y_1, ..., y_k) is 1/y_1 + ... + 1/y_k.
The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).
A partition is aperiodic if its multiplicities are relatively prime.
Does not contain 29888089, which belongs to A316890 and is the Heinz number of a periodic partition.

			The partition (6,4,4,3) with Heinz number 3185 is aperiodic, has relatively prime parts, and 1/6 + 1/4 + 1/4 + 1/3 = 1, so 3185 belongs to the sequence.
The sequence of partitions whose Heinz numbers belong to the sequence begins: (1), (6,3,2), (6,4,4,3), (12,4,3,3), (10,5,5,2), (20,5,4,2), (15,10,3,2), (12,12,3,2), (18,9,3,2), (24,8,3,2), (42,7,3,2).

Gus Wiseman, Sequences counting and ranking integer partitions by their reciprocal sums

Cf. A000837, A002966, A007916, A051908, A100953, A289509, A296150, A316855, A316856, A316857, A316888-A316904.

Select[Range[2,100000],And[GCD@@FactorInteger[#][[All,2]]==1,GCD@@PrimePi/@FactorInteger[#][[All,1]]==1,Sum[m[[2]]/PrimePi[m[[1]]],{m,FactorInteger[#]}]==1]&]

A316904 Heinz numbers of aperiodic integer partitions into relatively prime parts whose reciprocal sum is an integer.

Original entry on oeis.org

2, 18, 72, 162, 195, 250, 288, 294, 390, 500, 588, 648, 780, 1125, 1152, 1176, 1458, 1560, 1755, 2000, 2250, 2352, 2592, 2646, 3120, 3185, 3510, 4000, 4500, 4608, 4704, 4802, 5292, 6240, 6370, 6475, 7020, 8450, 9000, 9408, 10125, 10368, 10527, 10584, 12480

Offset: 1

Gus Wiseman, Jul 16 2018

nonn

The reciprocal sum of (y_1, ..., y_k) is 1/y_1 + ... + 1/y_k.
The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).
A partition is aperiodic if its multiplicities are relatively prime.

			The sequence of partitions whose Heinz numbers belong to this sequence begins: (1), (221), (22111), (22221), (632), (3331), (2211111), (4421), (6321), (33311), (44211), (2222111).

Gus Wiseman, Sequences counting and ranking integer partitions by their reciprocal sums

Cf. A000837, A002966, A051908, A058360, A100953, A296150, A316854, A316855, A316856, A316857, A316888-A316904.

Select[Range[2,20000],And[GCD@@FactorInteger[#][[All,2]]==1,GCD@@PrimePi/@FactorInteger[#][[All,1]]==1,IntegerQ[Sum[m[[2]]/PrimePi[m[[1]]],{m,FactorInteger[#]}]]]&]

cp's OEIS Frontend

A000837 Number of partitions of n into relatively prime parts. Also aperiodic partitions.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A047968 a(n) = Sum_{d|n} p(d), where p(d) = A000041 = number of partitions of d.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A303386 Number of aperiodic factorizations of n > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A301700 Number of aperiodic rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A305148 Number of integer partitions of n whose distinct parts are pairwise indivisible.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A303546 Number of non-isomorphic aperiodic multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A296302 Number of aperiodic compositions of n with relatively prime parts. Number of compositions of n with relatively prime parts and relatively prime run-lengths.

Views

Author

Keywords

Examples

Links

Crossrefs