Sieb des Eratosthenes

Bernhard

Registriertes Mitglied
Hallo zusammen,

ich beschäftige mich zur Zeit privat etwas mit der Programmierung des Siebes des Eratosthenes.

Allen Mathe- und Primzahl-Freunden wird das altbekannt sein, aber wer hat sich schon mal an die Programmierung desselben gewagt? Diejenigen, die das schon mal gemacht haben wissen, dass das recht schnell zu Speicherproblemen führen kann, wenn man damit auch Primzahlen mit mehr als zehn Stellen berechnen will.

Ein Blick auf den Pseudocode des WP-Artikels zeigt, dass auch dort von allen natürlichen Zahlen bis zum gewünschten Limit ausgegangen wird und das benötigt dann schnell auch sehr viel Speicher.

Meine Idee lautet nun, dass man die Startmenge an möglichen Zahlen vorab sinnvoll verkleinert. So kann man bei der Suche nach Primzahlen vorab trivialerweise alle geraden Zahlen streichen und reduziert damit die Größe des Siebes bereits um 50% !.

Das Sieb wird in diesem ersten Schritt also durch die Reihe

2 * n + 1

definiert, wobei n wieder in der Menge der natürlichen Zahlen größer oder gleich eins liegt.

Streicht man vorab die Vielfachen von 3, so erhält man nach relativ einfacher Rechnung die zwei Reihen:

6 * n + 1
6 * n + 5

wiederum mit n = 1, 2, 3, ...

streicht man weiter die Vielfachen von 5 erhält man die folgenden acht Reihen:

2*3*5 * n + 1
2*3*5 * n + 7
2*3*5 * n + 11
2*3*5 * n + 13
2*3*5 * n + 17
2*3*5 * n + 19
2*3*5 * n + 23
2*3*5 * n + 29

wiederum mit n = 1, 2, 3, ...

usw. und man erkennt dann auch, wie dieses Schema prinzipiell immer weiter fortgeführt werden kann. Man erhält auf diese Weise also immer bessere "übervollständige" Primzahlgeneratoren. Die D.h. die genannten Reihen produzieren immer alle Primzahlen, enthalten allerdings aber auch mehr oder weniger zusätzliche Zahlen, die nicht prim sind.

Über diese "Vorsiebung" kann man nun den benötigten Speicherplatz bei der Programmausführung für das vollständige Sieb stark reduzieren und ich würde nun gerne wissen, ob einer der Autoren oder Leser hier so etwas schon mal gemacht hat oder noch bessere Tricks zum Sieb des Eratosthenes kennt.
 

Bernhard

Registriertes Mitglied
Beschränkt man sich nur auf ungerade Zahlen kann man den Speicherbedarf eines Programmes bereits deutlich reduzieren (< 500 MB anstelle < 1GB) und kann innerhalb des Wertebereiches des Datentyps long (32 Bit) ohne nennenswerte Rechenzeit (< 1 Minute) immerhin alle Primzahlen < x = 1e9 berechnen.

Die komplizierteren Formeln bringen mMn keine nennenswerten Vorteile, weil das Programm dadurch deutlich unübersichtlicher wird und die Reduzierung von Speicherbedarf und Rechenzeit vergleichsweise gering bleiben.

Interessant erscheint mir dagegen die Berechnung der Primzahlfunktion für die Werte x >= 1e10. Dazu gibt es dann auch weiterführende Literatur, wie zB: https://primes.utm.edu/howmany.html
 
Zuletzt bearbeitet:

ralfkannenberg

Registriertes Mitglied
Interessant erscheint mir dagegen die Berechnung der Primzahlfunktion für die Werte x >= 1e10.
Halo Bernhard,

was Du hier machen kannst ist Zahlen mit Hilfe zweier Varialen zusammenzusetzen, d.h. die ersten 10 Stellen eines Primzahlkandidaten in einer Variablen und die anderen 10 Stellen in der anderen Variablen.

