Prove that the characteristic function of primes (i.e. $1$ if the number is prime, $0$ otherwise) is the Möbius transform of $\omega(n)$ (the number of distinct prime factors), number of distinct primes dividing $n$.

Thank you very much.

  • 2
    $\begingroup$ Do you know what the mobius transform is? Do you know about Mobius inversion? $\endgroup$ – Gerry Myerson Jul 28 '13 at 9:10

Let the prime detecting function is $f(n)=1 \ \text{if $n$ is prime}\\f(n)=0 \ \text{otherwise}$.

$$\omega(n)=\displaystyle\sum_{p|n}1=\displaystyle\sum_{d|n}f(d) \implies f(n)= \displaystyle\sum_{d|n}\mu\left({n \over d}\right)\omega(d)=(\mu \star \omega) (n).$$

$*$ is Dirichlet Convolution.


In case of the The first few values of $\omega(n)$ for $n=1,2,\cdots$ are $0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, ...$ see:

Sloane, N. J. A. Sequences A001221/M0056, A013939, A027748, A085548, and A091588 in "The On-Line Encyclopedia of Integer Sequences."

Abramowitz, M. and Stegun, I. A. (Eds.). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 844, 1972.

Kac, M. Statistical Independence in Probability, Analysis and Number Theory. Washington, DC: Math. Assoc. Amer., p. 64, 1959.

This sequence is given by the inverse Möbius transform (not the Möbius transform) of ${\chi_P(n)}$, where $\chi_P$ is the characteristic function of the prime numbers.

If there goes your question please see answer to here:

Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995. page 22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.