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

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

Offset: 1

Author

Reinhard Zumkeller, Oct 09 2002

Keywords

• nonn

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Rafael Jakimczuk and Matilde Lalín, The Number of Prime Factors on Average in Certain Integer Sequences, Journal of Integer Sequences, Vol. 25 (2022), Article 22.2.3.
• Eric Weisstein's World of Mathematics, Perfect Powers.
• Eric Weisstein's World of Mathematics, Prime Factor.

Crossrefs

Cf. A001222, A025478, A025479, A076398, A076400, A083342.

Programs

Haskell

a076399 n = a001222 (a025478 n) * a025479 n
-- Reinhard Zumkeller, Mar 28 2014

Mathematica

PrimeOmega[Select[Range[10^4], # == 1 || GCD @@ FactorInteger[#][[;; , 2]] > 1 &]] (* Amiram Eldar, Feb 18 2023 *)

PARI

is(n) = n==1 || ispower(n);
apply(bigomega, select(is, [1..5000])) \\ Amiram Eldar, Feb 18 2023

Python

from sympy import mobius, integer_nthroot, primeomega
def A076399(n):
    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())))
    kmin, kmax = 1,2
    while f(kmax) >= kmax:
        kmax <<= 1
    while True:
        kmid = kmax+kmin>>1
        if f(kmid) < kmid:
            kmax = kmid
        else:
            kmin = kmid
        if kmax-kmin <= 1:
            break
    return int(primeomega(kmax)) # Chai Wah Wu, Aug 14 2024

Formula

a(n) = A001222(A001597(n)).

a(n) = A001222(A025478(n))*A025479(n).

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