# The characteristic function of primes and the omega function

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.

• Do you know what the mobius transform is? Do you know about Mobius inversion? – 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.