________________________________________________________________________________
Inhalt....: Vollkommene Zahlen 1
Kategorie.: Unterrichtsmaterial
Mathematik: Zahlentheorie
MuPAD.....: 3.1.0
Datum.....: 2006-10-24
Autoren...: August Barkhausen <abarkhausen@gmx.de>
Funktionen: for, min, sum, nops, numlib::primedivisors, testeq, matrix, print
Funktionen: Typeset
________________________________________________________________________________
Konstruktion vollkommener Zahlen und Test
von Zahlen auf Vollkommenheit mit Hilfe einer
Tabelle vollkommener Zahlen
Im folgenden wird ein Algorithmus zur Berechnung von geraden vollkommenen
Zahlen durchgeführt, der auf die in dem Buch "Elementare Zahlentheorie" von
Remmert und Ulrich, 2. Auflage Birkhäuser1995" angegebene Charakterisierung
gerader vollkommener Zahlen zurückgeht. Die Formulierung der Charakterisierung
der vollkommenen geraden Zahlen sowie die weiteren Informationen zu vollkommen
Zahlen sind ebenfalls dem Buch von Remmert und Ulrich entnommen.
Mathematische Voraussetzungen sind neben Grundkenntnissen über elementare
Rechenregeln für reelle Zahlen und Primzahlen Programmierkenntnisse. Für die
Datenspeicherung werden Matrizen benutzt. Anderseits werden keine Grundkennt-
nisse über Rechenregeln für Matrizen benötigt. Eine Kurzeinführung über die De-
finition von Matrizen und die Identifikation einzelner Elemente einer Matrix reicht
hier aus. Schließlich wird alternativ auch der Befehl print für die Datenausgabe be-
nutzt.
Aus mathematischer Sicht wesentliche Aspekte des Notebooks sind:
- Umgang mit Algorithmen
- Überprüfung mathematischer Voraussetzungen
- Anwendung von Beweistechniken
- Wiederholung bekannter mathematischer Begriffe
- Kennenlernen neuer mathematischer Begriffe
Aus programmiertechnischer Sicht wesentliche Aspekte des Notebooks sind:
- Programmiertechniken in MuPAD
- Datenein- und Ausgabe in MuPAD
Vollkommene Zahlen sind natürliche Zahlen, bei denen die Summe der Teiler doppelt so
groß ist, wie die Zahl selbst.
Beispiele:
Die Teiler von 6 sind 1, 2, 3 und 6. Für die Summe gilt: 1+2+3+6 = 12. Andererseits ist
12: 2 = 6. Die Zahl 6 ist damit vollkommen. Die Teiler von 28 sind 1, 2, 4, 7, 14 und 28.
Für die Summe gilt: 1 + 2 + 4 + 7 + 14 = 28 und andererseits 28:2 = 14. Die Zahl 28 ist
damit vollkommen. Die Eigenschaft einer Zahl, vollkommen zu sein, ist nicht selbstver-
ständlich: Die Teiler von 12 beispielsweise sind 1, 2, 3, 4, 6, 12. Deren Summe ist 28
und die Hälfte von 28 ist 14. Die Zahl 12 ist damit nicht vollkommen.
Ob es ungerade vollkommene Zahlen gibt, ist nicht bekannt. Bekannt ist jedoch, dass es
keine ungeraden vollkommenen Zahlen a mit a < 10^50 gibt. (10 hoch 50).
Andererseits lassen sich alle geraden vollkommenen Zahlen angeben. Charakterisierung
der geraden vollkommenen Zahlen: Für eine natürliche gerade Zahl a = 2^(s-1)*b mit
s >=2, b ungerade sind äquivalent:
1) a ist vollkommen
2) b ist Primzahl und es gilt: b = 2^s-1
Das Notebook selbst setzt sich aus drei Teilen zusammen.
1) Die Konstruktion einer vollkommenen Zahl außerhalb einer Programmierlösung.
2) In einer Variation des Algorithmus zur Berechnung vollkommener Zahlen werden
die Ergebnisse des Algorithmus zur Speicherung in eine Matrix geschrieben und
anschließend auf Vollkommenheit überprüft.
3) Durch Vergleich mit den vollkommenen Zahlen in der Tabelle/ Matrix wird über-
prüft, inwieweit eine vorgegebene natürliche Zahl vollkommen ist.
1. Teil
Konstruktion vollkommener Zahlen in Einzelschritten am Beispiel der vollkommem Zahl 6.
s:=2:
b:=2^s-1
Vorausgesetzt wurde, dass b Primzahl sein soll. Für b = 3 ist dies ohne weitere Rechnung
bekannt. In anderen Fällen kann dies jedoch nicht ohne weiteres vorausgesetzt werden.
Wenn eine Zahl b Primzahl ist, hat sie nur einen Primteiler. Die Anzahl der Primtteiler wird
durch den Befehl nops geliefert.
Testergebnis:=testeq(nops(numlib::primedivisors(b))=1)
Bei dem Resultat TRUE ist b Primzahl, sonst nicht. Ist b Primzahl liefert der nächste
Schritt die vollkommene Zahl a. Ist b keine Primzahl ist die Zahl a unvollkommen, da
der Algorithmus alle geraden vollkommenen Zahlen charakterisiert.
a:=2^(s-1)*b:
if Testergebnis = TRUE
then
a:=2^(s-1)*b:
print(Typeset,
"Vollkommene Zahl : ".a);
else
print(Typeset,"unvollkommene Zahl : ".a);
end_if
Um andere vollkommene Zahlen zu erhalten ist oben ein anderer Wert für s zu wählen.
Wenn allerdings b keine Primzahl ist, ist die resultierende Zahl a nicht vollkommen.
2. Teil
Hier wird der Algorithmus ohne Berücksichtigung, ob die benötigten Exponenten s
Primzahlen sind durchlaufen. Das die potenziellen vollkommenen Zahlen a werden
berechnet. Anschließend wird überprüft. ob die Zwischenprodukte b Primzahlen sind
und damit die Zahlen a vollkommen sind. Die Ergebnisse werden in eine Matrix
geschrieben.
Die Ausgabematrix wird definiert und die benötigten Variablen werden zurückgesetzt.
Die Variable Ende gibt die Anzahl der Iterationen und damit die Anzahl der Zeilen
der Ausgabematrix an.
Ende:=10:
Ausgabe:=matrix(Ende,3):
delete a,b,k:
Die potenziellen vollkommen Zahlen werden nach dem oben angegebenen Algorithmus
und in die zweite Spalte der Ausgabematrix geschrieben. In der ersten Spalte der Aus-
gabematrix erscheint die Zahlnummer. Anschließend wird entsprechend dem in Teil 1
angegebenen Verfahren überprüft, ob die ermittelte Zahl Primzahl ist. Das Ergebnis
wird in die dritte Spalte der Ausgabematrix geschrieben.
for k from 2 to Ende + 1 do
b:=2^k-1;
a:=2^(k-1)*b;
Ausgabe[k-1,2]:=a;
Ausgabe[k-1,1]:="Zahl Nr ".expr2text(k-1);
Primzahltest:=testeq(nops(numlib::primedivisors(b))=1);
if Primzahltest = TRUE
then
Ausgabe[k-1,3]:=vollkommen
else
Ausgabe[k-1,3]:=unvollkommen;
end_if;
end_for:
Ausgabe
3. Teil
Probe auf Vollkommenheit
Letztlich gibt es drei Methoden, eine Zahl auf Vollkommenheit zu überprüfen:
1) Man überprüft die Vollkommenheit anhand der Definition. Dies wird ein dem
anderen Notebook zum Thema vollkommene Zahlen durchgeführt und hier nicht
weiter verfolgt.
2) Man erstellt eine Tabelle gerader vollkommener Zahlen und vergleicht die Probezahl
mit den Zahlen in der Tabelle. Kommt die Zahl in der Tabelle vor, ist sie vollkommen,
kommt die Zahl nicht vor, ist sie unvollkommen. Vorausgesetzt wird bei dieser
Methode, dass die Probezahl kleiner als die größte der vollkommenen Zahlen in der
Tabelle ist. Gegebenenfalls muss die Tabelle vor der Überprüfung um weitere voll-
kommene Zahlen ergänzt werden. Bei ungeraden Zahlen überprüft man, ob die Zahl
kleiner oder größer als 10^50 ist. Ist sie kleiner als 10^50 ist sie unvollkommen,
sonst ist eine Aussage nicht möglich.
3) Man berechnet für eine gegebene gerade Probezahl die Variable b und überprüft,
ob b Primzahl ist. Darüber hinaus überprüft man, ob s eine natürliche Zahl >= 2 ist.
Die Matrix für die Speicherung der Testergebnisse wird definiert. Ihre Zeilenzahl entspricht
der Anzahl der Iterationen.
Testergebnis:=matrix(Ende,1):
Die Probezahl ist die Zahl, die auf Vollkommenheit untersucht werden soll.
Probezahl:=6:
Die vorher berechneten potenziell vollkommenen Zahlen werden einzeln auf Vollkommenheit
überprüft. Dazu wird überprüft, ob erstens die Zahl in der Tabelle vorkommt und zweitens,
ob die Zahl vollkommen ist. Die Ergebnisse werden in die Testmatrix geschrieben.
for k from 1 to Ende do
a:=Ausgabe[k,2]:
b:=Ausgabe[k,3]:
Testergebnis[k,1]:=testeq(a=Probezahl)and
testeq(b=vollkommen)
end_for:
Die Testmatrix wird ausgegeben
Testergebnis
Die Einzelergebnisse werden zu einer Gesamtaussage zusammengefasst.
Gesamttestergebnis:=Testergebnis[1,1]:
for k from 2 to Ende do
Gesamttestergebnis :=Testergebnis[k,1]
or Gesamttestergebnis:
end_for:
Die Überprüfung liefert nur vollkommene Zahlen, wenn diese in der Tabelle vorkommen.
Insofern werden nur vollkommene Zahlen erfasst, die kleinergleich der größten in der Tabelle
vorkommenden vollkommenen Zahl sind. Das Gesamtergebnis der Überprüfung wird um
einen entsprechenden Check ergänzt und ausgegeben.
if Ausgabe[Ende,2] >= Probezahl
then
if Gesamttestergebnis = TRUE
then
print("die Zahl ".expr2text(Probezahl)." ist eine vollkommene Zahl")
else
print("die Zahl ".expr2text(Probezahl)." ist keine vollkommene Zahl")
end_if
else
print("Die Probezahl ist größer als die größte berechnete Zahl");
print("Eine Aussage über die Vollkommenheit ist daher nicht möglich")
end_if
"die Zahl 6 ist eine vollkommene Zahl"
Anschlussprobleme und offene Punkte:
1) Es sollte verhindert werden, dass andere als natürliche Zahlen zur Überprüfung auf
Vollkommenheit zugelassen werden.
2) Es sollte sichergestellt werden, dass für s nur natürliche Zahlen im Algorithmus
berücksichtigt werden können.
3) Ungerade Zahlen werden in der Überprüfung auf Vollkommenheit durch Vergleich
mit den Werten in der Tabelle automatisch als nicht vollkommen erkannt. Dies
Ergebnis ist jedoch nur für ungerade Zahlen < 10^50 richtig. Es ist nicht bekannt,
ob es größere ungerade vollkommene Zahlen gibt, die größer als 10^50 sind. Das
Notebook um eine entsprechende Überprüfung ergänzt werden.
4) In der Überprüfung auf Vollkommenheit scheint eine Redundanz zu sein. Einerseits
wird überprüft, ob die Zahl in der Tabelle vorkommt und zusätzlich wird überprüft,
ob diese Zahl vollkommen ist. Es sollte geklärt werden, welche Auswirkungen auf-
treten, wenn man je einen Teil der Doppelabfrage entfernt.
______________________________________________________________________________
Anmerkung:
1. Darstellungen des gewählten Algorithmus finden sich in vielen Büchern zur Zahlentheorie. Das vorliegende
Notebook bezieht sich auf die Darstellung in Remmert, Ulrich: "Elementare Zahlentheorie", 2. Auflage
Birkhäuser 1995.
2. Lösungen von Programmierproblemen im Rahmen der linearen Algebra und Analysis finden sich in weiteren
Notebooks des gleichen Autors.
3. In einem weiteren Notebook des Autors wird ein Algorithmus zur Berechnung von Primzahlen durchgeführt
und ausgewertet.
4. In einem weiteren Notebook des Autors wird eine weitere Möglichkeit zur Überprüfung einer Zahl auf
Vollkommenheit durchgeführt.
5. Weitere Aspekte der Anwendung von MuPAD auf die Zahlentheorie finden sich in zwei Notebooks des
gleichen Autors, die sich mit vollkommenen Zahlen beschäftigen.
6. Weitere Anregungen finden Sie in der Unterrichsmaterialsammlung unter schule.mupad.de. In diesen
Notebooks werden eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD Pro gelöst.
______________________________________________________________________________