cp's OEIS Frontend

A073576 Number of partitions of n into squarefree parts.

%I A073576 #49 Aug 23 2024 10:03:12
%S A073576 1,1,2,3,4,6,9,12,16,21,28,36,47,60,76,96,120,150,185,228,280,342,416,
%T A073576 504,608,731,877,1048,1249,1484,1759,2079,2452,2885,3387,3968,4640,
%U A073576 5413,6304,7328,8504,9852,11395,13159,15172,17468,20082,23056,26434,30267
%N A073576 Number of partitions of n into squarefree parts.
%C A073576 Euler transform of the absolute values of A008683. - _Tilman Neumann_, Dec 13 2008
%C A073576 Euler transform of A008966. - _Vaclav Kotesovec_, Mar 31 2018
%H A073576 Alois P. Heinz, <a href="/A073576/b073576.txt">Table of n, a(n) for n = 0..10000</a>
%F A073576 G.f.: 1/Product_{k>0} (1-x^A005117(k)).
%F A073576 a(n) = 1/n*Sum_{k=1..n} A048250(k)*a(n-k).
%F A073576 a(n) = A000041(n) - A114374(n) - A117395(n), n>0. - _Reinhard Zumkeller_, Mar 11 2006
%F A073576 G.f.: 1 + Sum_{i>=1} mu(i)^2*x^i / Product_{j=1..i} (1 - mu(j)^2*x^j). - _Ilya Gutkovskiy_, Jun 05 2017
%F A073576 a(n) ~ exp(2*sqrt(n)) / (4*Pi^(3/2)*n^(1/4)). - _Vaclav Kotesovec_, Mar 24 2018
%p A073576 with(numtheory):
%p A073576 a:= proc(n) option remember; `if`(n=0, 1, add(add(d*
%p A073576       abs(mobius(d)), d=divisors(j)) *a(n-j), j=1..n)/n)
%p A073576     end:
%p A073576 seq(a(n), n=0..60);  # _Alois P. Heinz_, Mar 05 2015
%t A073576 Table[Length[Select[Boole /@ Thread /@ SquareFreeQ /@ IntegerPartitions[n], FreeQ[#, 0] &]], {n, 48}] (* _Jayanta Basu_, Jul 02 2013 *)
%t A073576 a[n_] := a[n] = If[n==0, 1, Sum[Sum[d*Abs[MoebiusMu[d]], {d, Divisors[j]}] * a[n-j], {j, 1, n}]/n]; Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Oct 10 2015, after _Alois P. Heinz_ *)
%t A073576 nmax = 60; CoefficientList[Series[Exp[Sum[Sum[Abs[MoebiusMu[k]] * x^(j*k) / j, {k, 1, Floor[nmax/j] + 1}], {j, 1, nmax}]], {x, 0, nmax}], x] (* _Vaclav Kotesovec_, Mar 31 2018 *)
%o A073576 (Haskell)
%o A073576 a073576 = p a005117_list where
%o A073576    p _          0 = 1
%o A073576    p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
%o A073576 -- _Reinhard Zumkeller_, Jun 01 2015
%o A073576 (Python)
%o A073576 from functools import lru_cache
%o A073576 from sympy import mobius, divisors
%o A073576 @lru_cache(maxsize=None)
%o A073576 def A073576(n): return sum(sum(d*abs(mobius(d)) for d in divisors(i, generator=True))*A073576(n-i) for i in range(1,n+1))//n if n else 1 # _Chai Wah Wu_, Aug 23 2024
%Y A073576 Cf. A058647.
%Y A073576 Cf. A087188.
%Y A073576 Cf. A225244.
%Y A073576 Cf. A114374.
%K A073576 nonn
%O A073576 0,3
%A A073576 _Vladeta Jovovic_, Aug 27 2002