Sieb des Eratosthenes

16/11/2008 - 17:28 von Juli_München | Report spam
Hallo, ich bin dieser Gruppe beigetreten, weil mich eine Frage schon
das gesamte Wochenende bewegt. Ich habe mich die Woche über aus purem
Hobby ein wenig mit Primzahlen beschàftigt und bin dann Freitag auf
eine Frage gestoßen die folgendermaßen lautet.

1. Mit dem Sieb des Eratosthenes die Primzahlen bis 144 bestimmen.
Dabei soll mit nur mit 6 Spalten gearbeitet werden (--> letzte Zahl
einer Zeile ist Vielfaches von 6)

2. Nachdem man Vielfache von 13 gestrichen hat sind einige Zeilen
komplett gestrichen (die Zeilen beginnen mit 91, 115 und 121)

3. Würde man die "Tabelle" in Gedanken über 144 hinaus erweitern,
würden weitere Zeilen auch schon komplett wegfallen. Welche sind das?
Das ganze soll aber geschehen, ohne das man die Tabelle weiterführt,
sondern mit minimalem Aufwand.

1. und 2. habe ich mit Leichtigkeit gelöst, bei 3. zerbreche ich mir
den Kopf seit Freitag. Ich vermute, dass es etwas damit zu tun hat,
dass man jede Primzahl als Vielfaches von 6+/-1 darstellen kann (6k
+/- 1) und den Primzahlzwillingen.

Hat jemand eine einfache und schnelle Lösung?
 

Lesen sie die antworten

#1 Jan Fricke
16/11/2008 - 18:07 | Warnen spam
Juli_München wrote:
Hallo, ich bin dieser Gruppe beigetreten, weil mich eine Frage schon
das gesamte Wochenende bewegt. Ich habe mich die Woche über aus purem
Hobby ein wenig mit Primzahlen beschàftigt und bin dann Freitag auf
eine Frage gestoßen die folgendermaßen lautet.

1. Mit dem Sieb des Eratosthenes die Primzahlen bis 144 bestimmen.
Dabei soll mit nur mit 6 Spalten gearbeitet werden (--> letzte Zahl
einer Zeile ist Vielfaches von 6)

2. Nachdem man Vielfache von 13 gestrichen hat sind einige Zeilen
komplett gestrichen (die Zeilen beginnen mit 91, 115 und 121)

3. Würde man die "Tabelle" in Gedanken über 144 hinaus erweitern,
würden weitere Zeilen auch schon komplett wegfallen. Welche sind das?
Das ganze soll aber geschehen, ohne das man die Tabelle weiterführt,
sondern mit minimalem Aufwand.

1. und 2. habe ich mit Leichtigkeit gelöst, bei 3. zerbreche ich mir
den Kopf seit Freitag. Ich vermute, dass es etwas damit zu tun hat,
dass man jede Primzahl als Vielfaches von 6+/-1 darstellen kann (6k
+/- 1) und den Primzahlzwillingen.

Hat jemand eine einfache und schnelle Lösung?


Nein.

Das liegt daran, dass die Entscheidung, ob weder 6k+1 noch 6k+5 eine
Primzahl ist, genauso schwer ist wie die Frage, ob eine Zahl der Form
6k+1 eine Primzahl ist.
Allerdings kann man konkret die Zeilen angeben, in denen z.B. die eine
Zahl durch 5 und die andere durch 7 teilbar ist. (Konkret sind das die
Zeilen, die mit 6*(35*l+15)+1 und 6*(35*l+19)+1 anfangen.)
Außerdem sagt der Satz von Dirichlet, dass asymptotisch die Hàlfte aller
Primzahlen die Form 6k+1 hat. Somit ist die "Wahrscheinlichkeit", dass
die Zeile mit dem Anfang 6k+1 wegfàllt, etwa 1-6/ln(k).

Viele Grüße Jan

Ähnliche fragen