A076400 - OEIS

%I #12 Aug 14 2024 10:04:01

%S 1,3,4,3,5,3,4,6,9,3,7,5,9,3,4,8,15,3,9,16,9,6,9,3,15,4,3,15,9,9,10,3,

%T 21,5,9,7,15,3,27,3,16,11,9,9,9,25,4,3,9,9,21,3,28,27,3,15,15,12,9,8,

%U 4,3,27,5,15,9,15,16,3,21,9,6,21,9,9,16,3,45,3,9,15,13,9,27,3,15,9,27,4

%N Number of divisors of n-th perfect power.

%H Michael De Vlieger, <a href="/A076400/b076400.txt">Table of n, a(n) for n = 1..10000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerfectPower.html">Perfect Powers</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DivisorFunction.html">Divisor Function</a>.

%F a(n) = A000005(A001597(n)).

%t DivisorSigma[0, {1}~Join~Select[Range[5000], GCD @@ FactorInteger[#][[All, -1]] > 1 &]] (* _Michael De Vlieger_, Dec 16 2021 *)

%o (Python)

%o from sympy import mobius, integer_nthroot, divisor_count

%o def A076400(n):

%o     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     kmin, kmax = 1,2

%o     while f(kmax) >= kmax:

%o         kmax <<= 1

%o     while True:

%o         kmid = kmax+kmin>>1

%o         if f(kmid) < kmid:

%o             kmax = kmid

%o         else:

%o             kmin = kmid

%o         if kmax-kmin <= 1:

%o             break

%o     return int(divisor_count(kmax)) # _Chai Wah Wu_, Aug 14 2024

%Y Cf. A000005, A001597, A076398, A076399, A076401.

%K nonn

%O 1,2

%A _Reinhard Zumkeller_, Oct 09 2002