login
Number of prime power divisors of n.
42

%I #62 Sep 08 2022 08:45:06

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

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

%U 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

%N Number of prime power divisors of n.

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

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

%C 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

%C 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

%C Length of n-th row of triangle A210208. - _Reinhard Zumkeller_, Mar 18 2012

%C 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

%H Reinhard Zumkeller, <a href="/A073093/b073093.txt">Table of n, a(n) for n = 1..10000</a>

%H T. M. Apostol, <a href="http://dx.doi.org/10.1090/S0002-9939-1970-0251010-X">Resultants of Cyclotomic Polynomials</a>, Proc. Amer. Math. Soc. 24, 457-462, 1970.

%H T. M. Apostol, <a href="https://doi.org/10.1090/S0025-5718-1975-0366801-7">The Resultant of the Cyclotomic Polynomials Fm(ax) and Fn(bx)</a>, Math. Comput. 29, 1-6, 1975.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CyclotomicPolynomial.html">Cyclotomic Polynomial</a>

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

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

%F a(n) = if n=1 then 1 else a(A032742(n)) + 1. - _Reinhard Zumkeller_, Sep 24 2009

%F a(n) = max { a(d) ; d<n and d|n } + 1, if n > 1. - _David W. Wilson_, Dec 08 2010

%F a(n) = Sum_{k = 1 .. A001221(n)} A010055(A027750(n,k)). - _Reinhard Zumkeller_, Mar 18 2012

%F 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

%p seq(numtheory:-bigomega(n)+1, n=1..1000); # _Robert Israel_, Sep 06 2015

%t f[n_] := Plus @@ Flatten[ Table[1, {#[[2]]}] & /@ FactorInteger[n]]; Table[ f[2n], {n, 105}] (* _Robert G. Wilson v_, Dec 23 2004 *)

%t A001221[n_] := (Length[ FactorInteger[n]]); SetAttributes[A001221, Listable]; A073093[n_]:=Length[Select[A001221[Divisors[n]], # == 1 &]]; (* _Enrique Pérez Herrero_, Nov 05 2009 *)

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

%o (PARI) A073093(n)=bigomega(n)+1 \\ _M. F. Hasler_, Dec 08 2010

%o (MuPAD) numlib::Omega (2*n)$ n=1..105 // _Zerinvary Lajos_, May 13 2008

%o (Haskell)

%o a073093 = length . a210208_row -- _Reinhard Zumkeller_, Mar 18 2012

%o (Magma) [n eq 1 select 1 else &+[p[2]: p in Factorization(n)]+1: n in [1..100]]; // _Vincenzo Librandi_, Jan 06 2017

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

%K nonn,easy

%O 1,2

%A _Reinhard Zumkeller_, Aug 24 2002