Arithmetic function

From Wikipedia, the free encyclopedia

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]

A number-theoretic function whose range is included in the set of complex numbers is called an arithmetical function or arithmetic 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.

[edit] Examples

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

  • r4(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 = 12+02+02+02 = 02+12+02+02 = 02+02+12+02 = 02+02+02+12,
hence r4(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.

[edit] 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.