Modul 11

Berechnung und Eigenschaften einer zahlentheoretischen Funktion

1. Problemstellung

	3	4	5	6	8	9	12	13	14	16	22	30	31	33	36	37	40
	5	8	9	15	20	21	40	25	39	48	63	135	61	105	168	73	180

Tabelle 1: Funktionswerte für ausgewählte kleine

Naheliegend ist die iterative () Berechnung von unter Verwendung des Euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers von und der Laufvariable .

Wir gehen im folgenden von der Primfaktorenzerlegung von aus und entwickeln nach einigen Vorbetrachtungen zwei andere Algorithmen sowie eine geschlossene Formel zur Berechnung von für beliebige gegebene . Dieser Ansatz wird, wie aus Tabelle 2 ersichtlich, einen wesentlichen Effizienzgewinn liefern.

	1000	10000	100000	1000000
Anwendung des Euklidischen Algorithmus	0.3	32	4039	-
in 3.1 vorgestellter Algorithmus	0.3	0.2	2.1	30.0
Berechnung nach Formel (18)	0.3	0.1	1.1	19.7

Tabelle 2: Laufzeit verschiedener Algorithmen zur Berechnung von für in Sekunden, ermittelt auf einem AMD K6 166MHz.

2. Bezeichnungen und Vorbetrachtungen

(1)

Es gilt (wobei die Anzahl der Elemente einer endlichen Menge bezeichnet)

Die Teilbarkeit von läßt sich dann in der Sprache der Ordnungsrelation auf formulieren. Sei Entsprechend sei die strenge (nichtreflexive) Einschränkung der Ordnung auf .

Dann gilt somit

(2)

Das bezüglich maximale Element in ist offensichtlich : .

Die Anzahl der Zahlen () mit sei mit bezeichnet,

(3)

Offensichtlich gilt

(4)

Im weiteren dient der Erläuterung stets das Beispiel

(5)

Zur Veranschaulichung der oben eingeführten Begriffe und Beziehungen denke man sich die als Gitterpunkte eines -dimensionalen Feldes, wobei jeweils der -ten Dimension der -te Primfaktor von , zugeordnet ist. Nach (1) erhält man damit auch eine Anordnung von in diesem Gitter.

Ein Teiler von teilt genau dann, wenn dieser entlang aller Koordinatenachsen ,,weiter rechts`` () oder ,,gleichauf`` () liegt, also wenn (vgl. Bild 1).

Bild 1: Teiler von , vgl. (5),(1)

3. Lösungsideen

3.1. Dynamische Programmierung

Aus (2) und (3) folgt mit

(6)

eine rekursive Berechnungsvorschrift der mit dem Startwert . Ein direkt auf (6) basierender Algorithmus ist nicht effektiv, da einige mehrfach auftretende Teilsummen wiederholt berechnet werden. Am Beispiel (s.o.) sei dies für sowie anhand von Bild 2 dargestellt. Die Felder und sind durch gestrichelte bzw. gepunktete Linien umrandet. Sowohl bei der Berechnung von als auch bei der Berechnung von nach (6) wird die Summe aller Elemente des Feldes , umrandet mit durchgezogenen Linien, separat berechnet.

Bild 2: Feld der für n=180, vgl. (5) u. Bild 1; Identische Teilsummen bei der Berechnung von für verschiedene nach (6)

Durch ,,dynamische Programmierung`` kann der auf Gleichung (6) basierende rekursive Algorithmus in einen effizienteren iterativen überführt werden. Dabei besteht die Grundidee darin, möglichst viele relevante Zwischenergebnisse zu speichern und geschickt wiederzuverwenden. Das wird wie folgt formalisiert:

Sei die Standardbasis im , d.h. .

Für beliebige -Tupel sei die Summe komponentenweise erklärt, d.h. .

Die Summe aus (6) wird nun in rekurrente Teilsummen () zerlegt:

	(7)
	(8)

Für (8) kann auch geschrieben werden:

(9)

Die Startwerte für (9) sind für alle .

Nun erhalten wir die Summe aus (6) wie folgt:

(10)

Weiterhin gilt

(11)

und schließlich

(12)

In Bild 3 ist die Zerlegung der Summe aus (6) für das Beispiel dargestellt (vgl. (5) u. Bilder 1,2). Die Elemente, welche zu den Teilsummen () zusammengefaßt werden, sind durch gepunktete, gestrichelte bzw. volle Linien verbunden.

Zur Berechnung von wird das Feld beginnend bei ,,absteigend`` durchlaufen (für das Beispiel (5) in der Reihenfolge (2,2,1), (1,2,1), (0,2,1), (2,1,1), (1,1,1), ). In jedem Iterationsschritt werden die nach (9), nach (12) und anschließend die nach (8) berechnet.

Bild 3: Feld der für ; Zerlegung der Summe aus () für in Teilsummen nach (9).

3.2. Geschlossene Formel für

Der in 3.1 vorgestellte Algorithmus ist immer noch nicht optimal, da er einige Beziehungen der nicht ausnutzt. Im folgenden wird ein anderer, fruchtbarerer Ansatz zur Berechnung der entwickelt. Dazu sind zuerst einige Vorbetrachtungen notwendig.

