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

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

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.

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

Example

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)

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

Prog

(Haskell)
a050361 = product . map a000009 . a124010_row
-- Reinhard Zumkeller, Aug 28 2014
(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

Crossrefs

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

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.

Sequence in context: A061704 A325837 A366902 * A072911 A325988 A328856

Adjacent sequences: A050358 A050359 A050360 * A050362 A050363 A050364

Keyword

nonn,easy,mult

Author

Christian G. Bower, Oct 15 1999

Status

approved