In number theory and computability theory, subfields of mathematics, a number-theoretic function is any function whose domain is the set of natural numbers.^[1] Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ... Computability theory is the branch of theoretical computer science that studies which problems are computationally solvable using different models of computation. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Partial plot of a function f. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...

A number-theoretic function whose range is included in the set of complex numbers is called an arithmetical function.^[2] The most important arithmetic functions are the additive and the multiplicative ones. An important operation on arithmetic functions is the Dirichlet convolution. Arithmetic functions may be studied with Bell series. In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = −1. ... In number theory, an additive function is an arithmetic function f(n) of the positive integer n such that whenever a and b are coprime we have: f(ab) = f(a) + f(b). ... In number theory, a multiplicative function is an arithmetic function f(n) of the positive integer n with the property that f(1) = 1 and whenever a and b are coprime, then f(ab) = f(a) f(b). ... In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is of importance in number theory. ... In mathematics, the Bell series is a formal power series used to study properties of multiplicative arithmetical functions. ...

Examples

The articles on additive and multiplicative functions contain several examples of arithmetic functions. Here are some examples that are neither additive nor multiplicative:

• r₄(n) - the number of ways that n can be expressed as the sum of four squares of nonnegative integers, where we distinguish between different orders of the summands. For example:

1 = 1²+0²+0²+0² = 0²+1²+0²+0² = 0²+0²+1²+0² = 0²+0²+0²+1²,

hence r₄(1)=4.

• P(n), the Partition function - the number of representations of n as a sum of positive integers, where we don't distinguish between different orders of the summands. For instance: P(2 · 5) = P(10) = 42 and P(2)P(5) = 2 · 7 = 14 ≠ 42.

• π (n), the Prime counting function - the number of primes less than or equal to a given number n. We have π(1) = 0 and π(10) = 4 (the primes below 10 being 2, 3, 5, and 7).

• ω (n), the number of distinct primes dividing given number n. We have ω(1) = 0 and ω(20) = 2 (the distinct primes dividing 20 being 2 and 5).

• Λ(n), the von Mangoldt function which is defined to be ln(p) if n is an integer power of a prime p and 0 for all other n.

It has been suggested that this article or section be merged with Integer partition. ... In number theory, the prime number theorem (PNT) describes the approximate, asymptotic distribution of the prime numbers. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... The von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. ...

Footnotes

1. ^ William J. LeVeque (1996). Fundamentals of Number Theory. Courier Dover Publications. ISBN 0486689069. 
   Elliott Mendelson (1987). Introduction to Mathematical Logic. CRC Press. ISBN 0412808307. 
2. ^ Allan M. Kirch (1974). Elementary Number Theory: A Computer Approach. Intext Educational Publishers. ISBN 0700224564. 
   R. Sivaramakrishnan and Sivaramakrishnan Sivaramakrishnan (1988). Classical Theory of Arithmetic Functions. Marcel Dekker. ISBN 0824780817.