Sei . kann als Menge der Eckpunkte eines -dimensionalen Hyperkubus interpretiert werden.

Sei ferner die Abbildung von auf definiert durch mit

(13)

Speziell folgt stets .

Diese Abbildung liefert eine Einteilung von in Klassen (). Es gilt, wie induktiv ersichtlich wird,

(14)

Bild 4: Klasseneinteilung von für

Durch Einsetzen von (2) in die Definitionsgleichung (3) der erhält man woraus sich induktiv über beginnend mit (wobei das Produkt zu 1 definiert sei) entwickeln läßt: Unter Beachtung von für beliebige endliche Mengen folgt: Für erhalten wir schließlich:

	(15)
	(16)

Dieser geschlossene Formelausdruck für wird hauptsächlich durch bestimmt - insofern, als daß gilt:

(17)

3.3.Geschlossene Formel für

Nach Einsetzen von (15) in (4) kann ein geschlossener Formelausdruck für entwickelt werden: Unter Anwendung der zuvor eingeführten Klasseneinteilung von und (14),(17) folgt: Diese Summe kann - ähnlich wie (16),(15) - elegant als Produkt geschrieben werden:

(18)

Wir geben im folgenden einen Beweis der Formel (18), der unabhängig von der obigen Herleitung ist. Im Beweis wird gleichzeitig eine interessante Eigenschaft von gezeigt, nämlich daß falls .

Beweis:

Erster Schritt: Sei ( ...Primzahl, ). Dann folgt: Damit erhalten wir

Zweiter Schritt: Sei mit und . Dann gilt Mit und folgt:

Sei fest. Dann liegen je zwei verschiedene Zahlen in zwei verschiedenen Restklassen modulo . Es folgt

Damit erhält man induktiv wenn die paarweise teilerfremd, d.h.

4. Schlußbetrachtung

Der Zeitaufwand der Berechnung von nach dem in 3.1 vorgestellten Algorithmus bzw. nach der expliziten Formel (18) wird durch den Aufwand der Primfaktorzerlegung von bestimmt. Diesen Aufwand zu unterbieten scheint nicht möglich.

Die Funktion hat offenbar einige sehr interessante Eigenschaften, die weiterer Untersuchungen bedürfen. Auf einige Aspekte soll hingewiesen werden.

1. Die Punkte mit , Primzahl, approximieren für eine Gerade der Steigung . Analog bilden die Punkte mit , Primzahlen, für einen Strahl der Steigung . Für geht der Anstieg der zugeordneten Strahlen gegen 4, wie in Bild 5 zu sehen ist.

Bild 5: Graph von für mit Primzahlen.

Bild 6: Graph von für mit Primzahlen.

2. Der Graph von für , Primzahlen, kann auf die soeben erklärte Strahlenstruktur zurückgeführt werden: Wenn folgt , der Graph ist also eine Überlagerung von vertikalen Streckungen des soeben erklärten Strahlenbündels (vgl. Bild 6).

Auf analoge Weise läßt sich die Argumentation für , , Primzahlen fortsetzen; der Graph der Funktion wird von einer selbstähnlichen Struktur von Strahlenbündeln bestimmt. > 3. Man könnte nun erwarten, daß im wesentlichen linear wächst in dem Sinne, daß es einen durchschnittlichen Anstieg gibt mit

(19)

Verschiedene Überlegungen deuten darauf hin, daß dies nicht der Fall ist.

Eine grobe Argumentation benutzt folgendes: Die Wahrscheinlichkeit dafür, daß zwei zufällig gewählte Zahlen relativ prim sind, ist (vgl. [1]). Damit ist die Wahrscheinlichkeit dafür, daß der größte gemeinsame Teiler zweier zufällig gewählter Zahlen gleich einer natürlichen Zahl ist, gleich . Man kann nun abschätzen: wobei eine Konstante ist. Weiter erhält man auf diesem Weg:

	(20)
	(21)

Offenbar ist die asymptotische Abschätzung von nur schwer zu kontrollieren (es ist klar, daß nur exakt ist). Allerdings zeigen Computerexperimente, daß (20) eine recht gute Näherung ist, wobei sich noch ergibt.

Für eine weitere Untersuchung der Funktion bieten sich folgende Ausgangspunkte:

• Vielleicht kann unter Ausnutzung der oben erklärten rekursiven Struktur der Strahlenbündel das asymptotische Verhalten von für besser abgeschätzt werden als mit (20).
• Sei dann folgt aus (18) für alle : . Die Funktion stellt dann eine Normierung von dar: Vielleicht ergibt diese Normierung einen interessanten asymptotischen Mittelwert () von mit

  (21)

  Computerrechnungen bis liefern einen Wert von , aber keine stichhaltigen Aussagen über die Konvergenz des linken Ausdrucks von (21).

  Neben dem Mittelwert ist auch die Standardwabeichung von zu untersuchen.

• Aus (18) folgt für alle und damit eine weitere auszulotende Möglichkeit zur Normierung von .

Literatur