+6 Daumen
4,9k Aufrufe

ich sitze gerade an dem Problem, die kleinste natürliche Zahl z mit mehr als n Teilern zu bestimmen.

Die kleinste natürliche Zahl mit genau n Teilern kann man z.B. so finden:

n = 38,  38 = 2 * 19,  z = 2^{18} * 3 = 786432

n = 132,   132 = 2 * 2 * 3 * 11,   z = 2^{10} * 3^2 * 5 * 7 ) = 322560

 

Die Sache wird schwieriger, wenn die kleinste natürliche Zahl mit mehr als n Teilern zu finden.

z.B. mit n = 125,  125 = 5^3,  z = 2^4 * 3^4 * 5^4 = 810000 hat 125 Teiler.

Aber 83160 = 2^3 * 3^3 * 5 * 7 * 11 hat 128 Teiler, also mehr als n = 125, ist aber kleiner als 810000.

 

Danke,

Thilo

Avatar von 4,3 k
Hm ... ich weiß es nicht. Klingt aber interessant.

Ich würde erstmal alle Primzahlen ausschließen, die Zahl als gerade deklarieren und behaupten, dass die Zahl größer als deine bisherigen Versuchsergebnisse ist. Das Ganze natürlich den PC erledigen lassen :-) In den Algorithmus könntest du ja alle Teilbarkeitsregeln einarbeiten. 7 ist doof und durch 6 teilbar wäre gut, zum Beispiel ... ;-)

1 Antwort

+1 Daumen

ich habe die Frage hier vor einiger Zeit gesehen und mir ein paar Überlegungen dazu gemacht. Eine fixfertige Antwort habe ich leider noch nicht. Konkret stellte ich mir die Frage nach der kleinsten natürlichen Zahl mit mehr als 1000 Teilern. Ich vermute, dass man diese Zahl erhält, wenn man das Produkt der ersten 10 Primzahlen bildet, also  N = 2*3*5*7*11*13*17*19*23*29 = 6'469'693'230 . Man kann sich leicht klar machen, dass N genau 210 = 1024 Teiler besitzt, also mehr als 1000.

Ich weiß aber (noch) nicht, ob man nach demselben Rezept auch im Allgemeinen durchkommt. Falls ja, könnte man sogar eine ganz einfache Formel für die kleinste Zahl N mit mehr als T Teilern angeben, nämlich:

$$ N\quad =\quad \prod _{ i=1 }^{ imax }{ { p }_{ i } } $$

wobei $$ imax\ =\ \left \lfloor \frac{ln(T)}{ln(2)}\right \rfloor+1$$

Avatar von

Leider liefert meine angegebene Formel doch nicht unbedingt die kleinste Zahl N mit mehr als T Teilern, sondern nur eine (oft wohl recht gute) obere Schranke für die gesuchte kleinste Zahl.

Nimmt man zum Beispiel T=7 (sucht man also die kleinste Zahl mit mehr als 7 Teilern), so liefert meine Formel die Zahl N = p1*p2*p3 = 2*3*5 = 30 . Tatsächlich hat die Zahl 30 genau 8 Teiler, aber dies trifft auch schon auf die kleinere Zahl 24 = 23*31  zu .

Das ist eine sehr gute Frage! Das wüsste ich auch gerne

30 = 2^1 * 3^1 * 5^1 besitzt genau (1+1)*(1+1)*(1+1)=8 Teiler.

24 = 2^3 * 3^1 besitzt genau (3+1)*(1+1)=8 Teiler.

Es gibt also einen Zusammenhang zwischen der Zerlegung einer Zahl in Primpotenzen und ihrer Teileranzahl. Das kann man ausnutzen. Die kleinste Zahl n mit genau t=1001 Teilern etwa bekommt man so:

(1) t = 1001 = 13*11*7 = (12+1)*(10+1)*(6+1)
(2) n = 2^12 * 3^10 * 5^6 = 3779136000000

Andere Möglichkeiten wie etwa

(1') t = 1001 = 143*7 = (142+1)*(6+1)
(2') n = 2^142 * 3^6 = 4064310812432206067544884655190163884464930816

liefern größere Zahlen.


Die Zahl \(245044800 = 2^6 \cdot 3^2 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13 \cdot 17\) hat 1008 Teiler.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community