cp's OEIS Frontend

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

%I A000837 #92 Jul 25 2023 09:50:59
%S A000837 1,1,1,2,3,6,7,14,17,27,34,55,63,100,119,167,209,296,347,489,582,775,
%T A000837 945,1254,1481,1951,2334,2980,3580,4564,5386,6841,8118,10085,12012,
%U A000837 14862,17526,21636,25524,31082,36694,44582,52255,63260,74170,88931,104302
%N A000837 Number of partitions of n into relatively prime parts. Also aperiodic partitions.
%C A000837 Starting (1, 1, 2, 3, 6, 7, 14, ...), = row sums of triangle A137585. - _Gary W. Adamson_, Jan 27 2008
%C A000837 Triangle A168532 has aerated variants of this sequence in each column starting with offset 1, row sums = A000041. -  _Gary W. Adamson_, Nov 28 2009
%C A000837 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
%C A000837 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
%D A000837 H. W. Gould, personal communication.
%H A000837 Vaclav Kotesovec, <a href="/A000837/b000837.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1000 from T. D. Noe)
%H A000837 Mohamed El Bachraoui, <a href="https://doi.org/10.11575/cdm.v5i2.62030">On the Parity of p(n,3) and p_psi(n,3)</a>, Contributions to Discrete Mathematics, Vol. 5.2 (2010).
%H A000837 Wolfdieter Lang, <a href="https://arxiv.org/abs/2307.10645">Cantor's List of Real Algebraic Numbers of Heights 1 to 7</a>, arXiv:2307.10645 [math.NT], 2023.
%H A000837 Mircea Merca and Maxie D. Schmidt, <a href="https://arxiv.org/abs/1706.00393">Generating Special Arithmetic Functions by Lambert Series Factorizations</a>, arXiv:1706.00393 [math.NT], 2017. See Remark 3.4.
%H A000837 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%F A000837 Möbius transform of A000041. - _Christian G. Bower_, Jun 11 2000
%F A000837 Product_{n>0} 1/(1-q^n) = 1 + Sum_{n>0} a(n)*q^n/(1-q^n). - _Mamuka Jibladze_, Nov 14 2015
%F A000837 a(n) ~ exp(Pi*sqrt(2*n/3)) / (4*n*sqrt(3)). - _Vaclav Kotesovec_, Jan 28 2019
%F A000837 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
%e A000837 Of the 11 partitions of 6, we must exclude 6, 4+2, 3+3 and 2+2+2, so a(6) = 11 - 4 = 7.
%e A000837 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.
%e A000837 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
%t A000837 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}]]
%t A000837 (* _Clark Kimberling_, Mar 09 2012 *)
%t A000837 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 *)
%o A000837 (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
%o A000837 (PARI) print1("1, "); for(n=1,46,my(s=0);forpart(X=n,s+=gcd(X)==1);print1(s,", ")) \\ _Hugo Pfoertner_, Mar 27 2020
%o A000837 (Python)
%o A000837 from sympy import npartitions, mobius, divisors
%o A000837 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
%Y A000837 Cf. A000041, A018783.
%Y A000837 Cf. A000740, A007916, A047968, A055892, A100953, A137585, A168532, A281116.
%K A000837 nonn,easy,nice
%O A000837 0,4
%A A000837 _N. J. A. Sloane_
%E A000837 Corrected and extended by _David W. Wilson_, Aug 15 1996
%E A000837 Additional name from _Christian G. Bower_, Jun 11 2000