Divider count function

The number of divisors function indicates how many divisors a natural number has; the one and the number itself are counted. The number function is part of the mathematical branch of number theory . It is usually referred to as or - since it represents a special case of the divider function , also as . ${\displaystyle d}$ ${\displaystyle \tau }$ ${\displaystyle \sigma _{0}(n)}$

${\displaystyle d(n)}$... number of divisors of . ... the smallest with dividers. ${\displaystyle n}$
${\displaystyle n_{\mathrm {min} }}$ ${\displaystyle n}$ ${\displaystyle d(n)}$

${\displaystyle d(n)}$	${\displaystyle n_{\mathrm {min} }}$	Factorization of ${\displaystyle n_{\mathrm {min} }}$
1	1	1
2	2	2
3	4th	2 2
4th	6th	2 · 3
5	16	2 4
6th	12	2 2 3
7th	64	2 6
8th	24	2 3 3
9	36	2 2 3 2
10	48	2 4 3
11	1,024	2 10
12	60	2 2 3 5
13	4,096	2 12
14th	192	2 6 3
15th	144	2 4 3 2
16	120	2 3 3 5
17th	65,536	2 16
18th	180	2 2 3 2 5
19th	262.144	2 18
20th	240	2 4 3 5
21st	576	2 6 3 2
22nd	3,072	2 10 3
23	4,194,304	2 22
24	360	2 3 3 2 5
25th	1,296	2 4 3 4
26th	12,288	2 12 3
27	900	2 2 3 2 5 2
28	960	2 6 3 5
29	268.435.456	2 28
30th	720	2 4 3 2 5
31	1,073,741,824	2 30
32	840	2 3 3 5 7
33	9.216	2 10 3 2
34	196.608	2 16 3
35	5,184	2 6 3 4
36	1,260	2 2 3 2 5 7

definition

For every natural number is defined: ${\displaystyle n\in \mathbb {N} }$

${\displaystyle d(n):=\#\{d\in \mathbb {N} :d\mid n\}}$.

The first values ​​are:

${\displaystyle n}$	1	2	3	4th	5	6th	7th	8th	9	10	11	12
Divisor of ${\displaystyle n}$	1	1, 2	1, 3	1, 2, 4	1, 5	1, 2, 3, 6	1, 7	1, 2, 4, 8	1, 3, 9	1, 2, 5, 10	1, 11	1, 2, 3, 4, 6, 12
${\displaystyle d(n)}$	1	2	2	3	2	4th	2	4th	3	4th	2	6th

properties

• Does the number have the prime factorization ${\displaystyle n}$

${\displaystyle n=p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\dotsm p_{r}^{e_{r}},}$

so:

${\displaystyle d(n)=(e_{1}+1)(e_{2}+1)\dotsm (e_{r}+1)}$

• For coprime numbers and the following applies: ${\displaystyle m}$ ${\displaystyle n}$

${\displaystyle d(mn)=d(m)\cdot d(n)}$

The number of divisors function is therefore a multiplicative number theoretic function .

• A number is a prime number if and only if holds. ${\displaystyle n}$ ${\displaystyle d(n)=2}$
• A number is a square number if and only if is odd. ${\displaystyle n}$ ${\displaystyle d(n)}$
• The Dirichlet series belonging to the number function is the square of the Riemann zeta function :

${\displaystyle \zeta (s)^{2}=\sum _{n=1}^{\infty }{\frac {d(n)}{n^{s}}}}$(for ). ${\displaystyle \operatorname {Re} \,s>1}$

Asymptotics

On average , more precisely: There are constants , so ${\displaystyle d(n)\approx \log n}$ ${\displaystyle \beta \leq {\tfrac {1}{2}}}$

${\displaystyle \sum _{n\leq x}d(n)=x\log x+(2\gamma -1)x+O(x^{\beta })}$

applies. (" " Is a Landau symbol and the Euler-Mascheroni constant .) ${\displaystyle O}$ ${\displaystyle \gamma }$

The knowledge that a number is a divisor of roughly numbers can serve as a heuristic , so that the sum on the left is roughly too ${\displaystyle d\leq x}$ ${\displaystyle {\tfrac {x}{d}}}$ ${\displaystyle n\leq x}$

${\displaystyle x\cdot \sum _{d=1}^{\lfloor x\rfloor }{\frac {1}{d}}\approx x\log x.}$

(For the last step, see harmonic series .)

The value has already been proven by PGL Dirichlet ; the search for better values ​​is therefore also known as the Dirichletian divisor problem . ${\displaystyle \beta ={\tfrac {1}{2}}}$

Better values ​​were given by GF Woronoi (1903, ), J. van der Corput (1922, ) and MN Huxley ( ). On the other hand, GH Hardy and E. Landau showed that must apply. The possible values ​​for are still the subject of research. ${\displaystyle x^{\tfrac {1}{3}}\log x}$ ${\displaystyle \beta ={\tfrac {33}{100}}}$ ${\displaystyle \beta ={\tfrac {131}{416}}}$ ${\displaystyle \beta \geq {\tfrac {1}{4}}}$ ${\displaystyle \beta }$

Generalizations

The divisor function assigns the sum of the -th powers of its divisors to each number : ${\displaystyle \sigma _{k}(n)}$ ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle \sigma _{k}(n)=\sum _{d\mid n}d^{k}}$

The divisor sum is the special case of the divider function for , and the divisor number function is the special case of the divider function for : ${\displaystyle k=1}$ ${\displaystyle k=0}$

${\displaystyle \sigma (n)=\sigma _{1}(n)=\sum _{d\mid n}d^{1}=\sum _{d\mid n}d}$

${\displaystyle d(n)=\sigma _{0}(n)=\sum _{d\mid n}d^{0}=\sum _{d\mid n}1}$

See also

• High composite number
• Number theoretic function

literature

• GH Hardy, EM Wright: An Introduction to the Theory of Numbers. 4th edition, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1 .

Web links

• Eric W. Weisstein : Divisor Function . In: MathWorld (English).

swell

1. ↑ For further initial values ​​see also sequence A000005 in OEIS .
2. ^ GH Hardy, EM Wright: An Introduction to the Theory of Numbers. 4th edition, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1 , Theorem 273, p. 239.
3. ^ GH Hardy, EM Wright: An Introduction to the Theory of Numbers. 4th edition, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1 , Theorem 289, p. 250.
4. ^ GH Hardy, EM Wright: An Introduction to the Theory of Numbers. 4th edition, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1 , Theorem 320, p. 264.
5. ↑ PGL Dirichlet: About the determination of the mean values ​​in number theory. In: Treatises of the Royal Prussian Academy of Sciences. 1849, pp. 69-83; or Werke, Volume II, pp. 49-66.
6. ↑ G. Voronoï : Sur un problème du calcul des fonctions asymptotiques. In: J. Reine Angew. Math. 126 (1903) pp. 241-282.
7. ↑ JG van der Corput: tightening of the estimation in the divider problem. In: Math. Ann. 87 (1922) 39-65. Corrections 89 (1923) p. 160.
8. ^ MN Huxley: Exponential Sums and Lattice Points III . In: Proc. London Math. Soc. tape 87 , no. 3 , 2003, p. 591-609 .
9. ^ GH Hardy: On Dirichlet's divisor problem. In: Lond. MS Proc. (2) 15 (1915) 1-25.
   See GH Hardy, EM Wright: An Introduction to the Theory of Numbers. 4th edition, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1 , p. 272.
10. ↑ Eric W. Weisstein : Divisor Function . In: MathWorld (English).