cp's OEIS Frontend

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

%I A076398 #20 Feb 16 2025 08:32:47
%S A076398 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,
%T A076398 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,
%U A076398 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
%N A076398 Number of distinct prime factors of n-th perfect power.
%H A076398 Reinhard Zumkeller, <a href="/A076398/b076398.txt">Table of n, a(n) for n = 1..10000</a>
%H A076398 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PerfectPower.html">Perfect Powers</a>.
%H A076398 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DistinctPrimeFactors.html">Distinct Prime Factors</a>.
%F A076398 a(n) = A001221(A001597(n)).
%F A076398 a(n) = A001221(A025478(n)).
%t A076398 ppQ[1] = True; ppQ[n_] := GCD @@ FactorInteger[n][[All, 2]] > 1; PrimeNu /@ Select[Range[10^4], ppQ] (* _Jean-François Alcover_, Jul 15 2017 *)
%o A076398 (Haskell)
%o A076398 a076398 = a001221 . a025478  -- _Reinhard Zumkeller_, Mar 28 2014
%o A076398 (PARI) lista(nn) = for(n=1, nn, if ((n==1) || ispower(n), print1(omega(n), ", "))); \\ _Michel Marcus_, Jul 15 2017
%o A076398 (Python)
%o A076398 from sympy import mobius, integer_nthroot, primenu
%o A076398 def A076398(n):
%o A076398     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 A076398     kmin, kmax = 1,2
%o A076398     while f(kmax) >= kmax:
%o A076398         kmax <<= 1
%o A076398     while True:
%o A076398         kmid = kmax+kmin>>1
%o A076398         if f(kmid) < kmid:
%o A076398             kmax = kmid
%o A076398         else:
%o A076398             kmin = kmid
%o A076398         if kmax-kmin <= 1:
%o A076398             break
%o A076398     return int(primenu(kmax)) # _Chai Wah Wu_, Aug 14 2024
%Y A076398 Cf. A001221, A001597, A025478, A076399, A076400.
%K A076398 nonn
%O A076398 1,9
%A A076398 _Reinhard Zumkeller_, Oct 09 2002