login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000837 Number of partitions of n into relatively prime parts. Also aperiodic partitions. 189

%I

%S 1,1,1,2,3,6,7,14,17,27,34,55,63,100,119,167,209,296,347,489,582,775,

%T 945,1254,1481,1951,2334,2980,3580,4564,5386,6841,8118,10085,12012,

%U 14862,17526,21636,25524,31082,36694,44582,52255,63260,74170,88931,104302

%N Number of partitions of n into relatively prime parts. Also aperiodic partitions.

%C Starting (1, 1, 2, 3, 6, 7, 14, ...), = row sums of triangle A137585. - _Gary W. Adamson_, Jan 27 2008

%C 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 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

%D H. W. Gould, personal communication.

%H 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 Mohamed El Bachraoui, <a href="http://hdl.handle.net/10515/sy5ft8f01">On the Parity of p(n,3) and p_psi(n,3)</a>, Contributions to Discrete Mathematics, Vol. 5.10 (2010).

%H 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 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%F Möbius transform of A000041. - _Christian G. Bower_, Jun 11 2000

%F Product_{n>0} 1/(1-q^n) = 1 + Sum_{n>0} a(n)*q^n/(1-q^n). - _Mamuka Jibladze_, Nov 14 2015

%F a(n) ~ exp(Pi*sqrt(2*n/3)) / (4*n*sqrt(3)). - _Vaclav Kotesovec_, Jan 28 2019

%e 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 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 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 p[n_] := IntegerPartitions[n]; l[n_] := Length[p[n]];

%t g[n_, j_] := Apply[GCD, Part[p[n], j]]

%t h[n_] := Table[g[n, j], {j, 1, l[n]}]

%t Join[{0}, Table[Count[h[n], 1], {n, 1, 20}]]

%t (* _Clark Kimberling_, Mar 09 2012 *)

%t 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 (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 (Python)

%o from sympy import npartitions, mobius, divisors

%o 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 Cf. A000740, A007916, A047968, A055892, A100953, A137585, A168532, A281116.

%K nonn,easy,nice

%O 0,4

%A _N. J. A. Sloane_

%E Corrected and extended by _David W. Wilson_, Aug 15 1996

%E Additional name from _Christian G. Bower_, Jun 11 2000

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 22:34 EDT 2019. Contains 328335 sequences. (Running on oeis4.)