Teileranzahlfunktion

Teileranzahlfunktion d(n) für natürliche Zahlen 0<n<24

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

${\displaystyle d(n)}$ … Anzahl der Teiler von ${\displaystyle n}$.
${\displaystyle n_{\mathrm {min} }}$ … kleinstes ${\displaystyle n}$ mit ${\displaystyle d(n)}$ Teilern.

${\displaystyle d(n)}$	${\displaystyle n_{\mathrm {min} }}$ Rosa: hochzusammengesetzte Zahl	Faktorisierung von ${\displaystyle n_{\mathrm {min} }}$
1	1	1
2	2	2
3	4	2^2
4	6	2 · 3
5	16	2^4
6	12	2^2 · 3
7	64	2^6
8	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
14	192	2^6 · 3
15	144	2^4 · 3^2
16	120	2^3 · 3 · 5
17	65.536	2^16
18	180	2^2 · 3^2 · 5
19	262.144	2^18
20	240	2^4 · 3 · 5
21	576	2^6 · 3^2
22	3.072	2^10 · 3
23	4.194.304	2^22
24	360	2^3 · 3^2 · 5
25	1.296	2^4 · 3^4
26	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
30	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

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

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

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

Die ersten Werte sind:[1]

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12
Teiler von ${\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	4	2	4	3	4	2	6

Eigenschaften

• Hat die Zahl ${\displaystyle n}$ die Primfaktorzerlegung

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

so gilt:[2]

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

• Für teilerfremde Zahlen ${\displaystyle m}$ und ${\displaystyle n}$ gilt:

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

Die Teileranzahlfunktion ist also eine multiplikative zahlentheoretische Funktion.

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

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

• Wenn der Wert ${\displaystyle d(n)}$ eine Primzahl ist, dann ist ${\displaystyle n_{min}=2^{d(n)-1}}$
• Wenn der Wert ${\displaystyle d(n)}$ eine zusammengesetzte Zahl ${\displaystyle \neq 1}$ ist, dann ist ${\displaystyle n_{min}}$ stets durch 6 teilbar
• Wenn der Wert ${\displaystyle d(n)}$ eine Zweierpotenz ist, dann ist ${\displaystyle n_{min}}$ eine hochzusammengesetzte Zahl

Asymptotik

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

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

Dabei sind „${\displaystyle O}$“ ein Landau-Symbol und ${\displaystyle \gamma }$ die Euler-Mascheroni-Konstante.

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

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

(Zum letzten Schritt siehe harmonische Reihe.)

Der Wert ${\displaystyle \beta ={\tfrac {1}{2}}}$ für den Fehlerterm ${\displaystyle 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, ${\displaystyle x^{\tfrac {1}{3}}\log x}$),[6] J. van der Corput (1922, ${\displaystyle \beta ={\tfrac {33}{100}}}$)[7] sowie M. N. Huxley (${\displaystyle \beta ={\tfrac {131}{416}}}$)[8] angegeben. Auf der anderen Seite zeigten G. H. Hardy und E. Landau, dass ${\displaystyle \beta \geq {\tfrac {1}{4}}}$ gelten muss.[9] Die möglichen Werte für ${\displaystyle \beta }$ sind immer noch Forschungsgegenstand.

Verallgemeinerungen

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

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

Die Teilersumme ist der Spezialfall der Teilerfunktion für ${\displaystyle k=1}$, und die Teileranzahlfunktion ist der Spezialfall der Teilerfunktion für ${\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}$

Siehe auch

• Hochzusammengesetzte Zahl
• Zahlentheoretische Funktion

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

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

Quellen

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).