Number-theoretic functions which are equivalent to number of divisors (Q1064776): Difference between revisions

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).