Wie die Zahl mit den meisten Teilern finden?
Hallo,
wie kann ich am besten herausfinden, welche Zahl zwischen 1 und 230 die Zahl ist, die die meisten Teiler hat?
5 Antworten
Ich würde das so machen:
Wenn man wirklich verschiedene Primzahlen kombinieren will, fängt man natürlich erstmal mit den kleinsten an und merkt, dass
2*3*5*7 = 210, 2*3*5*7*11 = 2310 gilt.
Es ergibt sich somit, dass jede Zahl zwischen 1 und 230 maximal 4 verschiedene Primteiler haben kann, woraus 2^4 = 16 Teiler Folgen.
Nun kann man versuchen, Primteiler mehrmals vorkommen zu lassen. Da würde ich direkt mit dem Extremum anfangen, nur einen Primteiler zu verwenden, und zwar den kleinsten.
Es gilt 2^7 = 128, 2^8 = 256.
Es ergibt sich, dass jede Zahl zwischen 1 und 230 maximal 7 Primteiler insgesamt hat, woraus sich insgesamt 8 Teiler ergeben.
Wenn man eine Primfaktorzerlegung p1^(q1)*p2^(q2)...*pn^(qn) = x von x gegeben hat mit Primzahlen p und Exponenten q, kann man Kombinatorisch begründen, dass es (q1+1)*(q2+1)*..*(qn+1) Teiler gibt, da man für jede Primzahl die Möglichkeit hat, sie 0,1,...qp mal zu benutzen.
Es ist klar, dass man für jede neue Primzahl einen Faktor 2 gewinnt, für jede Primzahl, die bereits einmal vorgekommen ist erhöht man nur einen gegebenen Faktor um 1.
Aus (q+1) < q * 2 folgt, dass es sinnvoller ist, einen neuen Faktor hinzuzufügen, wenn man die größtmögliche Teilerzahl will.
Allerdings haben wir Anfangs gesehen, dass so eine Zahl maximal aus 4 verschiedenen Primfaktoren generieren kann. Wenn man zulässt dass sich Faktoren wiederholen kann man aber 7 Faktoren kombinieren.
Wir versuchen nun diese Funktion zu maximieren, also das perfekte Mittel aus Anzahl und "Wert" der Primfaktoren zu finden, der vermutlich irgendwo in der Mitte liegt, da wir einen kleinen Bereich 4 bis 7 haben, können wir das Problem lösen indem wir alle Möglichkeiten durchgehen.
Für 4 verschiedene bzw 7 gleiche kennen wir bereits die Anzahl der Teiler, 16 bzw 8.
Angenommen wir haben 5 Primteiler. Dann sind folgende Verteilungen möglich und es ergeben sich folgende Anzahl an Teilern:
-4 gleiche, eine einzelne Primzahl => 5*2 = 10
-3 gleiche, zwei einzelne => 4*2*2=16
-3 gleiche, 2 gleiche => 4*3 = 12
-zwei mal 2 gleiche, eine einzelne => 3*3*2=18
-2 gleiche, drei einzelne => 3*2*2*2 = 24
-5 gleiche => 6
Man sieht, dass hier 24 die größte Zahl ist. Wir versuchen eine Zahl zu Konstruieren, die diese Verteilung hat. Wir nehmen die kleinst mögliche, also
2*2*3*5*7=420 > 230. Dh es gibt keine Zahl in deinem Intervall mit dieser Zerlegung.
Analog machst du das jz auch noch für den Fall, dass du 6 Primteiler hast, was ich jetzt nicht gemacht habe, und dann versucht du eben die größte Zahl mit der gegebenen Teilerverteilung zu konstruieren. Für den Fall dass das die 18 bleibt mache ich das hier:
2*2*3*3*5 = 180 ist die kleinste Zahl mit dieser Verteilung. Gibt es eine andere?
Wenn wir die kleine Zahl, die 2, erhöhen, landen wir auf 3. Dann müssen wir die 3 aber auch erhöhen, womit wir auf der 5 landen, die wir dann auch erhöhen müssen, damit die Teilerverteilung erhalten bleibt.
Es folgt, dass 2*2*3*3*7 die nächstgrößere Zahl mit dieser Verteilung ist. Aber es gilt 2*2*3*3*7=252>230.
Somit ist 2*2*3*3*5 die einzige Zahl in deinem Intervall mit 18 Teilern.
Aber wie gesagt, du musst das gleiche nochmal für die Möglichkeit von 6 Primteilern machen
MfG
Edit: Ich habe den Fall 6 jetzt auch durchprobiert. Es finden sich natürlich Verteilungen mit mehr Teilern, allerdings gibt es keine Zahl kleiner 230 die eine dieser Verteilungen annimmt. Somit ist 180 tatsächlich die mit den meisten Teilern und sogar die einzige.
Man kann die Zahlen nach der Anzahl ihrer verschiedenen Primteiler untersuchen:
n = p^x1 q^x2 r^x2 s^x4
p, q, r, s verschiedene Primzahlen, x1 ... x4 ganze Zahlen > 0
Mehr als 4 braucht man nicht, und das scheidet auch schon aus, da 2x3x5x7 = 210 nur 16 Teiler hat.
Bei drei Primteilern probiert man 2^x1 3^x2 5^x3, du hast schon 2^2 3^2 5 = 180 mit 18 Teilern gefunden.
Bei 2 Primteilern probiert man 2^x1 3^x2. (x1+1) (x2+1) müsste grösser als 18 sein, da scheint nichts zu gehen.
Ein Primteiler: 2^7 = 128 mit 8 Teilern, das bringt's auch nicht.
Ich habe das nicht vollständig durchprobiert und wage aber mal den Tip, dass du mit 180 den richtigen Kandidaten gefunden hast.
Unterschiedliche Primfaktoren oder Teiler?
Für unterschiedliche Primfaktoren wäre das 2*3*5*7.
Du kannst aus der Zahl oben 16 verschiedene Teiler bauen.
Jeder Primfaktor kann da sein oder nicht da sein.
Also
2
3
2*3
5
2*5
3*5
Wenn Du Dir das überlegst, dann entspricht das einer Binärzahl
0001 ^= 2
0010 ^= 3
0011 ^= 2*3
0100 ^= 5
0101 ^= 5*3
etc.
1111 ^= 2*3*5*7
Die meisten Teiler oder die meisten verschiedenen Teiler?
bei ersterem hätte ich ohne es zu überprüfen auf die 128 getippt: 2*2*2*2*2*2*2
192 hat ebenso 7 Teiler.
Natürlich verschiedene Teiler. Jede natürliche Zahl hat unendlich oft den Teiler 1.
Damit ein Produkt von Primzahlen möglichst viele Teiler hat, müssen die Primzahlen verschieden sein. "Die meisten Teiler" besagt nichts anderes als "die meisten verschiedenen Teiler", denn wenn ich bei meiner Bestimmungsmethode der Teiler mehrfach auf denselben Teiler stoße, ändert sich dadurch ja nicht die Menge der Teiler! Schreibe ich die Menge der Teiler hin und wiederhole dabei welche, kann ich mir das auch schenken: Die Menge bleibt dieselbe. Die Zahl 4 hat genau drei (natürliche) Teiler - auch wenn ich den Teiler 2 doppelt hinschreibe. Die Zahl 6 dagegen hat genau vier Teiler.
Meine Frage war zwar zugegebnermaßen Blödsinn, aber natürlich erhöhen mir vielfach vorkommende Primzahlen in den Teilern auch die Teiler.
Beispiel: 16 = 2*2*2*2
hat als Primfaktoren nur den Teiler 2, als Teiler hat diese Zahl aber 1, 2, 4 (=2*2), 8 (=2*2*2) und 16 (=2*2*2*2).
Also: auch mehrere gleiche Primfaktoren erhöhen die Teilerzahl! (Wenn auch nicht im höchstmöglichen Ausmaß)
Ich habe aber bereits herausgefunden, dass die Zahl 180 18 Teiler hat, nur die Frage ist, wie komme ich darauf?
https://de.wikipedia.org/wiki/Eulersche_Phi-Funktion Das könntest du mit der eulerschen Phi Funktion überprüfen
Nein ich meine Teiler aber danke