A076399 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

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

(list; graph; refs; listen; history; text; internal format)

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

AUTHOR

Reinhard Zumkeller, Oct 09 2002

STATUS

approved