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 <math>d</math> oder <math>\tau</math> bezeichnet – da sie einen Spezialfall der Teilerfunktion darstellt, auch als <math>\sigma_0(n)</math>.
| <math>d(n)</math> | <math>n_\mathrm{min}</math> | Faktorisierung von <math>n_\mathrm{min}</math> |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 4 | 22 |
| 4 | 6 | 2 · 3 |
| 5 | 16 | 24 |
| 6 | 12 | 22 · 3 |
| 7 | 64 | 26 |
| 8 | 24 | 23 · 3 |
| 9 | 36 | 22 · 32 |
| 10 | 48 | 24 · 3 |
| 11 | 1.024 | 210 |
| 12 | 60 | 22 · 3 · 5 |
| 13 | 4.096 | 212 |
| 14 | 192 | 26 · 3 |
| 15 | 144 | 24 · 32 |
| 16 | 120 | 23 · 3 · 5 |
| 17 | 65.536 | 216 |
| 18 | 180 | 22 · 32 · 5 |
| 19 | 262.144 | 218 |
| 20 | 240 | 24 · 3 · 5 |
| 21 | 576 | 26 · 32 |
| 22 | 3.072 | 210 · 3 |
| 23 | 4.194.304 | 222 |
| 24 | 360 | 23 · 32 · 5 |
| 25 | 1.296 | 24 · 34 |
| 26 | 12.288 | 212 · 3 |
| 27 | 900 | 22 · 32 · 52 |
| 28 | 960 | 26 · 3 · 5 |
| 29 | 268.435.456 | 228 |
| 30 | 720 | 24 · 32 · 5 |
| 31 | 1.073.741.824 | 230 |
| 32 | 840 | 23 · 3 · 5 · 7 |
| 33 | 9.216 | 210 · 32 |
| 34 | 196.608 | 216 · 3 |
| 35 | 5.184 | 26 · 34 |
| 36 | 1.260 | 22 · 32 · 5 · 7 |
Definition
Für jede natürliche Zahl <math>n \in \N</math> wird die Teileranzahlfunktion definiert als
- <math>d(n) := |\{d \in \N : d\mid n\}|</math>,
wobei <math>| \cdot |</math> die Mächtigkeit der Menge ist.
Die ersten Werte sind:<ref>Weitere Anfangswerte siehe auch Folge A000005 in OEIS.</ref>
| <math>n</math> | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Teiler von <math>n</math> | 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 |
| <math>d(n)</math> | 1 | 2 | 2 | 3 | 2 | 4 | 2 | 4 | 3 | 4 | 2 | 6 |
Eigenschaften
- Hat die Zahl <math>n</math> die Primfaktorzerlegung
- <math>n=p_1^{e_1}\cdot p_2^{e_2}\dotsm p_r^{e_r},</math>
- so gilt:<ref>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.</ref>
- <math>d(n) = (e_1+1)(e_2+1) \dotsm (e_r+1)</math>
- Für teilerfremde Zahlen <math>m</math> und <math>n</math> gilt:
- <math>d(mn) = d(m)\cdot d(n)</math>
- Die Teileranzahlfunktion ist also eine multiplikative zahlentheoretische Funktion.
- Eine Zahl <math>n</math> ist genau dann eine Primzahl, wenn <math>d(n)=2</math> gilt.
- Eine Zahl <math>n</math> ist genau dann eine Quadratzahl, wenn <math>d(n)</math> ungerade ist.
- Die zur Teileranzahlfunktion gehörige Dirichlet-Reihe ist das Quadrat der riemannschen Zetafunktion:<ref>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.</ref>
- <math>\zeta(s)^2=\sum_{n=1}^\infty\frac{d(n)}{n^s}</math> (für <math>\operatorname{Re}\,s>1</math>).
- Wenn der Wert <math>d(n)</math> eine Primzahl ist, dann ist <math>n_{min} = 2^{d(n) - 1}</math>
- Wenn der Wert <math>d(n)</math> eine zusammengesetzte Zahl <math>\neq 1</math> ist, dann ist <math>n_{min}</math> stets durch 6 teilbar
- Wenn der Wert <math>d(n)</math> eine Zweierpotenz ist, dann ist <math>n_{min}</math> eine hochzusammengesetzte Zahl
Asymptotik
Im Mittel ist <math>d(n)\approx\log n</math>, präziser gilt:<ref>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.</ref>
- <math>\sum_{n\leq x}d(n)=x\log x+(2\gamma-1)x+O(\sqrt x )</math>
Dabei sind „<math>O</math>“ ein Landau-Symbol und <math>\gamma</math> die Euler-Mascheroni-Konstante.
Als Heuristik kann die Erkenntnis dienen, dass eine Zahl <math>d\leq x</math> ein Teiler von etwa <math>\tfrac xd</math> Zahlen <math>n\leq x</math> ist, damit wird die Summe auf der linken Seite in etwa zu
- <math>x\cdot\sum_{d=1}^{\lfloor x\rfloor}\frac 1d\approx x\log x.</math>
(Zum letzten Schritt siehe harmonische Reihe.)
Der Wert <math>\beta=\tfrac12</math> für den Fehlerterm <math>O(x^{\beta})</math> wurde bereits von P. G. L. Dirichlet bewiesen;<ref>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.</ref> die Suche nach besseren Werten ist deshalb auch als dirichletsches Teilerproblem bekannt.
Bessere Werte wurden von G. F. Woronoi (1903, <math>x^{\tfrac13}\log x</math>),<ref>G. Voronoï: Sur un problème du calcul des fonctions asymptotiques. In: J. Reine Angew. Math. 126 (1903) S. 241–282.</ref> J. van der Corput (1922, <math>\beta=\tfrac{33}{100}</math>)<ref>J. G. van der Corput: Verschärfung der Abschätzung beim Teilerproblem. In: Math. Ann. 87 (1922) 39–65. Berichtigungen 89 (1923) S. 160.</ref> sowie M. N. Huxley (<math>\beta=\tfrac{131}{416}</math>)<ref>{{#invoke:Vorlage:Literatur|f}}</ref> angegeben. Auf der anderen Seite zeigten G. H. Hardy und E. Landau, dass <math>\beta\geq\tfrac14</math> gelten muss.<ref>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.</ref> Die möglichen Werte für <math>\beta</math> sind immer noch Forschungsgegenstand.
Verallgemeinerungen
Die Teilerfunktion <math>\sigma_k(n)</math> ordnet jeder Zahl <math>n</math> die Summe der <math>k</math>-ten Potenzen ihrer Teiler zu:<ref>{{#if: | {{{author}}} | Eric W. Weisstein }}: Divisor Function. In: MathWorld (englisch). {{#if: | {{#ifeq: {{#property:P2812}} | {{{id}}} | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}</ref>
- <math>\sigma_k(n) = \sum_{d\mid n} d^k</math>
Die Teilersumme ist der Spezialfall der Teilerfunktion für <math>k=1</math>, und die Teileranzahlfunktion ist der Spezialfall der Teilerfunktion für <math>k=0</math>:
- <math>\sigma(n) = \sigma_1(n) = \sum_{d\mid n} d^1 = \sum_{d\mid n} d</math>
- <math>d(n) = \sigma_0(n) = \sum_{d\mid n} d^0 = \sum_{d\mid n} 1</math>
Siehe auch
Literatur
- 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
- {{#if: | {{{author}}} | Eric W. Weisstein }}: Divisor Function. In: MathWorld (englisch). {{#if: | {{#ifeq: {{#property:P2812}} | {{{id}}} | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}
Quellen
<references />