FazBrowse Wikipedia Viewer | Main Page | |

Viewing: https://en.wikipedia.org/wiki/Arithmetic_function

Arithmetic function

Contents
Ω(n), ω(n), νp(n) – prime power decomposition
φ(n) – Euler totient function
μ(n) – Möbius function
χ(n) – characters
D(n) – Arithmetic derivative
Relations among the functions
Dirichlet convolutions
Divisor sum convolutions
Miscellaneous
First 100 values of some arithmetic functions
References

In number theory, an arithmetic, arithmetical, or number-theoretic function is generally any function whose domain is the set of positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n". There is a larger class of number-theoretic functions that do not fit this definition, for example, the prime-counting functions. This article provides links to functions of both classes.

An example of an arithmetic function is the divisor function whose value at a positive integer n is equal to the number of divisors of n.

Arithmetic functions are often extremely irregular (see table), but some of them have series expansions in terms of Ramanujan's sum.

∏pf(p) mean that the sum or product is over all prime numbers: ∑pkf(pk) and ∑d∣nf(d) and ∏d∣12f(d)=f(1)f(2)f(3)f(4)f(6)f(12).

The notations can be combined: ∑p∣18f(p)=f(2)+f(3), and similarly ∏pk∣24f(pk)=f(2)f(3)f(4)f(8).

Ω(n), ω(n), νp(n) – prime power decomposition

edit

The fundamental theorem of arithmetic states that any positive integer n can be represented uniquely as a product of powers of primes: τ(n)=d(n)=(1+a1)(1+a2)⋯(1+aω(n)).

φ(n) – Euler totient function

edit

φ(n), the Euler totient function, is the number of positive integers not greater than n that are coprime to n. Jk(n)=nk∏p∣n(1−1pk)=nk(p1k−1p1k)(p2k−1p2k)⋯(pω(n)k−1pω(n)k).

μ(n) – Möbius function

edit

μ(n), the Möbius function, is important because of the Möbius inversion formula. See § Dirichlet convolution, below. cq(n)=∑gcd⁡(a,q)=11≤a≤qe2πiaqn.

Even though it is defined as a sum of complex numbers (irrational for most values of q), it is an integer. For a fixed value of n it is multiplicative in q:

If q and r are coprime, then λ(n)=(−1)Ω(n).

χ(n) – characters

edit

All Dirichlet characters χ(n) are completely multiplicative. Two characters have special notations:

The principal character (mod n) is denoted by χ0(a) (or χ1(a)). It is defined as (ap) is the Legendre symbol, defined for all integers a and all odd primes p by ld⁡(n)=D(n)n=∑p primep∣nvp(n)p, where Π(x)=∑pk≤x1k.

ϑ(x) and ψ(x), the Chebyshev functions, are defined as sums of the natural logarithms of the primes not exceeding x. p, in which case it is the natural logarithm of the prime p: aλ(n)≡1(modn) for all a coprime to n. Equivalently, it is the least common multiple of the orders of the elements of the multiplicative group of integers modulo n.

For powers of odd primes and for 2 and 4, λ(n) is equal to the Euler totient function of n; for powers of 2 greater than 4 it is equal to one half of the Euler totient function of n: rk(n)=|{(a1,a2,…,ak):n=a12+a22+⋯+ak2}|

D(n) – Arithmetic derivative

edit

Using the Heaviside notation for the derivative, the arithmetic derivative D(n) is a function such that

A(x):=∑n≤xa(n). A can be regarded as a function of a real variable. Given a positive integer m, A is constant along open intervals m < x < m + 1, and has a jump discontinuity at each integer for which a(m) ≠ 0.

Since such functions are often represented by series and integrals, to achieve pointwise convergence it is usual to define the value at the discontinuities as the average of the values to the left and right: lim supn→∞log⁡d(n)log⁡log⁡nlog⁡n=log⁡2 Fa(s):=∑n=1∞a(n)ns. Fa(s) is called a generating function of a(n). The simplest such series, corresponding to the constant function a(n) = 1 for all n, is ζ(s) the Riemann zeta function.

