Anzeige
Seite 2 von 7 ErsteErste 1234 ... LetzteLetzte
Ergebnis 11 bis 20 von 65

Thema: Sieb des Eratosthenes

  1. #11
    Registriert seit
    16.09.2005
    Beiträge
    8.740

    Standard

    Anzeige
    Zitat Zitat von Bernhard Beitrag anzeigen
    In diesem Vortrag waren sicher fast ausnahmlos echte Zahlenfreunde anwesend.

    Die genannte Primfaktor-Zerlegung von M(67) schaftt ein kurzes Python-Script heute in maximal einer Minute Rechenzeit.
    Hallo Bernhard,

    das war das Treffen der American Mathematical Society im Jahre 1903.


    Freundliche Grüsse, Ralf

  2. #12
    Registriert seit
    12.11.2005
    Beiträge
    5.491

    Standard

    Hallo Ralf,
    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    das war das Treffen der American Mathematical Society im Jahre 1903.
    ja, Danke. Ich hab's im zugehörigen WP-Artikel auch gefunden.

    M(67) ist insofern interessant, als dass die beiden Primzahl-Faktoren sehr groß sind und relativ nahe an der Quadratwurzel der Zahl liegen. Das macht die Zerlegung natürlich schwer und erstaunlich, dass man das ohne Computer überhaupt finden konnte.
    Freundliche Grüße, B.

  3. #13
    Registriert seit
    12.11.2005
    Beiträge
    5.491

    Standard

    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    Praktisch war auch, dass - da ich ja die kleinste von denen gesucht habe - ich an der Uni alle verfügbaren Rechner über das Wochenende in benachbarten Zahlenintervallen laufen lassen konnte, das ganze so abgeschätzt, dass meine Berechnungen am Montag früh um 6 Uhr abgeschlossen waren, damit dann die ersten Studenten nicht blockiert waren. Die Ergebnisse habe ich in einer Datei verspeichert und diese dann am Montag in der Mittagspause ausgedruckt. Somit ergaben sich verschiedene Kandidaten für g(n) und der absolut-kleinste war dann die gesuchte Zahl. Hierbei ist noch anzumerken, dass bei grösseren Zahlen pro Zehnerpotenz vielleicht 3 Hits zu erwarten sind, d.h. mit einer Ausnahme war jedesmal die gefundene Zahl schon das gesuchte Minimum, und in den allermeisten Fällen gab es keine Hits.
    Gratulation zu dem sicher spannenden und rechenintensiven Projekt. War das vom Uni-Personal genehmigt (vermute ich mal) oder eher privates Engagement?
    Freundliche Grüße, B.

  4. #14
    Registriert seit
    18.04.2016
    Ort
    Dresden
    Beiträge
    483

    Standard

    Das waren noch Zeiten ...

    Heute auf i9 (8Core) Intel-PC mit 5,2 GHz (von 3,5 GHz hoch) schafft es das #1-Python-Programm von https://trainyourprogrammer.de/pytho...reibweise.html unter Win10/64-Bit zum

    Ergebnis für die Zahl 147573952589676412927
    [193707721, 761838257287]
    193707721 ** 1
    761838257287 ** 1

    Das Programm lief 38.724287700000 s
    Das Programm lief 38724.287699999993 ms
    Das Programm lief 38724287.699999988079 us

    Da ist nix mehr mit mal einen Kaffee trinken gehen ...

    Gruß, Astrofreund
    "Der Krieg ist gewonnen - aber nicht der Friede."
    Albert Einstein Botschaft an die Nobel-Gedenkfeier in New York, 19. Dezember 1945

  5. #15
    Registriert seit
    16.09.2005
    Beiträge
    8.740

    Standard

    Zitat Zitat von Bernhard Beitrag anzeigen
    Gratulation zu dem sicher spannenden und rechenintensiven Projekt. War das vom Uni-Personal genehmigt (vermute ich mal) oder eher privates Engagement?
    Hallo Bernhard,

    ich hatte schon länger mit immer leistungsfährigeren Maschinen daran gearbeitet und die meisten meiner Studienkollegen nannten diese Zahlen nicht "Goldbach-Zahlen" - streng genommen sind es "Nicht-Goldbach-Zahlen", sondern "Kannenberg-Zahlen".

    Einmal konnte ich eine leistungsstarke Maschine auf der UNIX mit Cayley nutzen, um Untergruppen für eine Semsterarbeit zu bestimmen, und als das durch war habe ich meinen Account für diese Goldbach-Zahlen genutzt.

    Man kann übrigens ganz einfach zeigen, dass g(n) für jedes n eine Lösung hat; die grosse Kunst ist nur, dass diese Lösung möglichst klein sein muss und das ist sie halt nicht. Könnte ich das beweisen -> Fields-Medaille. Immerhin habe ich "gesehen", dass der Logarithmus der Primzahlen etwa 3x kleiner ist als der Logarithmus der Goldbach-Zahlen. Könnte ich das beweisen -> Fields-Medaille.

    Meine Aktivitäten auf der UNIX hätten damals tatsächlich fast zu meiner Account-Sperre geführt, wobei ich als Hilfs-Assistent (zwischen 5. und 8.Semester kann man Hilfsassistent werden und das war ich für Lineare Algebra und für Informatik) durchaus gewisse Privilegien in Anspruch nehmen konnte. Leider - dafür hatte auch ich Verständnis - haben meine Berechnungen während eines Wochenendes alle Doktoranden blockiert und dafür musste ich dann am nachfolgenden Montag zusammen mit einem Studienkollegen beim Oberassistenten antraben.

    Was war passiert ? - Das Problem war, dass man auf UNIX verschiedene CPU-Prioritäten eingeben konnte und für solche Sachen sollte man die unterste Priorität nutzen. Nur: da bekam man am Wochenende dann vielleicht 3 CPU-Sekunden zusammen und das war völlig unbrauchbar. Ich habe das einige Male probiert, völlig zwecklos. Also hat man die höchste Priorität genommen.

    Nun war es so, dass mehrere Studienkollegen von meinen Berechnungen mitbekommen haben und einer hat es dann auch selber programmiert. Fairerweise muss man sagen, dass wir beide uns nicht sonderlich gut mit diesen Prioritäten auskannten, wir waren eigentlich nur Anwender, die eine Semesterarbeit absolviert haben. Am Freitag abend haben wir also unsere Batches gestartet, natürlich ist gar nix passiert. Also habe ich meinen Batch 3x gestartet, weil ich dachte, dass ich irgendetwas falsch gemacht habe, und habe dann kapituliert und bin zu meinen Eltern nach Deutschland gefahren, es war ja schon Freitag abend.

    Dass mein Studienkollege auch zwei solche Jobs gestartet hat wusste ich nicht, und bei seinen ist natürlich auch nix passiert, so dass auch er nach Hause gefahren ist.

    Am Samstag sind dann meine Jobs - alle drei in höchster Priorität - angelaufen, erst der erste, der dann nach Ablauf der maximalen Rechendauer vom System gecancelled wurde, dann der zweite, der dann ebenfalls gecancelt wurde und tief in der Nacht zum Sonntag dann der dritte. Nachdem dieser gecancelled war war der erste Job meines Studienkollegen an der Reihe und schliesslich als dieser gecancelled war sein zweiter, inzwischen war es Montag morgen. Kurz und gut: 5x liefen am Wochenende unsere Berechnungen, die dann allesamt gecancelled wurden und die Doktoranden waren total blockiert.

    Zum Glück - es würde fast besser in den anderen Thread passen, hatte mein Studienkollege eine Semesterarbeit über den Rubiks-Cube - da kann man ja auch Untergruppen bestimmen, und er meinte, da müsse in seinem Programm ein "bedauerlicher" Programmierfehler passiert sein, weswegen das nun so passiert sei.

    Ich habe dann später noch einmal einen Lauf in hoher Priorität versucht, aber der Oberassistent wollte sofort wissen, was da los war, so dass ich den Job gecancelled habe. Diese UNIX war also für solche rechenintensiven Berechnungen nicht geeignet, und dann bekam ich von einem Informatiker den Tipp mit den Liliths. Von denen habe ich dann auch zahlreiche Tipps zur Optimierung meiner Berechnung erhalten, und ich habe auch immer meine Ergebnisse im Computerraum ausgehängt. - Zwar musste ich dafür Modula-2 lernen, aber ok - als PASCAL-Programmierer war das nicht so schwer und würde dann auch später ganz nett in meinem Lebenslauf aussehen.

    Es war eine wirklich nette Zeit, fast schon eine "Collaboration", obwohl es dieses Wort damals noch gar nicht gab.

    Aufgehört habe ich zum einen, weil dann Prüfungen anstanden, und zum anderen, weil ich einmal den Beweis eines einfachen Primzahlresultates, welches wir bei Übungsaufgaben unbewiesen nutzen durften, gesehen habe: trotz des einfachen Resultates war dieser 6 Seiten lang und ich habe fast nichts verstanden. Mir wurde damals bewusst, dass der Beweis oder die Widerlegung der Goldbach'schen Vermutung alles andere als einfach ist und es dafür jemanden braucht, der weltweit theoretisch führend ist und nicht jemanden, der das mit Rechenpower zu erledigen versucht und darauf hofft, "etwas" zu sehen. Kommt hinzu, dass Primzahlen auch nicht mein Hauptinteressensgebiet waren, es war vielmehr die Möglichkeit, mit leistungsfähigen Rechnern arbeiten zu können, die mich antrieb.


    Aber ja - es war eine "geile Zeit".


    Freundliche Grüsse, Ralf


    P.S. die Fields-Medaille entspricht dem Nobelpreis für Mathematik und damals erfüllte ich die Bedingung, unter 40 Jahre alt zu sein, ich war ja noch deutlich jünger als 30 Jahre alt.
    Geändert von ralfkannenberg (10.01.2022 um 14:25 Uhr)

  6. #16
    Registriert seit
    16.09.2005
    Beiträge
    8.740

    Standard

    Zitat Zitat von astrofreund Beitrag anzeigen
    Da ist nix mehr mit mal einen Kaffee trinken gehen ...
    Hallo Astrofreund,

    dazu habe ich auch eine Story, da war ich aber schon berufstätig und dieses Mal ist meine Mutter "schuld". Das ging damals so weit, dass sie um eine Aufgabe zu lösen den gesamten Wohnzimmertisch mit Kärtchen vollgelegt hat und mein Vater meinte, sie solle doch nachts schlafen statt neue Ideen von mir zu lösen.

    Es gibt da ein Problem von Newton (?), welches erst in den 1960-iger Jahren gelöst wurde.

    Das 4x4 Problem ist einfach, kann man mit einem Kartenspiel machen und das habe ich damals an einem Heiligen Abend unter (genauer: vor) dem Weihnachtsbaum meiner Eltern gelöst.

    Man nehme also 16 Karten eines Kartenspiels, z.B. Bube, Dame, König und Ass in den vier Farben (z.B. Kreuz, Pik, Herz und Karo) und lege die in einem Quadrat so hin, dass pro Reihe und pro Spalte jede Farbe genau einmal vorkommt und jeder Wert genau einmal vorkommt.

    Natürlich gibt es da viele Symmetrien, z.B. wenn man eine Lösung um 90° dreht ist das immer noch eine Lösung, oder wenn man zwei Zeilen vertauscht oder zwei Spalten einer Lösung vertauscht, so hat man immer noch eine Lösung. - Man kann also beispielsweise die 1.Reihe widerspruchsfrei, aber ansonsten beliebig auswählen und auch noch irgendwie die 1.Karte der 2.Reihe - danach wird es dann eindeutig.

    Na schön, beim 4x4-Problem gibt es bis auf diese Symmetrien 2 Lösungen. Doch was ist mit dem analogen nxn-Problem ?

    Und da ist es eben so, dass es ausser für 2x2 (trivial) und 6x6 immer Lösungen gibt. Und der Beweis, dass es für 6x6 keine Lösung gibt wurde erst in den 1960-iger Jahren gefunden.

    Ein Beweis, der erst so spät gefunden wurde ist also sehr schwer.


    Das hat mich gewundert, denn das "riecht" doch nach einem Backtracking-Algorithmus, den ich dann also programmiert habe: man gibt die erste Reihe und die 1.Karte der 2.Reihe vor und probiert dann einfach die übrigen Reihen durch. Sobald sich ein Widerspruch ergibt geht man ein Feld zurück und probiert die nächste freie Karte u.s.w. Wenn man eine Lösung gefunden hat nimmt man dann einfach ab den 2.Feld der 2.Reihe die nächste Karte und macht weiter, um die übrigen Lösungen zu bestimmen.

    Ok, ich habe das also progrmmiert und dann mal laufen lassen.

    3x3 ging schneller als ich sehen konnte.
    4x4 ging schneller als ich sehen konnte.
    5x5 dauerte etwa eineinhalb Minuten.

    Nun wurde es spannend: 6x6 ...

    Nichts geschah.

    Ok, ich habe das Programm über die Mittagspause laufen lassen. Das Programm lief immer noch.

    Ok, am Abend über Nacht. Das Programm lief immer noch.

    Ok, Freitag abend über das Wochenende. Das Programm lief immer noch.

    Also gut: den 2.Wert der 2.Reihe fest vorgeben und wieder Freitag abend über das Wochenende. Das Programm lief immer noch.

    Dann schätzte ich die Laufzeit mal ganz grob ab.


    Was würdet Ihr denken, wie lange das Programm brauchte: eine Woche, einen Monat, ein Jahr, länger ?

    Nochmal:
    3x3 ging schneller als ich sehen konnte.
    4x4 ging schneller als ich sehen konnte.
    5x5 dauerte etwa eineinhalb Minuten.


    Freundliche Grüsse, Ralf


    P.S.: der klassische Beispiel eines Backtracking-Algorithmus sind die 8 Damen auf dem Schachbrett, die sich gegenseitig nicht schlagen.
    Geändert von ralfkannenberg (10.01.2022 um 14:47 Uhr)

  7. #17
    Registriert seit
    12.11.2005
    Beiträge
    5.491

    Standard

    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    Was würdet Ihr denken, wie lange das Programm brauchte: eine Woche, einen Monat, ein Jahr, länger ?

    Nochmal:
    3x3 ging schneller als ich sehen konnte.
    4x4 ging schneller als ich sehen konnte.
    5x5 dauerte etwa eineinhalb Minuten.
    Das sieht für mich nach einer Alternative zur Weizenkornlegende aus. Also vermutlich sehr sehr lange, d.h. mehr als ein Jahr.

    Ist aber nur so ein Bauchgefühl, weil ich das eigentliche Problem nicht kenne.
    Freundliche Grüße, B.

  8. #18
    Registriert seit
    16.09.2005
    Beiträge
    8.740

    Standard

    Zitat Zitat von Bernhard Beitrag anzeigen
    Das sieht für mich nach einer Alternative zur Weizenkornlegende aus. Also vermutlich sehr sehr lange, d.h. mehr als ein Jahr.

    Ist aber nur so ein Bauchgefühl, weil ich das eigentliche Problem nicht kenne.
    Hallo Bernhard,

    es kam mir damals zugute, dass ich die Zahl "10^17 Sekunden" kannte

    Die Rechendauer steigt mit dem Quadrat der Fakulät !


    Freundliche Grüsse, Ralf

  9. #19
    Registriert seit
    12.11.2005
    Beiträge
    5.491

    Standard

    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    Zum Glück - es würde fast besser in den anderen Thread passen, hatte mein Studienkollege eine Semesterarbeit über den Rubiks-Cube - da kann man ja auch Untergruppen bestimmen, und er meinte, da müsse in seinem Programm ein "bedauerlicher" Programmierfehler passiert sein, weswegen das nun so passiert sei.
    Danke für den spannenden Beitrag.

    Passend zum Zitat gibt es diese Seite: http://www.cube20.org/
    Freundliche Grüße, B.

  10. #20
    Registriert seit
    12.11.2005
    Beiträge
    5.491

    Standard

    Anzeige
    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    es kam mir damals zugute, dass ich die Zahl "10^17 Sekunden" kannte
    Über den Daumen gepeilt entspricht das dem Alter des Universums.

    Da muss man also schon wirklich viel Geduld mitbringen .
    Freundliche Grüße, B.

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •  
astronews.com 
Nachrichten Forschung | Raumfahrt | Sonnensystem | Teleskope | Amateurastronomie
Übersicht | Alle Schlagzeilen des Monats | Missionen | Archiv
Weitere Angebote Frag astronews.com | Forum | Bild des Tages | Newsletter
Kalender Sternenhimmel | Startrampe | Fernsehsendungen | Veranstaltungen
Nachschlagen AstroGlossar | AstroLinks
Info RSS-Feeds | Soziale Netzwerke | Flattr & freiwilliges Bezahlen | Werbung | Kontakt | Suche
Impressum | Nutzungsbedingungen | Datenschutzerklärung
Copyright Stefan Deiters und/oder Lieferanten 1999-2013. Alle Rechte vorbehalten.  W3C