Difference between revisions of "MR 06 Loesung R"
(New page.) |
m |
||
| Line 1: | Line 1: | ||
Ich nenne die Anzahl der Stellen s, die Zahl n hat also eine Dezimaldarstellung aus s Ziffern mit dem Wert z. | Ich nenne die Anzahl der Stellen s, die Zahl n hat also eine Dezimaldarstellung aus s Ziffern mit dem Wert z. | ||
| − | Für <math>z > 1</math> ist n durch z teilbar und daher keine Primzahl, ab jetzt gilt daher <math>z=1</math>. | + | 1. Für <math>z > 1</math> ist n durch z teilbar und daher keine Primzahl, ab jetzt gilt daher <math>z=1</math>. |
Wir betrachten daher Zahlen der Form <math>n=(10^s - 1)/9</math>, sie werden als [https://de.wikipedia.org/wiki/Repunit repunits] (repeated units) | Wir betrachten daher Zahlen der Form <math>n=(10^s - 1)/9</math>, sie werden als [https://de.wikipedia.org/wiki/Repunit repunits] (repeated units) | ||
zur Basis 10 bezeichnet. Für die Basis 2 gibt es ja Primzahlen der Form <math>2^s - 1</math>, sie sind | zur Basis 10 bezeichnet. Für die Basis 2 gibt es ja Primzahlen der Form <math>2^s - 1</math>, sie sind | ||
nach [https://de.wikipedia.org/wiki/Mersenne-Zahl Marin Mersenne] benannt. | nach [https://de.wikipedia.org/wiki/Mersenne-Zahl Marin Mersenne] benannt. | ||
| − | Die Ziffernsumme hat den Wert s, wenn sie durch 3 teilbar ist, gilt das auch für n, es muss also | + | 2. Die Ziffernsumme hat den Wert s, wenn sie durch 3 teilbar ist, gilt das auch für n, es muss also |
<math>s \equiv \pm 1 \pmod{3}</math> gelten. | <math>s \equiv \pm 1 \pmod{3}</math> gelten. | ||
| − | Die Zifferndifferenz hat den Wert 0 wenn s gerade und 1, wenn s ungerade ist. Weil Zahlen mit der Zifferndifferenz | + | 3. Die Zifferndifferenz hat den Wert 0 wenn s gerade und 1, wenn s ungerade ist. Weil Zahlen mit der Zifferndifferenz |
Null durch 11 teilbar sind, kommen nur ungerade Zahlen für s in Frage (der Fall s=2 wird ja schon ausgeschlossen). | Null durch 11 teilbar sind, kommen nur ungerade Zahlen für s in Frage (der Fall s=2 wird ja schon ausgeschlossen). | ||
Zusammen mit 2 ergibt sich daher, dass s ≡ ±1 (mod 6) sein muss, um Vielfache von 3 und 11 auszuschließen. | Zusammen mit 2 ergibt sich daher, dass s ≡ ±1 (mod 6) sein muss, um Vielfache von 3 und 11 auszuschließen. | ||
| + | <!-- Drüber muss ich noch einmal nachdenken. | ||
| + | Die folgende Überlegung zeigt, dass nur Primzahlen für die Stellenzahl s in Frage kommen: wenn <math>s=p\cdot q</math> zusammengesetzt ist, kann man n faktorisieren: | ||
| + | <math>\displaystyle n=\frac{10^{pq}-1}{9}=(10^{p}-1)\cdot\sum_{k=0}^{q-1} 10^{kp}</math> --> | ||
| − | Eine kurze Suche liefert | + | Eine kurze Suche liefert die Primzahlkandidaten s=19 und s=23, die entsprechenden Zahlen bestehen probabilistische Primzahltests, |
ich bin ziemlich sicher, dass es sich bei den repunits | ich bin ziemlich sicher, dass es sich bei den repunits | ||
<math>(10^{19} - 1) / 9</math> und <math>(10^{23} - 1) / 9</math> | <math>(10^{19} - 1) / 9</math> und <math>(10^{23} - 1) / 9</math> | ||
Revision as of 23:53, 10 February 2018
Ich nenne die Anzahl der Stellen s, die Zahl n hat also eine Dezimaldarstellung aus s Ziffern mit dem Wert z.
1. Für ist n durch z teilbar und daher keine Primzahl, ab jetzt gilt daher . Wir betrachten daher Zahlen der Form , sie werden als repunits (repeated units) zur Basis 10 bezeichnet. Für die Basis 2 gibt es ja Primzahlen der Form , sie sind nach Marin Mersenne benannt.
2. Die Ziffernsumme hat den Wert s, wenn sie durch 3 teilbar ist, gilt das auch für n, es muss also gelten.
3. Die Zifferndifferenz hat den Wert 0 wenn s gerade und 1, wenn s ungerade ist. Weil Zahlen mit der Zifferndifferenz Null durch 11 teilbar sind, kommen nur ungerade Zahlen für s in Frage (der Fall s=2 wird ja schon ausgeschlossen).
Zusammen mit 2 ergibt sich daher, dass s ≡ ±1 (mod 6) sein muss, um Vielfache von 3 und 11 auszuschließen.
Eine kurze Suche liefert die Primzahlkandidaten s=19 und s=23, die entsprechenden Zahlen bestehen probabilistische Primzahltests, ich bin ziemlich sicher, dass es sich bei den repunits und um Primzahlen handelt.
In einem meiner Lieblingsbücher, Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity (Englisch) von Manfred Schroeder werden solche repunits besprochen, damals (ca. 1989) war noch nicht bekannt, ob die Zahl prim ist, ich habe vor etlichen Jahren viel Rechenzeit verwendet, um das zu überprüfen und habe ein positives Ergebnis bekommen.
