A227296 -id:A227296 - cp's OEIS frontend

A057562 Number of partitions of n into parts all relatively prime to n.

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

Offset: 1

Leroy Quet, Oct 03 2000

nonn

p is prime iff a(p) = A000041(p)-1. - Lior Manor, Feb 04 2005

			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.

Charles R Greathouse IV, Table of n, a(n) for n = 1..1000

Cf. A036998, A038566, A100347, A227296.

See also A098743 (parts don't divide n).

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

Table[Count[IntegerPartitions@ n, k_ /; AllTrue[k, CoprimeQ[#, n] &]], {n, 52}] (* Michael De Vlieger, Aug 01 2017 *)

R(n, v)=if(#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

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

Coefficient of x^n in expansion of 1/Product_{d : gcd(d, n)=1} (1-x^d). - Vladeta Jovovic, Dec 23 2004

More terms from Naohiro Nomoto, Feb 28 2002

Corrected by Vladeta Jovovic, Dec 23 2004

A079124 Number of ways to partition n into distinct positive integers <= phi(n), where phi is Euler's totient function (A000010).

Original entry on oeis.org

1, 1, 0, 1, 0, 2, 0, 4, 1, 5, 1, 11, 0, 17, 4, 13, 13, 37, 2, 53, 13, 51, 35, 103, 10, 135, 78, 167, 89, 255, 4, 339, 253, 378, 306, 542, 121, 759, 558, 872, 498, 1259, 121, 1609, 1180, 1677, 1665, 2589, 808, 3250, 1969, 3844, 3325, 5119, 1850, 6268, 4758, 7546, 7070

Offset: 0

Reinhard Zumkeller, Dec 27 2002

nonn

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education, Vol. 31, No. 1, pp. 24-28, Winter 1997. MathEduc Database (Zentralblatt MATH, 1997c.01891).

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17. Zentralblatt MATH, Zbl 1071.05501.

Cf. A079126, A000009, A079122, A079125, A067953.

Cf. A227296, A036998.

a079124 n = p [1 .. a000010 n] n where
   p _      0 = 1
   p []     _ = 0
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Jul 05 2013

with(numtheory):
b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, b(n, i-1)+`if`(i>n, 0, b(n-i, i-1))))
    end:
a:= n-> b(n, phi(n)):
seq(a(n), n=0..100);  # Alois P. Heinz, May 11 2015

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i>n, 0, b[n-i, i-1]]]]; a[n_] := b[n, EulerPhi[n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jun 30 2015, after Alois P. Heinz *)

a(n) = b(0, n), b(m, n) = 1 + sum(b(i, j): m

a(0)=1 prepended by Alois P. Heinz, May 11 2015

Showing 1-2 of 2 results.

cp's OEIS Frontend

A057562 Number of partitions of n into parts all relatively prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI