Teileranzahlfunktion

Die Teileranzahlfunktion gibt an, wie viele Teiler eine natürliche Zahl hat; dabei werden die Eins und die Zahl selbst mitgezählt. Die Teileranzahlfunktion gehört zum mathematischen Teilgebiet der Zahlentheorie. Sie wird meist mit oder $\tau$ bezeichnet – da sie einen Spezialfall der Teilerfunktion darstellt, auch als $\sigma _{0}(n)$ .

… Anzahl der Teiler von .
$n_{\mathrm {min} }$ … kleinstes mit Teilern.
Für $d(n)=37$ ist bereits $n>2^{31}$ .
	$n_{\mathrm {min} }$	Faktorisierung von $n_{\mathrm {min} }$
1	1	1
2	2	2
3	4	2²
4	6	2 · 3
5	16	2⁴
6	12	2² · 3
7	64	2⁶
8	24	2³ · 3
9	36	2² · 3²
10	48	2⁴ · 3
11	1.024	2¹⁰
12	60	2² · 3 · 5
13	4.096	2¹²
14	192	2⁶ · 3
15	144	2⁴ · 3²
16	120	2³ · 3 · 5
17	65.536	2¹⁶
18	180	2² · 3² · 5
19	262.144	2¹⁸
20	240	2⁴ · 3 · 5
21	576	2⁶ · 3²
22	3.072	2¹⁰ · 3
23	4.194.304	2²²
24	360	2³ · 3² · 5
25	1.296	2⁴ · 3⁴
26	12.288	2¹² · 3
27	900	2² · 3² · 5²
28	960	2⁶ · 3 · 5
29	268.435.456	2²⁸
30	720	2⁴ · 3² · 5
31	1.073.741.824	2³⁰
32	840	2³ · 3 · 5 · 7
33	9.216	2¹⁰ · 3²
34	196.608	2¹⁶ · 3
35	5.184	2⁶ · 3⁴
36	1.260	2² · 3² · 5 · 7

Definition

Für jede natürliche Zahl wird definiert:

$d(n):=\#\{d\colon 1\leq d\leq n{\text{ und }}d\mid n\}$

Die ersten Werte sind:

	1	2	3	4	5	6	7	8	9	10	11	12
Teiler von	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
	1	2	2	3	2	4	2	4	3	4	2	6

Eigenschaften

Hat die Zahl die Primfaktorzerlegung

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

so gilt:

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

Für teilerfremde Zahlen und gilt:

$d(mn)=d(m)\cdot d(n)$

Die Teileranzahlfunktion ist also eine multiplikative zahlentheoretische Funktion.

Eine Zahl ist genau dann eine Primzahl, wenn gilt.
Eine Zahl ist genau dann eine Quadratzahl, wenn ungerade ist.
Die zur Teileranzahlfunktion gehörige Dirichlet-Reihe ist das Quadrat der riemannschen Zetafunktion:

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

Asymptotik

Im Mittel ist $d(n)\approx \log n$ , präziser: Es gibt Konstanten $\beta \leq {\tfrac 12}$ , sodass

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

gilt. (Dabei sind „“ ein Landau-Symbol und $\gamma$ die Euler-Mascheroni-Konstante.)

Als Heuristik kann die Erkenntnis dienen, dass eine Zahl $d\leq x$ ein Teiler von etwa ${\tfrac {x}{d}}$ Zahlen $n\leq x$ ist, damit wird die Summe auf der linken Seite in etwa zu

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

(Zum letzten Schritt siehe harmonische Reihe.)

Der Wert $\beta ={\tfrac 12}$ wurde bereits von P. G. L. Dirichlet bewiesen; die Suche nach besseren Werten ist deshalb auch als dirichletsches Teilerproblem bekannt.

Bessere Werte wurden von G. F. Woronoi (1903, $x^{{{\tfrac 13}}}\log x$ ), J. van der Corput (1922, $\beta ={\tfrac {33}{100}}$ ) sowie M. N. Huxley ( $\beta ={\tfrac {131}{416}}$ ) angegeben. Auf der anderen Seite zeigten G. H. Hardy und E. Landau, dass $\beta \geq {\tfrac 14}$ gelten muss. Die möglichen Werte für $\beta$ sind immer noch Forschungsgegenstand.