Number-theoretic functions which are equivalent to number of divisors (Q1064776)

Let d(n) denote the number of positive integral divisors of n. In this paper we show that the Möbius function, \(\mu\) (N), can be computed by a single call to an oracle for d(n). We also show that any function that depends solely on the exponents in the prime factorization of N can be computed by at most \(\log_ 2N\) calls to an oracle for d(n).