Dann musst Du zwar die vier Grundrechenarten selber programmieren, aber im Falle der Addition und Subtraktion ist das sehr einfach und bei der Division machst Du das eben so wie man von Hand dividiert, d.h. die nächste noch nicht berücksichtigte Stelle "hinunterziehen" und dann die "Zwischensumme" dividieren.

Ausserdem kann man, falls man aus irgendeinem Grunde gewisse Primzahlen immer wieder neu ermitteln muss, diese in einer Tabelle zwischenspeichern und dann nur die Tabelle durchgehen, das hat damals meine Berechnung wesentlich beschleunigt. Damals ging es mir um die Fragestellung, wie viele Primzahlen ich von einer geraden natürlichen Zahl abziehen kann und das Ergebnis ist jedesmal eine Nicht-Primzahl. Also konkret um die Funktion g(n) = kleinste gerade natürliche Zahl, von der man die ersten n Primzahlen subtrahieren kann und das Ergebnis ist eine Nicht-Primzahl.

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.


Freundliche Grüsse, Ralf
 

Bernhard

Registriertes Mitglied
Hallo Ralf,
was Du hier machen kannst ist Zahlen mit Hilfe zweier Varialen zusammenzusetzen, d.h. die ersten 10 Stellen eines Primzahlkandidaten in einer Variablen und die anderen 10 Stellen in der anderen Variablen.

Dann musst Du zwar die vier Grundrechenarten selber programmieren, aber im Falle der Addition und Subtraktion ist das sehr einfach und bei der Division machst Du das eben so wie man von Hand dividiert, d.h. die nächste noch nicht berücksichtigte Stelle "hinunterziehen" und dann die "Zwischensumme" dividieren.
interessant, aber mittlerweile geht das mMn einfacher, wenn man gleich in Python programmiert. Dort kann man direkt mit beliebig großen ganzen Zahlen rechnen, solange man ausreichend Speicher hat.

Damit kann man dann die Menge an Primzahlen sicher nochmal vergrößern, allerdings kommt dann auch die Frage, was man mit dieser Liste überhaupt anfangen kann.

Erstaunlich auf jeden Fall, wie mächtig das "alte Sieb" ist.

Ausserdem kann man, falls man aus irgendeinem Grunde gewisse Primzahlen immer wieder neu ermitteln muss, diese in einer Tabelle zwischenspeichern und dann nur die Tabelle durchgehen, das hat damals meine Berechnung wesentlich beschleunigt.
Klar. So eine Tabelle, bzw. Array wird auch schon beim Sieb des Eratosthenes benötigt. Will man möglichst viele Primzahlen berechnen, wird diese Tabelle dann schnell sehr groß, so dass erneut der verfügbare Speicher die Menge an Primzahlen begrenzt.

Damals ging es mir um die Fragestellung, wie viele Primzahlen ich von einer geraden natürlichen Zahl abziehen kann und das Ergebnis ist jedesmal eine Nicht-Primzahl. Also konkret um die Funktion g(n) = kleinste gerade natürliche Zahl, von der man die ersten n Primzahlen subtrahieren kann und das Ergebnis ist eine Nicht-Primzahl.
War das eine Übung, oder gibt es dafür eine weitere Anwendung?

BTW: Die Zahlen 2^n - 1 werden Mersenne-Zahlen genannt und werden bei der Berechnung sehr großer Primzahlen verwendet. Was bieten die Zahlen 2^n + 1? Gibt es dazu keinen effektiven Primzahltest?
 
Zuletzt bearbeitet:

ralfkannenberg

Registriertes Mitglied
Die Zahlen 2^n - 1 werden Mersenne-Zahlen genannt
Hallo zusammen,

hierzu gibt es eine schöne Anekdote über Frank Nelson Cole, die wir im Studium gelernt haben und die auch in der Wikipedia dokumentiert ist:

Im Jahre 1903 präsentierte er bei einem Treffen der American Mathematical Society in einem ungewöhnlichen Vortrag die Faktoren der Mersenne-Zahl 267-1 (kurz M67). Bereits 1876 hatte Édouard Lucas gezeigt, dass diese Zahl, entgegen der Angabe von Marin Mersenne, keine Primzahl ist. Primfaktoren dieser Zahl blieben aber unbekannt.

