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

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 k<n such that the resultant of the k-th cyclotomic polynomial and the n-th cyclotomic polynomial is not 1. It is well known that if (k,n)=1, res(polcyclo(n),polcyclo(k))=1. - Benoit 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

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<n and d|n } + 1, if n > 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

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

Prog

(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
(MuPAD) numlib::Omega (2*n)$ n=1..105 // Zerinvary Lajos, May 13 2008
(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

Crossrefs

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

Sequence in context: A299990 A175193 A353861 * A326196 A222084 A327394

Adjacent sequences: A073090 A073091 A073092 * A073094 A073095 A073096

Keyword

nonn,easy

Author

Reinhard Zumkeller, Aug 24 2002

Status

approved