A114374 Number of partitions of n into parts that are not squarefree.

1, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 3, 1, 0, 0, 5, 2, 2, 0, 7, 3, 2, 0, 11, 6, 4, 3, 15, 8, 6, 3, 22, 13, 11, 6, 34, 18, 15, 9, 46, 27, 24, 17, 64, 43, 33, 23, 89, 60, 51, 37, 124, 84, 78, 51, 166, 119, 109, 78, 226, 168, 152, 118, 300, 228, 215, 166, 404, 313, 300, 230, 546, 421, 409

Offset: 0

Author

Reinhard Zumkeller, Feb 09 2006

Keywords

• nonn

Comments

a(A078135(n)) = 0; a(A078137(n)) > 0.

Examples

			a(12) = #{2*2*3, 2*2*2 + 2*2, 2*2 + 2*2 + 2*2} = 3;
a(13) = #{3*3 + 2*2} = 1.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A013929, A073576.

Cf. A256012.

Programs

Haskell

a114374 = p a013929_list where
   p _          0 = 1
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Jun 01 2015

Maple

with(numtheory):
b:= proc(n, i) option remember;
      `if`(n=0, 1, `if`(i<1, 0, b(n, i-1)+
      `if`(i>n or issqrfree(i), 0, b(n-i, i))))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 03 2015

Mathematica

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

Formula

a(n) = A000041(n) - A073576(n) - A117395(n). - Reinhard Zumkeller, Mar 11 2006

G.f.: Product_{k>=1} (1 - mu(k)^2*x^k)/(1 - x^k), where mu(k) is the Moebius function (A008683). - Ilya Gutkovskiy, Dec 30 2016

Extensions

Offset changed and a(0)=1 prepended by Reinhard Zumkeller, Jun 01 2015