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

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.

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

Mathematica

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

Prog

(Haskell)
a076399 n = a001222 (a025478 n) * a025479 n
-- Reinhard Zumkeller, Mar 28 2014
(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

Crossrefs

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

Sequence in context: A080771 A025477 A080189 * A360729 A370328 A286602

Adjacent sequences: A076396 A076397 A076398 * A076400 A076401 A076402

Keyword

nonn

Author

Reinhard Zumkeller, Oct 09 2002

Status

approved