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

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, 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, 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

Offset: 1

Author

Marc Bogaerts, Apr 04 2011

Keywords

• nonn
• easy
• mult

Examples

			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.
		

Links

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

Crossrefs

Cf. A000688, A000070.

Programs

GAP

trf:=function ( f, x )  # the Dirichlet convolution 1 * f
    local  d;
    d := DivisorsInt( x );
    return Sum( d, function ( i )
            return f( i );
        end );
end;
nra:=function ( x )     # the number of Abelian Groups of order(n)
    local  pp, ll;
    pp := PrimePowersInt( x );
    ll := [ 1 .. Size( pp ) / 2 ];
    return Product( List( 2 * ll, function ( i )
              return NrPartitions( pp[i] );
          end ) );
end;
a:=function ( n )
    return trf( nra, n );
end;

Maple

with(combinat): with(numtheory):
a:= n-> add(mul(numbpart(i[2]), i=ifactors(d)[2]), d=divisors(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Apr 08 2011

Mathematica

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 *)
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 *)

PARI

A000688(n)={local(f); f=factor(n); prod(i=1, matsize(f)[1], numbpart(f[i, 2]))}
A188581(n)=sumdiv(n,d,A000688(d))
r=vector(66,n,A188581(n)) /* show terms */ /* Joerg Arndt, Apr 08 2011 */

Formula

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

Multiplicative with a(p^e) = A000070(e). - Amiram Eldar, Sep 09 2020

Dirichlet g.f.: zeta(s)^2 * Product_{k>=2} zeta(k*s). - Ilya Gutkovskiy, Nov 03 2020

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