A073093 Number of prime power divisors of n.

1, 2, 2, 3, 2, 3, 2, 4, 3, 3, 2, 4, 2, 3, 3, 5, 2, 4, 2, 4, 3, 3, 2, 5, 3, 3, 4, 4, 2, 4, 2, 6, 3, 3, 3, 5, 2, 3, 3, 5, 2, 4, 2, 4, 4, 3, 2, 6, 3, 4, 3, 4, 2, 5, 3, 5, 3, 3, 2, 5, 2, 3, 4, 7, 3, 4, 2, 4, 3, 4, 2, 6, 2, 3, 4, 4, 3, 4, 2, 6, 5, 3, 2, 5, 3, 3, 3, 5, 2, 5, 3, 4, 3, 3, 3, 7, 2, 4, 4, 5, 2, 4, 2, 5, 4

Offset: 1

Author

Reinhard Zumkeller, Aug 24 2002

Keywords

• nonn
• easy

Comments

Also, number of prime divisors of 2n (counted with multiplicity).

A001221(n) < a(n) <= A000005(n) for all n; a(n)=A001221(n)+1 iff n is squarefree (A005117); a(n)=A000005(n) iff n is a prime power (A000961).

a(n) is also the number of kBenoit Cloitre, Oct 13 2002

a(n) is also 1 + the number of divisors of n with omega(d)=1, where omega is A001221. - Enrique Pérez Herrero, Nov 05 2009

Length of n-th row of triangle A210208. - Reinhard Zumkeller, Mar 18 2012

a(n) depends only on the prime signature of n with a(A025487(n)) = 1, 2, 3, 3, 4, 4, 5, 5, 4, 6, 5, 6, 5, 7, 6, 7 ,.. = A036041(n)+1; (n>=1). - R. J. Mathar, May 28 2017

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• T. M. Apostol, Resultants of Cyclotomic Polynomials, Proc. Amer. Math. Soc. 24, 457-462, 1970.
• T. M. Apostol, The Resultant of the Cyclotomic Polynomials Fm(ax) and Fn(bx), Math. Comput. 29, 1-6, 1975.
• Eric Weisstein's World of Mathematics, Cyclotomic Polynomial

Crossrefs

Cf. A000961, A023888, A054372. Bisection of A001222.

Programs

Haskell

a073093 = length . a210208_row  -- Reinhard Zumkeller, Mar 18 2012

Magma

[n eq 1 select 1 else &+[p[2]: p in Factorization(n)]+1: n in [1..100]]; // Vincenzo Librandi, Jan 06 2017

Maple

seq(numtheory:-bigomega(n)+1, n=1..1000); # Robert Israel, Sep 06 2015

Mathematica

f[n_] := Plus @@ Flatten[ Table[1, {#[[2]]}] & /@ FactorInteger[n]]; Table[ f[2n], {n, 105}] (* Robert G. Wilson v, Dec 23 2004 *)
A001221[n_] := (Length[ FactorInteger[n]]); SetAttributes[A001221, Listable]; A073093[n_]:=Length[Select[A001221[Divisors[n]], # == 1 &]]; (* Enrique Pérez Herrero, Nov 05 2009 *)
PrimeOmega[Range[100]] + 1 (* Paolo Xausa, Nov 23 2024 *)

MuPAD

numlib::Omega (2*n)$ n=1..105 // Zerinvary Lajos, May 13 2008

PARI

a(n)=sum(k=1,n,if(1-polresultant(polcyclo(n),polcyclo(k)),1,0))

PARI

A073093(n)=bigomega(n)+1   \\ M. F. Hasler, Dec 08 2010

Formula

If n = Product (p_j^k_j), a(n) = 1 + Sum (k_j).

a(n) = bigomega(n)+1 = A001222(n)+1 = A001222(2*n).

a(n) = if n=1 then 1 else a(A032742(n)) + 1. - Reinhard Zumkeller, Sep 24 2009

a(n) = max { a(d) ; d 1. - David W. Wilson, Dec 08 2010

a(n) = Sum_{k = 1 .. A001221(n)} A010055(A027750(n,k)). - Reinhard Zumkeller, Mar 18 2012

G.f.: x/(1 - x) + Sum_{k>=2} floor(1/omega(k))*x^k/(1 - x^k), where omega(k) is the number of distinct prime factors (A001221). - Ilya Gutkovskiy, Jan 04 2017