|
| |
|
|
A057562
|
|
Number of partitions of n into parts all relatively prime to n.
|
|
6
|
|
|
|
1, 1, 2, 2, 6, 2, 14, 6, 16, 7, 55, 6, 100, 17, 44, 32, 296, 14, 489, 35, 178, 77, 1254, 30, 1156, 147, 731, 142, 4564, 25, 6841, 390, 1668, 474, 4780, 114, 21636, 810, 4362, 432, 44582, 103, 63260, 1357, 4186, 2200, 124753, 364, 105604, 1232, 24482, 3583
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
p is prime iff a(p) = A000041(p)-1. - Lior Manor Feb 04 2005
|
|
|
LINKS
|
Charles R Greathouse IV, Table of n, a(n) for n = 1..1000
|
|
|
FORMULA
|
Coefficient of x^n in expansion of 1/Product_{d : gcd(d, n)=1} (1-x^d). - Vladeta Jovovic, Dec 23 2004
|
|
|
EXAMPLE
|
The unresticted partitions of 4 are 1+1+1+1, 1+1+2, 1+3, 2+2 and 4. Of these, only 1+1+1+1 and 1+3 contain parts which are all relatively prime to 4. So a(4) = 2.
|
|
|
PROG
|
(PARI) R(n, v)=if(#v<2 || n<v[2], n>=0, sum(i=1, #v, R(n-v[i], v[1..i])))
a(n)=if(isprime(n), return(numbpart(n)-1)); R(n, select(k->gcd(k, n)==1, vector(n, i, i))) \\ Charles R Greathouse IV, Sep 13 2012
(PARI) a(n)=polcoeff(1/prod(k=1, n, if(gcd(k, n)==1, 1-x^k, 1), O(x^(n+1))+1), n) \\ Charles R Greathouse IV, Sep 13 2012
(Haskell)
a057562 n = p (a038566_row n) n where
p _ 0 = 1
p [] _ = 0
p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Jul 05 2013
|
|
|
CROSSREFS
|
Cf. A036998, A038566, A100347, A227296.
See also A098743 (parts don't divide n).
Sequence in context: A055934 A096217 A098555 * A102628 A211776 A036655
Adjacent sequences: A057559 A057560 A057561 * A057563 A057564 A057565
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Leroy Quet, Oct 03 2000
|
|
|
EXTENSIONS
|
More terms from Naohiro Nomoto, Feb 28 2002
Corrected by Vladeta Jovovic, Dec 23 2004
|
|
|
STATUS
|
approved
|
| |
|
|
