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,4

Comments

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

References

H. W. Gould, personal communication.

Links

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

Formula

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

Example

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

Mathematica

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

Prog

(PARI) 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
(PARI) print1("1, "); for(n=1, 46, my(s=0); forpart(X=n, s+=gcd(X)==1); print1(s, ", ")) \\ Hugo Pfoertner, Mar 27 2020
(Python)
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

Crossrefs

Cf. A000041, A018783.

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

Sequence in context: A117087 A322367 A319811 * A200144 A056498 A325093

Adjacent sequences: A000834 A000835 A000836 * A000838 A000839 A000840

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

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

Additional name from Christian G. Bower, Jun 11 2000

Status

approved