login
Inverse Moebius transform of A000688, the number of factorizations of n into prime powers greater than 1.
2

%I #34 Aug 21 2021 05:31:40

%S 1,2,2,4,2,4,2,7,4,4,2,8,2,4,4,12,2,8,2,8,4,4,2,14,4,4,7,8,2,8,2,19,4,

%T 4,4,16,2,4,4,14,2,8,2,8,8,4,2,24,4,8,4,8,2,14,4,14,4,4,2,16,2,4,8,30,

%U 4,8,2,8,4,8,2,28,2,4,8,8,4,8,2,24,12,4,2,16,4,4,4,14,2,16

%N Inverse Moebius transform of A000688, the number of factorizations of n into prime powers greater than 1.

%H Alois P. Heinz, <a href="/A188581/b188581.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = Sum_{d | n} A000688(d).

%F Multiplicative with a(p^e) = A000070(e). - _Amiram Eldar_, Sep 09 2020

%F Dirichlet g.f.: zeta(s)^2 * Product_{k>=2} zeta(k*s). - _Ilya Gutkovskiy_, Nov 03 2020

%F Sum_{k=1..n} a(k) ~ n*((log(n) + 2*gamma - 1)*f(1) + f'(1)), where f(1) = Product_{k>=2} zeta(k) = A021002 = 2.1955691982567064617939..., f'(1) = f(1) * Sum_{k>=2} k*zeta'(k)/zeta(k) = -5.0385164470942955610707128990779476296197... and gamma is the Euler-Mascheroni constant A001620. - _Vaclav Kotesovec_, Aug 21 2021

%e For n=8; the divisors of 8 are 1,2,4,8. There are 1,1,2,3 abelian groups of these orders respectively, so a(n) = 1+1+2+3 = 7.

%p with(combinat): with(numtheory):

%p a:= n-> add(mul(numbpart(i[2]), i=ifactors(d)[2]), d=divisors(n)):

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Apr 08 2011

%t InverseMobiusTransform[a_List] := Module[{n = Length[a], b}, b = Table[0, {i, n}]; Do[b[[i]] = Plus @@ a[[Divisors[i]]], {i, n}]; b]; A688[n_] := Times @@ PartitionsP /@ Last /@ FactorInteger@n; InverseMobiusTransform[Array[A688, 100]] (* _T. D. Noe_, Apr 07 2011 *)

%t f[0] = 1; f[e_] := f[e] = f[e - 1] + PartitionsP[e]; a[1] = 1; a[n_] := Times @@ (f[Last[#]] & /@ FactorInteger[n]); Array[a, 100] (* _Amiram Eldar_, Sep 09 2020 *)

%o (GAP)trf:=function ( f, x ) # the Dirichlet convolution 1 * f

%o local d;

%o d := DivisorsInt( x );

%o return Sum( d, function ( i )

%o return f( i );

%o end );

%o end;

%o nra:=function ( x ) # the number of Abelian Groups of order(n)

%o local pp, ll;

%o pp := PrimePowersInt( x );

%o ll := [ 1 .. Size( pp ) / 2 ];

%o return Product( List( 2 * ll, function ( i )

%o return NrPartitions( pp[i] );

%o end ) );

%o end;

%o a:=function ( n )

%o return trf( nra, n );

%o end;

%o (PARI)

%o A000688(n)={local(f); f=factor(n); prod(i=1, matsize(f)[1], numbpart(f[i, 2]))}

%o A188581(n)=sumdiv(n,d,A000688(d))

%o r=vector(66,n,A188581(n)) /* show terms */ /* _Joerg Arndt_, Apr 08 2011 */

%Y Cf. A000688, A000070.

%K nonn,easy,mult

%O 1,2

%A _Marc Bogaerts_, Apr 04 2011