cp's OEIS Frontend

A188585 Moebius inversion of sequence A000688, the number of factorizations of n into prime powers greater than 1.

%I A188585 #47 Jun 10 2025 13:53:28
%S A188585 1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,2,0,0,
%T A188585 0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,
%U A188585 0,0,0,1,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0
%N A188585 Moebius inversion of sequence A000688, the number of factorizations of n into prime powers greater than 1.
%C A188585 Dirichlet convolution product of A000688 with the Moebius function.
%C A188585 It appears that a(n) is nonzero for n in A001694, the powerful numbers. - _T. D. Noe_, Apr 06 2011 [This is correct: a(n) > 0 if and only if n is in A001694. - _Amiram Eldar_, Jun 10 2025]
%C A188585 There is a similar sequence defined by b(n) = Product_{i} floor(e(i)/2) where n = Product_{p} p(i)^e(i) is the usual prime factorization, which differs from a(n) at n = 64, 128, 256, 512, 576, 729,.... - _R. J. Mathar_, Sep 18 2012 [This sequence is A365550. - _Amiram Eldar_, Jun 10 2025]
%C A188585 The number of unordered factorizations of n into 1 and prime powers p^e where p is prime and e >= 2 (A025475). - _Amiram Eldar_, Jun 10 2025
%H A188585 Charles R Greathouse IV, <a href="/A188585/b188585.txt">Table of n, a(n) for n = 1..10000</a>
%F A188585 a(n) = Sum_{d|n} A008683(n/d) * A000688(d).
%F A188585 Dirichlet g.f.: Product_{k>=2} zeta(k*s). - _Ilya Gutkovskiy_, Nov 03 2020
%F A188585 Sum_{k=1..n} a(k) ~ c * sqrt(n), where c = Product_{k>=3} zeta(k/2) = 10.0301441966843566206076085895839492473559217336... - _Vaclav Kotesovec_, Apr 22 2025
%F A188585 Multiplicative with a(p^e) = A002865(e). - _Amiram Eldar_, Jun 10 2025
%p A188585 with(numtheory): with(combinat):
%p A188585 a:= n-> add(mobius(n/d) *mul(numbpart(i[2]),
%p A188585         i=ifactors(d)[2]), d=divisors(n)):
%p A188585 seq(a(n), n=1..110);  # _Alois P. Heinz_, Apr 07 2011
%t A188585 MobiusTransform[a_List] := Module[{n = Length[a], b}, b = Table[0, {i, n}];Do[b[[i]] = Plus @@ (MoebiusMu[i/Divisors[i]] a[[Divisors[i]]]), {i, n}]; b]; A688[n_] := Times @@ PartitionsP /@ Last /@ FactorInteger@n; MobiusTransform[Array[A688, 100]] (* _T. D. Noe_, Apr 06 2011 *)
%t A188585 f[p_, e_] := PartitionsP[e] - PartitionsP[e-1]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Jun 10 2025 *)
%o A188585 (GAP)
%o A188585 mtrf:=function ( f, x )     # the Moebius inversion formula
%o A188585     local  d;
%o A188585     d := DivisorsInt( x );
%o A188585     return Sum( d, function ( i )
%o A188585             return f( i ) * MoebiusMu( (x / i) );
%o A188585         end );
%o A188585 end;
%o A188585 nra:=function ( x )         # the number of Abelian groups of order x
%o A188585     local  pp, ll;
%o A188585     pp := PrimePowersInt( x );
%o A188585     ll := [ 1 .. Size( pp ) / 2 ];
%o A188585     return Product( List( 2 * ll, function ( i )
%o A188585               return NrPartitions( pp[i] );
%o A188585           end ) );
%o A188585 end;
%o A188585 a:=function ( n )
%o A188585     return mtrf( nra, n );
%o A188585 end;
%o A188585 (PARI) a(n) = vecprod(apply(x -> numbpart(x)-numbpart(x-1), factor(n)[, 2])); \\ _Amiram Eldar_, Jun 10 2025
%o A188585 (Python)
%o A188585 from math import prod
%o A188585 from sympy import partition, factorint
%o A188585 def A188585(n): return prod(partition(e)-partition(e-1) for e in factorint(n).values()) # _Chai Wah Wu_, Jun 10 2025
%Y A188585 Cf. A000688, A001694, A002865, A008683, A025475, A365550.
%K A188585 nonn,mult,easy
%O A188585 1,16
%A A188585 _Marc Bogaerts_, Apr 04 2011