Primfaktoren von extrem großer Zahl berechnen

Question

ich soll mit Unterstützung von Computer-Algorithmen die ersten 40 Primfaktoren der Repunit R( 10⁹ ) bestimmen. Eine Repunit-Zahl besteht nur aus Einsen, und zwar besteht R( n ) aus n hintereinanderstehenden Einsen. Also z.B. R( 3 ) = 111, R( 7 ) = 1111111, R( 10⁹ ) = 1111111111111111111111111111....

R( 10⁹ ) ist also immens groß mit seinen 10⁹ Ziffern. Normale algorithmische Primfaktorzerlegung schließe ich daher aus, die größte bekannte Primzahl hat nichteinmal annähernd so viele Ziffern.

Ich weiss, dass aus a | n => R( a ) | R( n ). Teiler von 10⁹ sind z.B. 2, 3, 5, 8, 10, 16, ... Da 2 | 8 => R( 2 ) | R( 8 ), also hat R( 8 ) alle Primfaktoren, die auch R( 2 ) hat, d.h. die 11. Ich hatte in meinem Algorithmus so weiterverfahren mit allen Teiler von 10⁹. Aber trotzdem bleiben die unfaktorisierten Reste der R( n ) viel zu groß, um sie weiter zu faktorisieren.

Insgesamt kriege ich mit diesem Verfahren ca. 60 Primfaktoren von R( 10⁹ ) heraus, aber das sind nicht die ersten 40...

Weiss jemand zu helfen? Ich habe nirgends andere Eigenschaften von Repunit-Zahlen gefunden, die ich noch nutzen könnte.

 

Danke,

Thilo

Answer 1

die Primfaktorzerlegung von $10^9$ ist

$10^9 = 5^9 2^9$,

das heißt $2$ und $5$ sind jeweils $9$-fache Primfaktoren der Zahl $10^9$. Die Zahl $10^9$ hat also $100 - 2 =98$ Teiler ($1$ und $10^9$ sind keine echten Teiler von $10^9$).

$R(2) = 11$ ist eine Primzahl. $R(5) = 11.111$ hat die Zerlegung

$11.111 = 41 \cdot 271$.

Ich würde vorschlagen, jetzt alle möglichen Kombinationen $k_i$ von $2$ und $5$ durchzugehen ($i = 1, \dots, 98$) und in den $R_i \equiv R(k_i)$ nach neuen Primfaktoren der Zahl $R(10^9)$ zu suchen.

Z.B. $2$, $5$, $2^2$, $2 \cdot 5$, $5^2$, $2^3$, $2^2 \cdot 5$, $2 \cdot 5^2$, etc. $\dots$.

MfG

Mister

PS: Der Unterschied zu deinem Verfahren ist lediglich, dass ich zunächst die minimalen Primfaktorzerlegungen betrachte und nicht Potenzen der $2$ ($2, 4, 8, 16, \dots$) oder der $5$ ($5, 25, \dots$) gesondert durchgehe. Durch diese Minimalitätsforderung sollte sich die Minimalitätseigenschaft eigentlich auch auf die $R(k_i)$ vererben (intuitive Überlegung).

Comments

Die Idee find ich gut.

---

Danke. Ja, so hatte ich es auch gemacht. Aber ist leider immernoch viel zu langsam. Bei R( n ) mit n > 2000 dauert es ewig, auch wenn ich nur die ersten 1000 Primzahlen auf Primzahleigenschaft überprüfe. Also entweder ich brauche einen sehr schnellen Faktorisierungsalgorithmus, wie das quadratische Sieb, was ich aber schwer zu implementieren finde, oder die R( n ) haben noch irgendwelche Eigenschaften, die man ausnutzen kann... Ich werde mal weiterrecherchieren ^^

---

Für kleine $a$ lassen sich die Zahlen $R(a)$ doch aber noch relativ leicht faktorisieren. Da du aber nun nur die ersten $40$ Primfaktoren von $R(10^9)$ suchst, ist der Rechenaufwand vielleicht überschaubar.

