Sieb von Ulam / Eratosthenes < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:32 Do 02.12.2010 | | Autor: | Tappys |
Hi,
ich habe zwei Aufgaben, die ich irgendwie nicht so richtig hinbekomme.
a) Bei dem Sieb von Ulam (6 Spalten, man fängt mit 1 an)
Wenn man mit 5 "siebt", dann liegen die Zahlen die man streicht auf parallelen Geraden.
b) Bei dem Sieb von Erathoshenes (10 Spalten, man fängt mit 1 an)
Wenn man mit einer Primzahl p, die echt größer als 2 ist siebt, dann kann man mit p² beginnen und in Schritten von 2p voran schreiten.
Meine Überlegungen:
Also bei a) da habe ich mir ein Bild gemalt und es sofort gesehen. Ich würde so argumentieren, da 5 eine Primzahl ist hat sie keinen kleineren Teiler, also wird nur in 5er Schritten gestrichen. Und da wir 6 Spalten haben erhalten wir eine Diagonale anordnung der Streichungen (das ist kein richtiger Beweis) Ich glaube, dass ich es verstehe, ich weiß aber nicht wie ich es ausformulieren kann.
b) Hier weiß ich nicht was ich zu tun habe, irgendwie kann ich das nicht so richtig glauben.
Ich hoffe jemand kann mir bei meinen Problemen helfen.
LG
Tappys
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Tappys, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
die erste Aufgabe hast Du nicht richtig verstanden, und die zweite ist einfacher, als Du offenbar denkst.
> Hi,
> ich habe zwei Aufgaben, die ich irgendwie nicht so richtig
> hinbekomme.
> a) Bei dem Sieb von Ulam (6 Spalten, man fängt mit 1 an)
> Wenn man mit 5 "siebt", dann liegen die Zahlen die man
> streicht auf parallelen Geraden.
>
> Meine Überlegungen:
> Also bei a) da habe ich mir ein Bild gemalt und es sofort
> gesehen.
Das kann ich mir kaum vorstellen. Das Streichverfahren ist ein ganz anderes als bei Eratosthenes. Das Sieb von Ulam geht auf das ![[]](/images/popup.gif) Josephus-Problem zurück und verallgemeinert es. Ziel ist es, die sogenannten Glücklichen Zahlen zu ermitteln.
Im ersten Schritt wird jede 2. Zahl gestrichen, also alle geraden Zahlen. Im zweiten Schritt wird jede dritte Zahl der noch nicht gestrichenen Zahlen gestrichen, also die 5,11,17,23,29,35,41,47 etc.
Zu diesem Zeitpunkt können wir sicher sagen, dass die 1 und die 3 nie mehr gestrichen werden, und mit wenig Überlegung können wir die 7 auch schon so einordnen.
Es stehen nun also noch 1,3,7,9,13,15,19,21,25,27,31,33,37,39,43,45,49,51,55,57,61,63,67,69,73,75,
79,81,85,87 etc.
Nun wird jede vierte Zahl gestrichen, also 9,21,33,45,57,69,81,93 etc.
Dass auch die 13 eine "glückliche Zahl" ist, wissen wir damit auch.
Und nun ist die Frage, wie man jede fünfte der noch stehenden Zahlen charakterisieren kann.
Noch gibt es 1,3,7,13,15,19,25,27,31,37,39,43,49,51,55,61,63,67,73,75,
79,85,87,91,97 etc.
Gestrichen werden also 15,37,55,75,97,115,135,157,175,195 usw.
Das ist die fünfte Streichung und damit die zu untersuchende.
Die Aufgabe ist ungeschickt gestellt, da es mehrere Lösungen gibt.
Am leichtesten zu zeigen ist die Anordnung der Streichkandidaten auf nur zwei Geraden, nämlich denen, die in der ersten und dritten Spalte verlaufen.
> Ich würde so argumentieren, da 5 eine Primzahl
> ist hat sie keinen kleineren Teiler, also wird nur in 5er
> Schritten gestrichen. Und da wir 6 Spalten haben erhalten
> wir eine Diagonale anordnung der Streichungen (das ist kein
> richtiger Beweis) Ich glaube, dass ich es verstehe, ich
> weiß aber nicht wie ich es ausformulieren kann.
Dann wäre die Aufgabe ziemlich langweilig, weil Deine Regel für jede Zahl gelten würde, nicht nur die 5.
> b) Bei dem Sieb von Erathoshenes (10 Spalten, man fängt
> mit 1 an)
> Wenn man mit einer Primzahl p, die echt größer als 2 ist
> siebt, dann kann man mit p² beginnen und in Schritten von
> 2p voran schreiten.
>
> b) Hier weiß ich nicht was ich zu tun habe, irgendwie
> kann ich das nicht so richtig glauben.
Du sollst nicht glauben, sondern prüfen.
Alle Vielfachen von p, die kleiner sind als [mm] p^2 [/mm] (und größer als p), sind durch einen anderen Faktor <p teilbar und also bereits gestrichen.
Dann wird behauptet, dass Schritte von 2p genügen, also nur noch Zahlen der Form [mm] p^2+2mp [/mm] gestrichen werden.
Eigentlich müsste die Schrittweite (so die Anweisung des Erathostenes) aber p betragen. Allerdings müssen bereits gestrichene Zahlen ja nicht noch einmal gestrichen werden.
Die Frage reduziert sich also darauf, ob für [mm] m\in\IN [/mm] bereits alle Zahlen der Form [mm] p^2+(2m-1)p [/mm] gestrichen worden sind.
Dazu ein Tipp: da p>2 sein muss, ist $ p=2k+1,\ [mm] k\in\IN [/mm] $.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:24 Fr 03.12.2010 | | Autor: | Tappys |
Hi reverend,
erstmal vielen Dank für deine Antwort und dass du mich im Matheraum willkommen geheißen hast.
Ich habe Aufgabe a gerade versucht, sehe aber ehrlich gesagt noch keine Parallelen mit "Abstand" 5. Ich habe gesehen, dass die Zahlen, die beim Schritt in dem man die 5te Zahl siebt in der ersten und der dritten Spalte sind, aber irgendwie finde ich das komisch, dass man so siebt...
Hoffe einer kann mir eine Erklärung dafür liefern, warum sie auf parallelen mit "Abstand" 5 liegen. Ich habe ja nach dem streichen nur noch die beiden Spalten.
LG
Tappys
|
|
|
| |
|
Hallo Tappys,
das klingt sehr danach, als hättest Du die Lösung eigentlich bereits, ohne aber zu sehen, dass es sich um die Lösung handelt.
> Hi reverend,
> erstmal vielen Dank für deine Antwort und dass du mich im
> Matheraum willkommen geheißen hast. 
>
> Ich habe Aufgabe a gerade versucht, sehe aber ehrlich
> gesagt noch keine Parallelen mit "Abstand" 5.
Die gibt es auch nicht. Auch die Aufgabe behauptet das nicht.
> Ich habe
> gesehen, dass die Zahlen, die beim Schritt in dem man die
> 5te Zahl siebt in der ersten und der dritten Spalte sind,
![[ok]](/images/smileys/ok.gif "[ok]")
> aber irgendwie finde ich das komisch, dass man so siebt...
Na, so ist das Sieb des Ulam halt definiert. Das kann man komisch finden, aber es wirft eine interessante Aufgabe auf, von der Du einen kleinen Teil hier lösen sollst.
> Hoffe einer kann mir eine Erklärung dafür liefern, warum
> sie auf parallelen mit "Abstand" 5 liegen.
Das tun sie nicht.
> Ich habe ja nach
> dem streichen nur noch die beiden Spalten.
Bingo. ![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]") Du hast nur die Spalten mit den Zahlen 6k+1 und 6k+3. Kannst Du denn zeigen, dass bei den ersten drei Streichungen alle anderen, also die mit [mm] n\equiv 0,2,4,5\mod{6} [/mm] komplett gestrichen werden? Dann wärst Du schon fertig.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:48 Fr 03.12.2010 | | Autor: | Tappys |
Hi reverend,
danke nochmal
> Na, so ist das Sieb des Ulam halt definiert.
Ich glaube ich habe einen Riesenfehler gemacht. Wir sollen zeigen, dass wenn man das Sieb von Eratosthenes benutzt und 6er Spalten benutzt, dass dann die Anordnung der Zahlen die man mit 5 siebt auf parallelen Geraden (mit "abstand" 5) liegen.
Mein denkfehler war, dass ich dachte das Sieb des Ulam wäre das Sieb des Eratosthenes mit 6 Spalten.
Also bin ich wieder bei meinem urspünglichen Problem.
Sorry, dass ich für meine Blödheit deine Zeit verplämpert habe. Vielleicht kannst du mir noch ein letztes Mal helfen.
LG
Tappys
|
|
|
| |
|
Hallo nochmal,
> Ich glaube ich habe einen Riesenfehler gemacht. Wir sollen
> zeigen, dass wenn man das Sieb von Eratosthenes benutzt und
> 6er Spalten benutzt, dass dann die Anordnung der Zahlen die
> man mit 5 siebt auf parallelen Geraden (mit "abstand" 5)
> liegen.
Sicher?
> Mein denkfehler war, dass ich dachte das Sieb des Ulam
> wäre das Sieb des Eratosthenes mit 6 Spalten.
Nein, die haben nichts miteinander zu tun und funktionieren unterschiedlich.
> Also bin ich wieder bei meinem urspünglichen Problem.
> Sorry, dass ich für meine Blödheit deine Zeit
> verplämpert habe. Vielleicht kannst du mir noch ein
> letztes Mal helfen.
Wenn die Aufgabe jetzt so richtig ist, ist sie ein bisschen langweilig. Denn es ist egal, ob man mit 5 siebt oder mit einer anderen zur Spaltenzahl teilerfremden Zahl. Um ehrlich zu sein, sind sogar dann parallele Geraden auszumachen, wenn die Streichungsweite nicht einmal teilerfremd zur Spaltenzahl ist.
Für die 5 ist es am hübschesten zu zeigen, wenn Du Dir den ganzen Zahlenblock nimmst und in geeigneter Weise duplizierst und daneben legst, unendlich oft... Dabei heißt "in geeigneter Weise" im wesentlichen nichts weiter als eine "Höhenverschiebung". Dann werden die Geraden auch unendlich lang, jedenfalls wenn man das ganze noch auf die ganzen Zahlen erweitert. Sonst bekommt man eben keine Geraden, sondern nur Strahlen.
Mach doch mal 'ne Skizze. 
Begründen kann mans übrigens gut mit Modulrechnung, falls Ihr die schon hattet.
Grüße
reverend
|
|
|
|
