cp's OEIS Frontend

A076399 Number of prime factors of n-th perfect power (with repetition).

%I A076399 #24 Feb 16 2025 08:32:47
%S A076399 0,2,3,2,4,2,3,5,4,2,6,4,4,2,3,7,6,2,4,6,4,5,8,2,6,3,2,6,4,4,9,2,8,4,
%T A076399 4,6,6,2,6,2,6,10,4,4,4,8,3,2,4,4,8,2,9,6,2,6,6,11,4,7,3,2,10,4,6,4,6,
%U A076399 6,2,8,4,5,8,4,4,6,2,8,2,4,6,12,4,6,2,6,4,6,3,2,10,2,4,6,6,9,4,6,2,10,8
%N A076399 Number of prime factors of n-th perfect power (with repetition).
%H A076399 Reinhard Zumkeller, <a href="/A076399/b076399.txt">Table of n, a(n) for n = 1..10000</a>
%H A076399 Rafael Jakimczuk and Matilde Lalín, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Lalin/lalin2.html">The Number of Prime Factors on Average in Certain Integer Sequences</a>, Journal of Integer Sequences, Vol. 25 (2022), Article 22.2.3.
%H A076399 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PerfectPower.html">Perfect Powers</a>.
%H A076399 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimeFactor.html">Prime Factor</a>.
%F A076399 a(n) = A001222(A001597(n)).
%F A076399 a(n) = A001222(A025478(n))*A025479(n).
%F A076399 Sum_{A001597(k) <= x} a(k) = 2*sqrt(x)*log(log(x)) + 2*(B_2 - log(2))*sqrt(x) + O(sqrt(x)/log(x)), where B_2 = A083342 (Jakimczuk and Lalín, 2022). - _Amiram Eldar_, Feb 18 2023, corrected Sep 21 2024
%t A076399 PrimeOmega[Select[Range[10^4], # == 1 || GCD @@ FactorInteger[#][[;; , 2]] > 1 &]] (* _Amiram Eldar_, Feb 18 2023 *)
%o A076399 (Haskell)
%o A076399 a076399 n = a001222 (a025478 n) * a025479 n
%o A076399 -- _Reinhard Zumkeller_, Mar 28 2014
%o A076399 (PARI) is(n) = n==1 || ispower(n);
%o A076399 apply(bigomega, select(is, [1..5000])) \\ _Amiram Eldar_, Feb 18 2023
%o A076399 (Python)
%o A076399 from sympy import mobius, integer_nthroot, primeomega
%o A076399 def A076399(n):
%o A076399     def f(x): return int(n-2+x+sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
%o A076399     kmin, kmax = 1,2
%o A076399     while f(kmax) >= kmax:
%o A076399         kmax <<= 1
%o A076399     while True:
%o A076399         kmid = kmax+kmin>>1
%o A076399         if f(kmid) < kmid:
%o A076399             kmax = kmid
%o A076399         else:
%o A076399             kmin = kmid
%o A076399         if kmax-kmin <= 1:
%o A076399             break
%o A076399     return int(primeomega(kmax)) # _Chai Wah Wu_, Aug 14 2024
%Y A076399 Cf. A001222, A025478, A025479, A076398, A076400, A083342.
%K A076399 nonn
%O A076399 1,2
%A A076399 _Reinhard Zumkeller_, Oct 09 2002