The generating function of the Möbius function is the inverse of the zeta function: 1."}}'>ζ(s)∑n=1∞μ(n)ns=1,ℜs>1.

Consider two arithmetic functions a and b and their respective generating functions Fa(s) and Fb(s). The product Fa(s)Fb(s) can be computed as follows: Fc(s)=Fa(s)Fb(s).

This function c is called the Dirichlet convolution of a and b, and is denoted by f(n)=∑d∣nμ(nd)g(d).

If f is multiplicative, then so is g. If f is completely multiplicative, then g is multiplicative, but may or may not be completely multiplicative.

Relations among the functions
edit

There are a great many formulas connecting arithmetical functions with each other and with the functions of analysis, especially powers, roots, and the exponential and log functions. The page divisor sum identities contains many more generalized and related examples of identities involving arithmetic functions.

Here are a few examples:

Dirichlet convolutions
edit

φ(n)=∑δ∣nμ(nδ)δ=n∑δ∣nμ(δ)δ. Möbius inversion

∑δ∣nδsJr(δ)Js(nδ)=Jr+s(n)

|μ(n)|=∑δ∣nμ(nδ)2ω(δ). Möbius inversion

∑δ∣nd(δ2)=d2(n).

∑δ∣nλ(δ)={1 if n is a square 0 if n is not square. where λ is the Liouville function.

k≥4,rk(n)>0. (Lagrange's four-square theorem).

r4(n)=8∑4∤dd∣nd=8(2+(−1)n)∑2∤dd∣nd={8σ(n)if n is odd 24σ(n2ν)if n is even , where 2(''n'')"}},"i":0}}]}'/>ν = ν2(n). σk(n) as σk(n), and if n is even it is the sum of the kth powers of the even divisors of n minus the sum of the kth powers of the odd divisors of n.

r24(n)=16691σ11∗(n)+128691{(−1)n−1259τ(n)−512τ(n2)}

Divisor sum convolutions

edit

Here "convolution" does not mean "Dirichlet convolution" but instead refers to the formula for the coefficients of the product of two power series:

These formulas may be proved analytically (see Eisenstein series) or by elementary methods.

σ7(n)=120{21(2n−1)σ5(n)−σ1(n)+504∑0<k<nσ1(k)σ5(n−k)}=σ3(n)+120∑0<k<nσ3(k)σ3(n−k).

(a2)={0 if a is even(−1)a2−18 if a is odd.

Then if D < −4 is a fundamental discriminant Hn=1+12+13+⋯+1n be the nth harmonic number. Then

Π(x)=∑n≤xΛ(n)log⁡n.

∑gcd⁡(k1,k2,…,ks,n)=11≤k1,k2,…,ks≤ngcd⁡(k1−a1,k2−a2,…,ks−as,n)s=Js(n)d(n), where a1, a2, ..., as are integers, gcd(a1, a2, ..., as, n) = 1.

László Fejes Tóth ∗ stands for Dirichlet convolution.

Miscellaneous

edit

Let m and n be distinct, odd, and positive. Then the Jacobi symbol satisfies the law of quadratic reciprocity: 2ω(n)≤d(n)≤2Ω(n).

ϕ(q)=∑δ∣qμ(qδ)δ.

∑δ∣nd3(δ)=(∑δ∣nd(δ))2. Compare this with 3 + 23 + 33 + ... + ''n''3 = (1 + 2 + 3 + ... + ''n'')2"}},"i":0}}]}'/>1 + 2 + 3 + ... + n = (1 + 2 + 3 + ... + n)

τ(u)τ(v)=∑δ∣gcd⁡(u,v)δ11τ(uvδ2), where τ(n) is Ramanujan's function.

First 100 values of some arithmetic functions

edit

factorization

φ(n)

ω(n)

Ω(n)

λ(n)

μ(n)

Λ(n)

π(n)

σ0(n)

σ1(n)

σ2(n)

r2(n)

r3(n)

r4(n)

−1

0.69

−1

1.10

0.69

−1

1.61

2 · 3

−1

1.95

−1

0.69

1.10

104

2 · 5

130

144

−1

2.40

122

2 · 3

−1

210

−1

2.56

170

112

2 · 7

250

192

3 · 5

260

192

0.69

341

−1

2.83

290

144

2 · 3

−1

455

312

−1

2.94

362

160

2 · 5

−1

546

144

3 · 7

500

256

2 · 11

610

288

−1

3.14

530

192

2 · 3

850

1.61

651

248

2 · 13

850

336

−1

1.10

820

320

2 · 7

−1

1050

192

−1

3.37

842

240

2 · 3 · 5

−1

1300

576

−1

3.43

962

256

−1

0.69

1365

3 · 11

1220

384

2 · 17

1450

432

5 · 7

1300

384

2 · 3

1911

312

−1

3.61

1370

304

2 · 19

1810

480

3 · 13

1700

448

2 · 5

2210

144

−1

3.71

1682

336

2 · 3 · 7

−1

2500

768

−1

3.76

1850

352

2 · 11

−1

2562

288

3 · 5

−1

2366

624

2 · 23

2650

576

−1

3.85

2210

384

2 · 3

−1

124

3410

1.95

2451

456

2 · 5

−1

3255

744

3 · 17

2900

576

2 · 13

−1

3570

336

−1

3.97

2810

432

2 · 3

120

4100

960

5 · 11

3172

576

2 · 7

120

4250

192

3 · 19

3620

640

2 · 29

4210

720

−1

4.08

3482

480

2 · 3 · 5

168

5460

576

−1

4.11

3722

496

2 · 31

4810

768

3 · 7

−1

104

4550

832

0.69

127

5461

5 · 13

4420

672

2 · 3 · 11

−1

144

6100

1152

−1

4.20

4490

544

2 · 17

−1

126

6090

432

3 · 23

5300

768

2 · 5 · 7

−1

144

6500

1152

−1

4.26

5042

576

2 · 3

−1

195

7735

312

−1

4.29

5330

592

2 · 37

114

6850

120

912

3 · 5

−1

124

6510

992

2 · 19

−1

140

7602

480

7 · 11

6100

768

2 · 3 · 13

−1

168

8500

1344

−1

4.37

6242

640

2 · 5

−1

186

8866

144

1.10

121

7381

102

968

2 · 41

126

8410

1008

−1

4.42

6890

672

2 · 3 · 7

224

10500

768

5 · 17

108

7540

864

2 · 43

132

9250

120

1056

3 · 29

120

8420

960

2 · 11

180

10370

288

−1

4.49

7922

144

720

2 · 3 · 5

234

11830

120

1872

7 · 13

112

8500

896

2 · 23

−1

168

11130

576

3 · 31

128

9620

1024

2 · 47

144

11050

1152

5 · 19

120

9412

960

2 · 3

252

13650

−1

4.57

9410

784

2 · 7

−1

171

12255

108

1368

3 · 11

−1

156

11102

1248

100

2 · 5

217

13671

744

factorization

φ(n)

ω(n)

Ω(n)

↑ Long (1972, p. 151)

↑ Pettofrezzo & Byrkit (1970, p. 58)

↑ Niven & Zuckerman, 4.2.

↑ Nagell, I.9.

↑ Bateman & Diamond, 2.1.

↑ Hardy & Wright, intro. to Ch. XVI

↑ Hardy, Ramanujan, § 10.2

↑ Apostol, Modular Functions ..., § 1.15, Ch. 4, and ch. 6

↑ Hardy & Wright, §§ 18.1–18.2

↑ Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. Vol. 46. Cambridge University Press. pp. 36–55. ISBN 0-521-41261-7.

↑ Hardy & Wright, § 17.6, show how the theory of generating functions can be constructed in a purely formal manner with no attention paid to convergence.

↑ Hardy & Wright, Thm. 263

↑ Hardy & Wright, Thm. 63

↑ see references at Jordan's totient function

↑ Holden et al. in external links The formula is Gegenbauer's

↑ Hardy & Wright, Thm. 288–290

↑ Dineva in external links, prop. 4

↑ Hardy & Wright, Thm. 264

↑ Hardy & Wright, Thm. 296

↑ Hardy & Wright, Thm. 278

↑ Hardy & Wright, Thm. 386

↑ Hardy, Ramanujan, eqs 9.1.2, 9.1.3

↑ Koblitz, Ex. III.5.2

1 2 Hardy & Wright, § 20.13

↑ Hardy, Ramanujan, § 9.7

↑ Hardy, Ramanujan, § 9.13

↑ Hardy, Ramanujan, § 9.17

↑ Williams, ch. 13; Huard, et al. (external links).

1 2 Ramanujan, On Certain Arithmetical Functions, Table IV; Papers, p. 146

1 2 Koblitz, ex. III.2.8

↑ Koblitz, ex. III.2.3

↑ Koblitz, ex. III.2.2

↑ Koblitz, ex. III.2.4

↑ Apostol, Modular Functions ..., Ex. 6.10

↑ Apostol, Modular Functions..., Ch. 6 Ex. 10

↑ G.H. Hardy, S. Ramannujan, Asymptotic Formulæ in Combinatory Analysis, § 1.3; in Ramannujan, Papers p. 279

↑ Landau, p. 168, credits Gauss as well as Dirichlet

↑ Cohen, Def. 5.1.2

↑ Cohen, Corr. 5.3.13

↑ see Edwards, § 9.5 exercises for more complicated formulas.

↑ Cohen, Prop 5.3.10

↑ See Divisor function.

↑ Hardy & Wright, eq. 22.1.2

↑ See prime-counting functions.

↑ Hardy & Wright, eq. 22.1.1

↑ Hardy & Wright, eq. 22.1.3

↑ László Tóth, Menon's Identity and Arithmetical Sums ..., eq. 1

↑ Tóth, eq. 5

↑ Tóth, eq. 3

↑ Tóth, eq. 35

↑ Tóth, eq. 2

↑ Tóth states that Menon proved this for multiplicative f in 1965 and V. Sita Ramaiah for general f.

↑ Hardy Ramanujan, eq. 3.10.3

↑ Hardy & Wright, § 22.13

↑ Hardy & Wright, Thm. 329

↑ Hardy & Wright, Thms. 271, 272

↑ Hardy & Wright, eq. 16.3.1

↑ Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (C); Papers p. 133. A footnote says that Hardy told Ramanujan it also appears in an 1857 paper by Liouville.

↑ Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (F); Papers p. 134

↑ Apostol, Modular Functions ..., ch. 6 eq. 4

↑ Apostol, Modular Functions ..., ch. 6 eq. 3

References

edit

Bateman, Paul T.; Diamond, Harold G. (2004), Analytic number theory, an introduction, World Scientific, ISBN 978-981-238-938-1
Jameson, G. J. O. (2003), The Prime Number Theorem, Cambridge University Press, ISBN 0-521-89110-8
William J. LeVeque (1996), Fundamentals of Number Theory, Courier Dover Publications, ISBN 0-486-68906-9
Nagell, Trygve (1964), Introduction to number theory (2nd Edition), Chelsea, ISBN 978-0-8218-2833-5{{citation}}: ISBN / Date incompatibility (help)
Ramanujan, Srinivasa (2000), Collected Papers, Providence RI: AMS / Chelsea, ISBN 978-0-8218-2076-6
"Arithmetic function", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Matthew Holden, Michael Orrison, Michael Varble Yet another Generalization of Euler's Totient Function
Huard, Ou, Spearman, and Williams. Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions
Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions Archived 2021-01-16 at the Wayback Machine
László Tóth, Menon's Identity and arithmetical sums representing functions of several variables

Classes of natural numbers

Powers and related numbers
Achilles Power of 2 Power of 3 Power of 10 Square Cube Fourth power Fifth power Sixth power Seventh power Eighth power Perfect power Powerful Prime power

Of the form a × 2 ± 1
Cunningham Cullen Double Mersenne Fermat Mersenne Proth Thabit Woodall

Other polynomial numbers
Hilbert Idoneal Leyland Loeschian Lucky numbers of Euler Williams

Recursively defined numbers
Fibonacci Jacobsthal Leonardo Lucas Narayana Padovan Pell Perrin Graham

Possessing a specific set of other numbers
Amenable Congruent Knödel Riesel Sierpiński

Expressible via specific sums
Nonhypotenuse Polite Practical Primary pseudoperfect Ulam Wolstenholme

Figurate numbers

2-dimensional

centered	Centered triangular Centered square Centered pentagonal Centered hexagonal Centered heptagonal Centered octagonal Centered nonagonal Centered decagonal Star
non-centered	Triangular Square Square triangular Pentagonal Hexagonal Heptagonal Octagonal Nonagonal Decagonal Dodecagonal

3-dimensional

centered	Centered tetrahedral Centered cube Centered octahedral Centered dodecahedral Centered icosahedral
non-centered	Tetrahedral Cubic Octahedral Dodecahedral Icosahedral Stella octangula
pyramidal	Square pyramidal

4-dimensional

non-centered	Pentatope Squared triangular Tesseractic

Combinatorial numbers
Bell Cake Catalan Dedekind Delannoy Euler Eulerian Fuss–Catalan Lah Lazy caterer's sequence Lobb Motzkin Narayana Ordered Bell Schröder Schröder–Hipparchus Stirling first Stirling second Telephone number Wedderburn–Etherington

Primes
Wieferich Wall–Sun–Sun Wolstenholme prime Wilson

Pseudoprimes
Carmichael number Catalan pseudoprime Elliptic pseudoprime Euler pseudoprime Euler–Jacobi pseudoprime Fermat pseudoprime Frobenius pseudoprime Lucas pseudoprime Lucas–Carmichael number Perrin pseudoprime Somer–Lucas pseudoprime Strong pseudoprime

Arithmetic functions and dynamics

Divisor functions	Abundant Almost perfect Arithmetic Betrothed Colossally abundant Deficient Descartes Hemiperfect Highly abundant Highly composite Hyperperfect Multiply perfect Perfect Practical Primitive abundant Quasiperfect Refactorable Semiperfect Sublime Superabundant Superior highly composite Superperfect
Prime omega functions	Almost prime Semiprime
Euler's totient function	Highly cototient Highly totient Noncototient Nontotient Perfect totient Sparsely totient
Aliquot sequences	Amicable Perfect Sociable Untouchable
Primorial	Euclid Fortunate

Other prime factor or divisor related numbers
Blum Cyclic Erdős–Nicolas Erdős–Woods Friendly Giuga Harmonic divisor Jordan–Pólya Lucas–Carmichael Pronic Regular Rough Smooth Sphenic Størmer Super-Poulet

Numeral system-dependent numbers

Arithmetic functions
and dynamics

Persistence
- Additive
- Multiplicative

Digit sum	Digit sum Digital root Self Sum-product
Digit product	Multiplicative digital root Sum-product
Coding-related	Meertens
Other	Dudeney Factorion Kaprekar Kaprekar's constant Keith Lychrel Narcissistic Perfect digit-to-digit invariant Perfect digital invariant Happy

P-adic numbers-related

Automorphic
- Trimorphic

Digit-composition related

Digit-permutation related

Divisor-related

Other

Friedman

Binary numbers
Evil Odious Pernicious

Generated via a sieve
Lucky Prime

Sorting related
Pancake number Sorting number

Natural language related
Aronson's sequence Ban

Graphemics related
Strobogrammatic

View original on Wikipedia | Back | FazBrowse Home

Arithmetic function

Ω(n), ω(n), νp(n) – prime power decomposition

φ(n) – Euler totient function

μ(n) – Möbius function

χ(n) – characters

D(n) – Arithmetic derivative

Relations among the functions

Dirichlet convolutions

Divisor sum convolutions

Miscellaneous

First 100 values of some arithmetic functions

References