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 unrestricted 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.
MATHEMATICA
Table[Count[IntegerPartitions@ n, k_ /; AllTrue[k, CoprimeQ[#, n] &]], {n, 52}] (* Michael De Vlieger, Aug 01 2017 *)
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
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