|
| |
|
|
A000837
|
|
Number of partitions of n into relatively prime parts. Also aperiodic partitions.
|
|
232
|
|
|
|
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
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).
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
|
| |
|
|
