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

Links

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

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

Example

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.

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

Prog

(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;
(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 */

Crossrefs

Cf. A000688, A000070.

Sequence in context: A101113 A055155 A085191 * A347958 A318316 A328721

Adjacent sequences: A188578 A188579 A188580 * A188582 A188583 A188584

Keyword

nonn,easy,mult

Author

Marc Bogaerts, Apr 04 2011

Status

approved