A050361 Number of factorizations into distinct prime powers greater than 1.

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

Offset: 1

Author

Christian G. Bower, Oct 15 1999

Keywords

• nonn
• easy
• mult

Comments

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

The number of unordered factorizations of n into 1 and exponentially odd prime powers, i.e., p^e where p is a prime and e is odd (A246551). - Amiram Eldar, Jun 12 2025

Examples

			From _Gus Wiseman_, Jul 30 2022: (Start)
The A000688(216) = 9 factorizations of 216 into prime powers are:
  (2*2*2*3*3*3)
  (2*2*2*3*9)
  (2*2*2*27)
  (2*3*3*3*4)
  (2*3*4*9)
  (2*4*27)
  (3*3*3*8)
  (3*8*9)
  (8*27)
Of these, the a(216) = 4 strict cases are:
  (2*3*4*9)
  (2*4*27)
  (3*8*9)
  (8*27)
(End)
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..100000 (first 10000 terms from Reinhard Zumkeller)
• Index entries for sequences computed from exponents in factorization of n.

Crossrefs

Cf. A000009, A050360, A050362, A050363, A050364, A101296, A246551.

Cf. A124010.

This is the strict case of A000688.

Positions of 1's are A004709, complement A046099.

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

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

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

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

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

A001222 counts prime-power divisors.

A005117 lists all squarefree numbers.

A034699 gives maximal prime-power divisor.

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

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

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

Programs

Haskell

a050361 = product . map a000009 . a124010_row
-- Reinhard Zumkeller, Aug 28 2014

Maple

A050361 := proc(n)
    local a,f;
    if n = 1 then
        1;
    else
        a := 1 ;
        for f in ifactors(n)[2] do
            a := a*A000009(op(2,f)) ;
        end do:
    end if;
end proc: # R. J. Mathar, May 25 2017

Mathematica

Table[Times @@ PartitionsQ[Last /@ FactorInteger[n]], {n, 99}] (* Arkadiusz Wesolowski, Feb 27 2017 *)

PARI

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));
A050361(n) = factorback(apply(A000009,factor(n)[,2])); \\ Antti Karttunen, Nov 17 2019

Formula

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

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

a(A002110(k))=1.

a(n) = A050362(A101296(n)). - R. J. Mathar, May 26 2017

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