Teileranzahlfunktion

Die Teileranzahlfunktion gibt an, wie viele positive 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 $d$ oder $\tau$ bezeichnet – da sie einen Spezialfall der Teilerfunktion darstellt, auch als $\sigma _{0}(n)$ .

$d(n)$ … Anzahl der Teiler von $n$ .
$n_{\mathrm {min} }$ … kleinstes $n$ mit $d(n)$ Teilern.
$d(n)$	$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 Bearbeiten

Für jede natürliche Zahl $n\in \mathbb {N}$ wird die Teileranzahlfunktion definiert als

d(n):=|\{d\in \mathbb {N} :d\mid n\}|

,

wobei $|\cdot |$ die Mächtigkeit der Menge ist.

Die ersten Werte sind:^[1]

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

Eigenschaften Bearbeiten

Hat die Zahl $n$ die Primfaktorzerlegung

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

so gilt:^[2]

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

Für teilerfremde Zahlen $m$ und $n$ gilt:

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

Die Teileranzahlfunktion ist also eine multiplikative zahlentheoretische Funktion.

Eine Zahl $n$ ist genau dann eine Primzahl, wenn $d(n)=2$ gilt.
Eine Zahl $n$ ist genau dann eine Quadratzahl, wenn $d(n)$ ungerade ist.
Die zur Teileranzahlfunktion gehörige Dirichlet-Reihe ist das Quadrat der riemannschen Zetafunktion:^[3]

\zeta (s)^{2}=\sum _{n=1}^{\infty }{\frac {d(n)}{n^{s}}}

(für

\operatorname {Re} \,s>1

).

Asymptotik Bearbeiten

Im Mittel ist $d(n)\approx \log n$ , präziser gilt: ^[4]

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

Dabei sind „ $O$ “ 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 {1}{d}}\approx x\log x.

(Zum letzten Schritt siehe harmonische Reihe.)

Der Wert $\beta ={\tfrac {1}{2}}$ für den Fehlerterm $O(x^{\beta })$ wurde bereits von P. G. L. Dirichlet bewiesen;^[5] die Suche nach besseren Werten ist deshalb auch als dirichletsches Teilerproblem bekannt.

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

Verallgemeinerungen Bearbeiten

Die Teilerfunktion $\sigma _{k}(n)$ ordnet jeder Zahl $n$ die Summe der $k$ -ten Potenzen ihrer Teiler zu:^[10]

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

Die Teilersumme ist der Spezialfall der Teilerfunktion für $k=1$ , und die Teileranzahlfunktion ist der Spezialfall der Teilerfunktion für $k=0$ :

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

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

Siehe auch Bearbeiten

Literatur Bearbeiten

G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers. 4. Auflage, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1.

Weblinks Bearbeiten

Eric W. Weisstein: Divisor Function. In: MathWorld (englisch).

Quellen Bearbeiten

↑ Weitere Anfangswerte siehe auch Folge A000005 in OEIS.
↑ G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers. 4. Auflage, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1, Theorem 273, S. 239.
↑ G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers. 4. Auflage, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1, Theorem 289, S. 250.
↑ G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers. 4. Auflage, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1, Theorem 320, S. 264.
↑ P. G. L. Dirichlet: Über die Bestimmung der mittleren Werthe in der Zahlentheorie. In: Abhandlungen der Königlich Preussischen Akademie der Wissenschaften. 1849, S. 69–83; oder Werke, Band II, S. 49–66.
↑ G. Voronoï: Sur un problème du calcul des fonctions asymptotiques. In: J. Reine Angew. Math. 126 (1903) S. 241–282.
↑ J. G. van der Corput: Verschärfung der Abschätzung beim Teilerproblem. In: Math. Ann. 87 (1922) 39–65. Berichtigungen 89 (1923) S. 160.
↑ M. N. Huxley: Exponential Sums and Lattice Points III. In: Proc. London Math. Soc. Band 87, Nr. 3, 2003, S. 591–609.
↑ G. H. Hardy: On Dirichlet’s divisor problem. In: Lond. M. S. Proc. (2) 15 (1915) 1–25.
Vgl. G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers. 4. Auflage, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1, S. 272.
↑ Eric W. Weisstein: Divisor Function. In: MathWorld (englisch).

[1] Weitere Anfangswerte siehe auch Folge A000005 in OEIS.

[2] G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers. 4. Auflage, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1, Theorem 273, S. 239.

[3] G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers. 4. Auflage, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1, Theorem 289, S. 250.

[4] G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers. 4. Auflage, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1, Theorem 320, S. 264.

[5] P. G. L. Dirichlet: Über die Bestimmung der mittleren Werthe in der Zahlentheorie. In: Abhandlungen der Königlich Preussischen Akademie der Wissenschaften. 1849, S. 69–83; oder Werke, Band II, S. 49–66.

[6] G. Voronoï: Sur un problème du calcul des fonctions asymptotiques. In: J. Reine Angew. Math. 126 (1903) S. 241–282.

[7] J. G. van der Corput: Verschärfung der Abschätzung beim Teilerproblem. In: Math. Ann. 87 (1922) 39–65. Berichtigungen 89 (1923) S. 160.

[8] M. N. Huxley: Exponential Sums and Lattice Points III. In: Proc. London Math. Soc. Band 87, Nr. 3, 2003, S. 591–609.

[9] G. H. Hardy: On Dirichlet’s divisor problem. In: Lond. M. S. Proc. (2) 15 (1915) 1–25.
Vgl. G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers. 4. Auflage, Oxford University Press, Oxford 1975. ISBN 0-19-853310-1, S. 272.

[10] Eric W. Weisstein: Divisor Function. In: MathWorld (englisch).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]