22: Plätzchenexplosion / Cookie Explosion

  • Ich habe mal mit einem Programm die letzten 20 Ziffern von unserer Maximalzahl berechnet:

    Code
    1. 2*2^^6 endet in 83652555014874857472.
    2. Für n>=22 endet 2*2^^n in 97230150706865897472.

    Die untere Zahl ist für mehr als 3 belegbare Felder, da man dann am Ende 2*2^^(irgendwas Riesiges) hat.

  • Damit kein falscher Ton in die Diskussion kommt:..

    nicht doch, Ce1, ich hoffe, das hat auch niemand so verstanden...


    Aber zurück zum Thema: Stichwort WESTKOMA. Wegen der Frage, ob man sich die Zahl 2*2↑↑6 nicht doch irgendwie plausibler vorstellen könnte, als durch unmögliche Notation ihrer Ziffern auf sämtlichen Atomen dieser Welt (wie MatheJürgen ja schon illustrierte) oder eine nicht enden wollende Konstruktionen auf dem Schachbrett (bei der nur ein verschwindend kleiner Teil der Plätzchen, die auf das sechste Feld zu liegen kommen, jemals wieder angefasst werden würde) oder die Unanschaulichkeit einer abstrakten mathematischen Notation. Generell scheint in dieser Hinsicht erst mal jede noch so feine gleichmäßige Einteilung des Raum-Zeit-Kontinuums aussichtslos.


    Aber zum Glück gibt es da ja auch noch die Weihnachtssternkopiermaschine. Diese wurde bekanntlich genau 24 Lichtjahre / Fröhlich-Schallgeschwindigkeit (1 nach der Entdeckung des Ymasiums entworfen und kopiert einfach nur Weihnachtslicht. Weihnachtslicht ist eine harmonische Mischung von positiver und negativer Energie (konkreter: von Freude/Besinnlichkeit/Adventsknobeleien und Stress/Konsumrausch/Familienstreitigkeiten) und entzieht sich aufgrund von 2 / (1/E + 1/-E) jeglicher Art von Materialisierbarkeit und damit möglicher Widersprüche mit aktuell-physikalischen Thesen. Ein simpler Weihnachtsstern besteht aus sechs entlang der Raumachsen angeordneten Zacken, die je eine dieser Grundenergien ausstrahlen. WESTKOMA kopiert nun in einem Kopiervorgang Miniaturkopien des Originalsterns auf die Zacken des Originals. Das Licht der entsprechenden Originalzacke wird dabei komplett gleichmäßig in die zugehörige Miniaturkopie eingemischt.


    Ein solcher Kopiervorgang dauert gerade mal eine Sekunde. Die Kopie wird nun wieder kopiert, dann die Kopie der Kopie usw. Gegen Ende eines durchschnittlichen 20h-Lichtwichtel-Arbeitstages kann dieser dann das entstandene höchst fragile Gebilde versehentlich fallenlassen :/ und entprechend viele Zacken aufsammeln, die nur aus Freude und Adventsknobeleien bestehen.


    --------------------

    (1 Diese ist anscheinend tatsächlich nirgends in der Wikipedia erwähnt: Die Fröhlich-Schallgeschwindigkeit ist die nach dem Astrowissenswichtel und Vulkanologen Alexander Fröhlich benannte Ausbreitungsgeschwindigkeit von Weihnachtsklängen im Quasi-Vakuum.

  • Niemals bestimmen lassen sich alle Stellen dieser Zahl.

    Selbst "nur" die eine MITTLERE Stelle... Und einmal dabei, mich wundert's, dass noch keiner nach den ersten Stellen gefragt hat ...

  • Ich muss bei der Aufgabe irgendwie auch an die Türme von Hanoi denken, bei denen es ja heißt, dass die Welt untergehe, wenn die Mönche in einem indischen Kloster einen Turm von 64 Scheiben nach den entsprechenden Regeln verschoben haben - was selbst bei einer Scheibe, die pro Sekunde verschoben wird, lange genug dauern wird, dass sich die nächsten Generationen da keine Gedanken machen müssen.

    Und ähnlich sieht es ja auch mit den Plätzchen für die Rentiere aus. Schließlich muss das Spiel ja auch erst mal in der Praxis durchgespielt werden - ich lese jedenfalls in Rudolphs Aussagen nichts davon, dass sie das nur theoretisch durchrechnen wollen, da ist immer von konkreten Aktionen die Rede. Da kann der Weihnachtsmann also schon mal beim Auszahlen etwas bremsen. Und die Rentiere sind mit ihren Hufen ja auch nicht sooo geschickt, wenn es um das filigrane Verschieben von schnell wachsenden Plätzchentürmen über Schachbrettfelder geht.

    Ob die Rentiere und der Weihnachtsmann sich diesbezüglich noch irgendwie einig werden, oder ob die das Spiel tatsächlich durchspielen, werden wir wohl im Dezember sehen - in letzterem Fall wird der Mathekalender wohl Geschichte sein, weil Weihnachtsmann und Rentiere nur noch Plätzchen verschieben und somit Weihnachten in Zukunft ausfällt... ;)

  • Selbst "nur" die eine MITTLERE Stelle... Und einmal dabei, mich wundert's, dass noch keiner nach den ersten Stellen gefragt hat ...

    Also: ich habe jetzt ein kleines Programm geschrieben, das mir die knapp 20000 Stellen von 2^^5 berechnet. (Ist schon ein ziemliches Monstrum, wenn man sie mal so komplett vor sich sieht! Begriffe, wie "endlich" und "endliche Menge" bekommen ein ganz anderes Gewicht, obwohl man rein theoretisch weiß, dass es solche Zahlen gibt und noch beliebig viel größere, natürlich, aber dennoch ...)


    Die Zahl habe ich dann mit log10(2) (32 Stellen genau) malgenommen, dann 10^die Nachkommastellen, in der Hoffnung, damit die ersten Stellen von 2^^6 zu bekommen. Geklappt hat's, fürchte ich, nicht. Bin mir aber auch in dieser negativen Hinsicht nicht sicher.

    Wie macht's der Profi?

    (Ich frage ganz jungfräulich, habe noch keine Internet- oder sonstige Recherche betrieben.)

  • Mein Ansatz war wohl einigermaßen naiv, da die fehlenden Stellen bei log(2) natürlich die frühen Nachkommastellen des Produkts beeinflussen.


    Die Frage bleibt: Wie ermittelt man die ersten Stellen dieser Riesen, speziell 2^^6 ? Man kennt doch diese ersten Stellen, oder etwa nicht?


    (Allerdings hatte ich auch noch nie von diesen Themen gehört (Graham, TREE(3), ...), (von Busy Beaver-Alg. hatte ich immerhin schon mal gehört). Dabei benutzt man doch ständig Google, und die haben ihren Namen nach dem Begriff Googol gebildet, woraus sich die (nicht zu ernst zu nehmende) Googology gebildet hat.

    So hat dieser Kalender für eine gewisse Weiterbildung gesorgt! Sehr schön!)

  • .Wie macht's der Profi?

    :) Als Profi fühle ich mich jetzt zwar nicht direkt angesprochen, eher als gestandener Dillettant und Amateur (im Sinne von dilletare=erfreuen, amare=lieben).


    Als erstes mal die Erklärung, warum dein Ansatz so nicht klappt. x1=2^65536 und x2=2^65536+6 haben natürlich auf viele(!!) Dezimalstellen übereinstimmend so ziemlich den gleichen Wert für log(x) / log(10) ~ 65536 * log(2)/log(10). Dennoch ist 2x2 = 64 * 2x1, d.h. 2x1 hat eine andere Anzahl von Stellen und komplett andere Ziffern als 2x2


    EDIT: Ah, sehe grad, dass Du's auch schon gemerkt hast. Diesmal warst Du schneller :)

    EDIT2 Aeehm, sogar schon vor ein paar Stunden. Komisch, ist mir irgendwie entgangen. Sorry. Vermutlich habe ich nur gesehen: "letzter Post von Ce1" und dachte, aha hat sich seitdem nichts geändert...


    So sehr ich Python generell als auch speziell für solche mathematischen Fragestellungen sehr gern verwende (1, so möchte ich diese Gelegenheit gleich auch noch mal nutzen, für algebraische und zahlentheoretische Berechnungen verschiedenster Art PARI/GP zu empfehlen (2.


    Die letzten 20 Stellen unserer Zahl, ist in GP nicht mehr als ein:

    ? 2*Mod(2,10^20)^2^65536

    %1 = Mod(83652555014874857472, 100000000000000000000)


    Mod(x,m) bezeichnet dabei die Restklasse x(modulo m). Alle Stellen von 2^65536 lassen sich ebenso einfach ausgeben.

    ? print(2^2^2^2^2)

    20035299...(mehrere Bildschirme voller Ziffern)...19156736


    Für die ersten Stellen helfen Restklassen natürlich nicht weiter. Hier hatte ich ja schon die WESTKOMA erwähnt, also 65536-maliges Quadrieren unter Extra-Auswertung des 10er-Exponents. Das ginge ähnlich auch zB. in Python, hier aber trotzdem mal zur Illustration das Codestück in GP.


    Code
    1. \\ gives an idea of 2*2^pow
    2. huge( pow=2^16 ) = {
    3. my( t=0, ar=Mod(2,10^20), a=2. );
    4. for( i=1,pow, a*=a; ar*=ar; t*=2; if(a>=10,a/=10;t+=1) );
    5. a*=2; ar*=2; if(a>=10,a/=10;t+=1);
    6. printf( "%d...(%.5e digits)...%020d\n\n", floor(a*10^19), t-40, lift(ar) );
    7. }

    ? huge()

    11035890206151685072...(6.03123 e19727 digits)...83652555014874857472


    Und zuguterletzt noch das Beispiel 2^^22 von GraphZahl oben. Da alles in GP von Haus aus schon vorbereitet ist, muss es nur noch zusammengepackt werden.


    Code
    1. \\ calculates 2^^h mod 2^n*5^m
    2. tower( h, n=10, m=n ) = {
    3. if( h==1, return( Mod(2,2^n*5^m) ) );
    4. my( k=2 ); for( i=2,h, if( k>=n, k=0; break ); k=2^k );
    5. k = Mod(k,2^n);
    6. if( m==0, return(k) );
    7. return( chinese( k, Mod(2,5^m) ^ lift(tower( h-1, 2, m-1)) ) );
    8. }

    ? 2*tower(22,20)

    %3 = Mod(97230150706865897472, 100000000000000000000)


    Wenngleich das ja nur einen winzigen Bruchteil des Gesamtsystems überhaupt tangentiert, hat das die Stärken von GP sicher schon mal eindrucksvoll demonstriert.

  • So sehr ich Python generell als auch speziell für solche mathematischen Fragestellungen sehr gern verwende (1, so möchte ich diese Gelegenheit gleich auch noch mal nutzen, für algebraische und zahlentheoretische Berechnungen verschiedenster Art PARI/GP zu empfehlen (2.

    Für einen Nicht-Profi kennst Du Dich aber immerhin ziemlich gut aus - scheint mir.


    In das Loblied auf Python kann ich nur einstimmen. Habe viel in dieser Sprache programmiert. Sehr geschmeidig, sehr elegant, interessante und intelligente Konzepte (yield z.B.), dabei nicht übermäßig komplex, eine Unmenge von tollen Paketen (von denen ich - natürlich! - nur ein paar benutzt habe, vor allem numpy, pandas, matplotlib, Datenbankzugriff und ein paar weitere). Dazu ein bequemer Zugriff auf C-Bibliotheken, und eine Möglichkeit, die Sprache zu erweitern. Ich habe auch viel Zeit damit verbracht, die Interna der CPython-Implementation mit Hilfe des Visual Studios zu studieren. Sehr spannend und sehr erhellend!

    Was sollte man an Python verbessern?

    Was sagte doch Dennis Ritchie auf die Frage, was er an C verbessern würde: Er würde nun die Funktion creat doch lieber mit e schreiben: create. :)

    Was sollte man an Python verbessern? Vielleicht auf die Einrücklogik verzichten und statt dessen in guter C-Manier mit geschweiften Klammern arbeiten?!

    (Für Programmieranfänger allerdings finde ich den Einrückzwang gut. Ich hatte mal eine russische Schülerin, die alle ihre Programme entgegen oft wiederholten Ermahnungen linksbündig eingegeben hat. Dabei war sie programmiertechnisch durchaus begabt. Eine Folter, solche Programme zu lesen!)

    Aber von dieser und ein paar anderen Kleinigkeiten abgesehen, eine tolle Sprache. Kein Wunder, denn Guido van Rossum ist doch Mathematiker, oder täusche ich mich?


    PARI/GP kenne ich leider nicht. Werde ich mir jetzt mal ansehen. Den Algorithmus zum 65536-fachen Quadrieren muss ich mir noch angucken, kann mir kaum vorstellen, dass ... naja, wir werden sehen.

  • So, vielleicht noch ein letztes Mal (gibt ja noch andere Themen!):


    Zu Umu: Du hast folgende PARI/GP-Prozedur verwendet, um die ersten und letzten Stellen zu berechnen und auszugeben:


    \\ gives an idea of 2*2^pow

    huge( pow=2^16 ) = {

    my( t=0, ar=Mod(2,10^20), a=2. );


    for( i=1,pow, a*=a; ar*=ar; t*=2; if(a>=10,a/=10;t+=1) );

    a*=2; ar*=2; if(a>=10,a/=10;t+=1);

    printf( "%d...(%.5e digits)...%020d\n\n", floor(a*10^19), t-40, lift(ar) );

    }


    Dass die letzten Stellen dabei richtig herauskommen ist klar, da das Quadrieren im Restklassenring mod 10^20 exakt ist. Was aber die ersten Stellen angeht: Die Operationen a*=a (Quadrieren) und a/=10 (Kommaverschiebung) sind doch bestenfalls ein paar (oder auch ein paar mehr, aber niemals 65536) Schritte am Anfang exakt. Woher weiß man also, dass am Schluss die richtigen ersten Stellen herauskommen?

  • Ce1 . Ja, Du hast vollkommen recht. Danke für den Hinweis. Ich bin doch tatsächlich davon ausgegangen, dass beim Quadrieren eines Floats ja nur die letzte Stelle nicht exakt ist und der Gesamtfehler dann ungefähr 65536 eps ist. Nur dummerweise wird der Fehler in jedem Schritt wegen (x²)' = 2x etwa verdoppelt und ist dann am Ende in der Größenordnung der Zahl selbst. Womit der Dilettant bewiesen wäre. qed :)

  • Ok. Dann belassen wir's doch erstmal dabei (es sei denn, du weißt noch eine Quelle für die erste Stellen-Problematik). So allmählich werde ich für mich den Kalender abschließen.


    Und was heißt schon Dilettant?! E.E.Kummer glaubte, den großen Fermat bewiesen zu haben und scheiterte an einem kleinen Überseher. (Muss für ihn schlimm gewesen sein.) Und es sollen auch schon Schach-Großmeister einzügige Matts übersehen haben.

    Alles keine Dilettanten. :)

  • Ja mir ging's auch kurz ein wenig komisch. Hab erst mal Dank für Deinen Trost. Und bekanntlich kann man ja aus Fehlern nur lernen.


    Aber ganz so schlimmer mathematischer Unfug war es dann doch nicht, man kann die Idee mit einer korrekten Fehlerabschätzung retten, oder? Mittels "\p 20000" lässt sich in GP die Präzision in diesem Falle noch ausreichend erhöhen. Dann ist der Fehler etwa 2^65636 * 10^-20000 und die ersten Stellen korrekt !!?!


    42400774576164239697...(6.03123..357807 e19727 more digits)...83652555014874857472

  • Vielleicht hast Du Recht. Ich kann's so schnell nicht sehen. Vorstellen kann ich's mir nicht. 65536-faches Quadrieren ... ...

    Ok, wir wollen nur die ersten Stellen wissen, nicht alle, aber trotzdem.

    Ich werde nochmal drüber nachdenken, aber nicht mehr heute, keine Zeit.


    \p 100000 bedeutet was? 100000 Stellen Genauigkeit? (Ich kenne die PARI/GP-Software noch kaum.)

  • Ja, sogenannte signifikante Stellen. Bin mir mittlerweile ziemlich sicher, dass es so stimmt. Hab es mit verschiedenen Genauigkeiten ausprobiert. Ab 20000 Stellen ist das Ergebnis immer gleich, vorher eher "zufällig". Wie man das wegen 2^65636 ≈ 2e19728 auch erwarten würde.


    ... und da Du ja schon Deinen Rückzug angedeutet hast, vielleicht sieht man sich ja wieder im nächsten Jahr. Würde mich freuen :)

  • Doch noch ein kurzer Beitrag zum Thema "Erste Stellen". Du wirst wohl Recht behalten:


    Ich habe folgendes in PARI/GP eingegeben:


    \p 100000

    a=2^2^16

    b=log(2)/log(10)

    c=a*b

    \w ...datei \\ um alle Stellen zu sehen; wie kann man die Console dazu bringen, die Anzeige umzubrechen?


    In der Datei habe ich mir dann einige (30,40) Nachkommastellen nk genommen und damit


    10^nk


    berechnen lassen. Und, siehe da, die ersten Stellen sind 21200, mit 2 malgenommen also genau Dein Ergebnis!

    Ich staune, wie "leichtfüßig" diese Software mit solchen Genauigkeiten umgeht.


    "Im nächsten Jahr wieder sehen ...". Sagen wir "beim nächsten Kalender".;)

  • ... wage ich mich also auch noch mal kurz in diesen mittlerweile fast ein wenig unheimlichen Tempel der Stille ...


    Das nenne ich mal perfekte Synergie: erst die Irrtümer, und jetzt haben wir am Ende beide recht :) Klar, mit der größeren internen Präzision funktioniert ja jetzt auch Dein Ansatz mit dem Logarithmus.

    Code
    1. ? \p 20000
    2. realprecision = 20017 significant digits (20000 digits displayed)
    3. ? 2*10^(frac(2^2^16*log(2)/log(10)))
    4. %1 = 4.240077457616423969770329383324549261671308461350744967251903504708829131122322081417542017613864427947476604657175235712615340860593754350361470891374695454435421197995460509805991240661577631336462519623735954146703418998030823422504169547085720000940954068970289600231968666505528818552
    5. ?

    Er ist sogar besser, als das wiederholte Quadrieren. Da GP intern die ausreichende Präzision bei dem einen Ausdruck komplett prüft, bei dem Algorithmus jedoch nur das Einhalten der Präzision in jedem Einzelschritt sicherstellen kann. Schön zu sehen an der Fehlermeldung obigen Ausdrucks bei Präzision 10000. Bei höheren Präzisionen hingegen sind so jetzt auch ALLE ausgegebenen Ziffern verlässlich. Kann man prüfen mit 20100, 20200 ... Ja, das ist wirklich schwer beeindruckend. Anfang gut, Mittel egal :) Ende gut, alles gut. Na denne...



    EDIT: Übrigens, das ganze geht so auch in Python + mpmath, nur um die Präzision muss man sich da selber kümmern:

    Code
    1. >>> from mpmath import mp,log10
    2. >>> mp.dps = 20000 # precision
    3. >>> s = 2**2**16 * log10(2)
    4. >>> assert( log10(s) < mp.dps )
    5. >>> mp.dps -= log10(s) # precision of fractional part s%1
    6. >>> print( 2 * 10**(s%1) )
    7. 4.240077457616423969770329383324549261671308461350744967251903504708829131122322081417542017613864427947476604657175235712615340860593754350361470891374695454435421197995460509805991240661577631336462519623735954146703418998030823422504169547085720000940954068970289600232

    Dieser Beitrag wurde bereits 2 Mal editiert, zuletzt von umu () aus folgendem Grund: using mpmath instead of sympy for somewhat leaner code