A076398 Number of distinct prime factors of n-th perfect power.

0, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 2, 2, 2, 1, 1, 2, 2, 2, 1, 2, 3, 1, 2, 2, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 2, 1, 2, 2, 1, 2, 2, 2, 2, 1, 3, 1, 2, 2, 1, 2, 3, 1, 2, 2, 3, 1, 1, 2, 1, 2, 2, 2, 2, 2, 3, 1, 2, 1, 2, 1, 1, 3

Offset: 1

Author

Reinhard Zumkeller, Oct 09 2002

Keywords

• nonn

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Perfect Powers.
• Eric Weisstein's World of Mathematics, Distinct Prime Factors.

Crossrefs

Cf. A001221, A001597, A025478, A076399, A076400.

Programs

Haskell

a076398 = a001221 . a025478  -- Reinhard Zumkeller, Mar 28 2014

Mathematica

ppQ[1] = True; ppQ[n_] := GCD @@ FactorInteger[n][[All, 2]] > 1; PrimeNu /@ Select[Range[10^4], ppQ] (* Jean-François Alcover, Jul 15 2017 *)

PARI

lista(nn) = for(n=1, nn, if ((n==1) || ispower(n), print1(omega(n), ", "))); \\ Michel Marcus, Jul 15 2017

Python

from sympy import mobius, integer_nthroot, primenu
def A076398(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(primenu(kmax)) # Chai Wah Wu, Aug 14 2024

Formula

a(n) = A001221(A001597(n)).

a(n) = A001221(A025478(n)).