Problematisch ist die Formulierung der "ersten" Primfaktoren, sind damit beliebige paarweise verschiedene Primfaktoren gemeint oder sind die $40$ kleinsten Primfaktoren der Zahl $R(10^9)$ gesucht? Sind diese desweiteren gemäß ihrer Vielfachheit zu zählen oder sollen sie paarweise verschieden sein?

---

Es gibt ja schon für diverse Primzahlen Teilbarkeitsregeln.

Ich denke da z.B. an. 

Eine Zahl ist genau dann durch 41 teilbar, wenn ihre nichtalternierende 5er-Quersumme durch 41 teilbar ist.

Ich denke mir mit solcher Regel ist das sehr einfach R(10⁹) auf Teilbarkeit zu überprüfen.

die 5er quersumme ist 5 

wir brauchen 10⁹ / 5 = 200 Millionen Quersummen davon.

macht also zusammen 1 Milliarde. Da das nicht durch 41 teilbar ist ist R(10⁹) auch nicht durch 41 teilbar.

Kann man nicht solche Teilbarkeitsregeln rechnergestützt herausfinden und damit einfach die Teilbarkeit der Repunit-Zahlen untersuchen oder denke ich da gerade viel zu einfach? 

---

Jede nichtalternierende Quersumme der Zahlen $R(n)$ ist gleich der Stellenanzahl von $R(n)$, die wiederum durch $n$ selbst gegeben ist.

Deinen vorletzten Absatz verstehe ich nicht: Du meinst, es gilt $a \not\mid n \Rightarrow a \not\mid R(n)$?

Sowohl die Division mit Rest als auch die Quersummenberechnung $10^9$-stelliger Zahlen ist übrigens relativ zeitaufwändig. Die Probedivision ist also keine Option. Ich glaube auch, darin liegt die Essenz der Aufgabe: Dass über eine bestimmte Eigenschaft der Zahl eine Vereinfachung der Aufgabe gefunden wird, die sich algorithmisch dann handhaben lässt.

---

Ah klar. Weiß schon wo ich den Denkfehler hatte.

---

Ja, danke für die Hilfe :P Inzwischen habe ich es mit einer weiteren Eigenschaft von Repunits geschafft. Habe das allerdings nicht ganz und gar verstanden.

Also es gilt ja nach Fermats kleinem Satz: $$a^{ p -1 } \equiv 1 mod p$$. Setze a = 10, dann ist $$10^{ p - 1 } \equiv 1 mod p \Leftrightarrow 10^{ p - 1 } - 1 \equiv 0 mod p$$. Klammert man die 9 aus, dann ist $$9 \cdot \frac{10^{ p - 1 } - 1}{ 9 } \equiv 0 mod p$$, also $$9 \cdot R( p - 1 ) \equiv 0 mod p$$. Sprich für p >= 7 gilt p | R( p - 1 ).

Nun zum Teil den ich nicht mehr so ganz verstanden habe:

Wenn bei der Reihe der R( n ) der Primfaktor p zum ersten Mal in R( k ) auftritt, muss k Teiler von p - 1 sein, also $$p \equiv 1 mod k$$. Also soll man bei der Primteilersuche von R( k ) nur noch nach Primteilern der Form r * k + 1 suchen müssen. Habe ich nicht wirklich verstanden.

Jedenfalls habe ich algorithmisch von den R( k ) die Zahlen r * k + 1 bis zu einer oberen Grenze mit dem Miller-Rabin-Primzahltest auf prim überprüft, wobei k natürlich immer Teiler von 10⁹ war. Und dann per Divisionstest, ob sie auch Primfaktoren von R( k ) sind. Sind sie Primfaktoren von R( k ), dann auch von R( 10⁹ ). So habe ich die ersten 40 Primfaktoren von R( 10⁹ ) in unter einer Minute berechnet.