Bei seinem Vortrag ging Cole wortlos zur Tafel und berechnete den Wert von M67. Sodann schrieb er auf die andere Tafelseite die Aufgabe 193.707.721 · 761.838.257.287. Er führte die langwierige Multiplikation handschriftlich aus und zeigte am Schluss, dass beide Berechnungen zum gleichen Ergebnis von 147.573.952.589.676.412.927 führten. Ohne ein Wort gesprochen zu haben, ging Cole an seinen Platz zurück, während seine Kollegen aufstanden und ihm applaudierten.
Man muss sich das einmal vorstellen: da geht einer zur Tafel, spricht kein Wort und subtrahiert 1 von einer Zweierpotenz.

Danach geht er weiterhin wortlos zur anderen Tafelhälfte und multipliziert dort zwei Zahlen. Das ist übrigens Grundschulmathematik.

Ohne ein Wort gesprochen zu haben erhebt sich die gesamte Zuhörerschaft und spendet standing ovations, denn sie wissen natürlich ganz genau, was Cole in diesem Moment bewiesen hat, und natürlich haben sie schon vorher bereits nach der 1.Zeile geahnt, dass Cole das nun beweisen wird, was er dann auch tat.


Freundliche Grüsse, Ralf
 

Bernhard

Registriertes Mitglied
was Du hier machen kannst ist Zahlen mit Hilfe zweier Varialen zusammenzusetzen, d.h. die ersten 10 Stellen eines Primzahlkandidaten in einer Variablen und die anderen 10 Stellen in der anderen Variablen.
Hast Du das bei Deinem damaligen "Goldbach-Projekt" verwendet? Falls ja, waren die Zahlen also vermutlich auf 20 Stellen begrenzt.
 

Bernhard

Registriertes Mitglied
Ausserdem kann man, falls man aus irgendeinem Grunde gewisse Primzahlen immer wieder neu ermitteln muss, diese in einer Tabelle zwischenspeichern und dann nur die Tabelle durchgehen, das hat damals meine Berechnung wesentlich beschleunigt.
Zur Abschätzung der Größe einer solchen (Hilfs-)Tabelle ist wieder die Primzahlfunktion hilfreich.
 

Bernhard

Registriertes Mitglied
Man muss sich das einmal vorstellen: da geht einer zur Tafel, spricht kein Wort und subtrahiert 1 von einer Zweierpotenz.

Danach geht er weiterhin wortlos zur anderen Tafelhälfte und multipliziert dort zwei Zahlen. Das ist übrigens Grundschulmathematik.
In diesem Vortrag waren sicher fast ausnahmlos echte Zahlenfreunde anwesend.

Die genannte Primfaktor-Zerlegung von M(67) schafft ein kurzes Python-Script heute in maximal einer Minute Rechenzeit.
 
Zuletzt bearbeitet:

ralfkannenberg

Registriertes Mitglied
Hast Du das bei Deinem damaligen "Goldbach-Projekt" verwendet? Falls ja, waren die Zahlen also vermutlich auf 20 Stellen begrenzt.
Lieber Bernhard,

wir haben damals auf dem Apple II mit PASCAL programmiert und der Datentyp INTEGER ging bis 2^15 - 1, also bis 32767 :)


Freundliche Grüsse, Ralf
 
Zuletzt bearbeitet:

ralfkannenberg

Registriertes Mitglied
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
 

Bernhard

Registriertes Mitglied
Hallo Ralf,
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.
 

Bernhard

Registriertes Mitglied
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?
 

astrofreund

Registriertes Mitglied
Das waren noch Zeiten ... :eek:

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/python-335-primfaktorzerlegung-und-potenzschreibweise.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
 

ralfkannenberg

Registriertes Mitglied
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.
 
Zuletzt bearbeitet:

ralfkannenberg

Registriertes Mitglied
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.
 
Zuletzt bearbeitet:

Bernhard

Registriertes Mitglied
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.
 

Bernhard

Registriertes Mitglied
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/
 
Oben