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. 109
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 (list; graph; refs; listen; history; text; internal format)
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

REFERENCES

H. W. Gould, personal communication.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..1000

Mohamed El Bachraoui, On the Parity of p(n,3) and p_psi(n,3), Contributions to Discrete Mathematics, Vol. 5.10 (2010).

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

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[{0}, 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

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

Sequence in context: A191615 A018606 A117087 * A200144 A056498 A018652

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

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

License Agreements, Terms of Use, Privacy Policy. . Note: Contributor's License Agreement was changed Aug 14 2018.

Last modified August 15 01:13 EDT 2018. Contains 313756 sequences. (Running on oeis4.)