Gesetzmäßigkeiten für die Anzahl der Teiler einer Zahl - 14.06.2005

Ich habe vor einiger Zeit begonnen mich aus Spaß und dem Drang etwas neues zu entdecken :) für die Anzahl an Teilern, die eine Zahl hat zu interessieren. Irgendwann kam ich zu der Frage, ob es möglich sei, die erste (also kleinste) Zahl zu finden, die eine bestimmte Anzahl an Teilern hat.

habe ich z.B n=4, so ist m=6 die erste Zahl mit n Teilern (1,2,3,6).
Ziel meiner Überlegungen und Tests war es natürlich Regeln zu finden und so diese Zahl m Vorraussagen zu können.
So schrieb ich mir ein Programm, welches alle Zahlen durchtestete und notierte mir das ganze. Das ging so wie ich es mir vorstellte, bis n=23. Dort eine Zahl m zu finden dauerte ungewöhnlich lange. Letztendlich wurde die Zahl bei 2^22 gefunden. Die Regel die man daraus ableiten konnte:

m = 2n-1

traf aber nur auf bestimmte Zahlen zu, die ich letztendlich als Primzahlen identifizieren konnte.

Sei n also eine Primzahl, findet man m über m=2^n-1.

Im Umkehrschluss bedeutet das auch, dass jede Zahl p^x mit p als Primzahl genau x+1 Teiler hat.

Nach reichlich weiterer Überlegung kam ich auch zu einer Vorgehensweise für jede andere Zahl n.
Zuerst viel mir auf, dass bei Nichtprimzahlen für n der Wert von m stets durch 3 teilbar war und durch irgendein Vielfaches der 3:

m = 3x * 2p-1

Zunächst war mir der Aufbau des "x" unklar und man konnte es nur über Durchtesten rausfinden. Später viel mir aber auf, dass es die nachfolgenden Primzahlen (also 5,7, 11 usw.) enthält. Letztendlich kam ich zu der Erkenntnis, dass man n in seine Primfaktoren zerlegen muss und dann das erste Glied der Primfakultät mit dem höchsten Primteiler der Zahl n reduziert um eins potenzieren muss, dann das 2. Glied der Primfakultät mit dem zweitgrößten Primteiler (-1) usw. bis zum n. Glied der Primfakultät mit dem kleinsten Primteiler (-1) der Zahl n.

Bsp: n = 30 = 2*3*5 m = 25-1 * 33-1 * 52-1 = 24 * 33 * 5 = 720 Also: k=Anzahl der Primteiler der Zahl n q(k)=größter Primteiler der Zahl n q(k-1) = 2. größter Primteiler der Zahl n usw. q(1) = kleinster Primteiler der Zahl n P(k) = k-te Primzahl n = q(1) * q(2) * ... * q(k) m = 2q(k)-1 * 3q(k-1)-1 * ... * P(k-1)q(2)-1 * P(k)q(1)-1

Das funktioniert perfekt. Für jede Zahl wird tatsächlich ein m gefunden, das n Teiler hat. Was ja so sein muss, da die Potenzen der Primzahlen es eben so erzeugen.

Das Problem ist nun, dass es doch nicht für alle Zahlen n tatsächlich das kleinste m liefert. Sie haben alle die Form

n = 2 * ... * 2 * p = p * 2x

Wobei p eine zusammengesetzte Zahl sein kann.
Ich habe auch bereits vor einiger Zeit diese Anomalie erklärt, kann aber meine Aufzeichnungen gerade nicht finden und werde das später ergänzen!

Es hing zusammen mit der kleinsten Zerlegung oder so. Muss ich mal ausprobieren ^^


Zurück zur Übersicht