login
Number of factorizations into distinct prime powers greater than 1.
23

%I #36 Oct 03 2023 13:14:24

%S 1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,2,1,1,2,1,1,1,1,3,1,1,

%T 1,1,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,1,1,2,1,2,1,1,1,1,1,1,1,4,1,1,1,1,

%U 1,1,1,2,1,1,1,1,1,1,1,2,2,1,1,1,1,1,1,2,1,1,1,1,1,1,1,3,1,1,1

%N Number of factorizations into distinct prime powers greater than 1.

%C a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3,1).

%H Antti Karttunen, <a href="/A050361/b050361.txt">Table of n, a(n) for n = 1..100000</a> (first 10000 terms from Reinhard Zumkeller)

%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>.

%F Dirichlet g.f.: Product_{n is a prime power >1}(1 + 1/n^s).

%F Multiplicative with a(p^e) = A000009(e).

%F a(A002110(k))=1.

%F a(n) = A050362(A101296(n)). - _R. J. Mathar_, May 26 2017

%F Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = Product_{p prime} f(1/p) = 1.26020571070524171076..., where f(x) = (1-x) * Product_{k>=1} (1 + x^k). - _Amiram Eldar_, Oct 03 2023

%e From _Gus Wiseman_, Jul 30 2022: (Start)

%e The A000688(216) = 9 factorizations of 216 into prime powers are:

%e (2*2*2*3*3*3)

%e (2*2*2*3*9)

%e (2*2*2*27)

%e (2*3*3*3*4)

%e (2*3*4*9)

%e (2*4*27)

%e (3*3*3*8)

%e (3*8*9)

%e (8*27)

%e Of these, the a(216) = 4 strict cases are:

%e (2*3*4*9)

%e (2*4*27)

%e (3*8*9)

%e (8*27)

%e (End)

%p A050361 := proc(n)

%p local a,f;

%p if n = 1 then

%p 1;

%p else

%p a := 1 ;

%p for f in ifactors(n)[2] do

%p a := a*A000009(op(2,f)) ;

%p end do:

%p end if;

%p end proc: # _R. J. Mathar_, May 25 2017

%t Table[Times @@ PartitionsQ[Last /@ FactorInteger[n]], {n, 99}] (* _Arkadiusz Wesolowski_, Feb 27 2017 *)

%o (Haskell)

%o a050361 = product . map a000009 . a124010_row

%o -- _Reinhard Zumkeller_, Aug 28 2014

%o (PARI)

%o A000009(n,k=(n-!(n%2))) = if(!n,1,my(s=0); while(k >= 1, if(k<=n, s += A000009(n-k,k)); k -= 2); (s));

%o A050361(n) = factorback(apply(A000009,factor(n)[,2])); \\ _Antti Karttunen_, Nov 17 2019

%Y Cf. A000009, A050360, A050362, A050363, A050364, A101296.

%Y Cf. A124010.

%Y This is the strict case of A000688.

%Y Positions of 1's are A004709, complement A046099.

%Y The case of primes (instead of prime-powers) is A008966, non-strict A000012.

%Y The non-strict additive version allowing 1's A023893, ranked by A302492.

%Y The non-strict additive version is A023894, ranked by A355743.

%Y The additive version (partitions) is A054685, ranked by A356065.

%Y The additive version allowing 1's is A106244, ranked by A302496.

%Y A001222 counts prime-power divisors.

%Y A005117 lists all squarefree numbers.

%Y A034699 gives maximal prime-power divisor.

%Y A246655 lists all prime-powers (A000961 includes 1), towers A164336.

%Y A296131 counts twice-factorizations of type PQR, non-strict A295935.

%Y Cf. A001970, A002110, A025487, A055887, A063834, A076610, A085970, A279786, A302590, A302601, A354911, A355742.

%K nonn,easy,mult

%O 1,8

%A _Christian G. Bower_, Oct 15 1999