A076400 Number of divisors of n-th perfect power.

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

Offset: 1

Author

Reinhard Zumkeller, Oct 09 2002

Keywords

• nonn

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Perfect Powers.
• Eric Weisstein's World of Mathematics, Divisor Function.

Crossrefs

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

Programs

Mathematica

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

Python

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

Formula

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