22: Plätzchenexplosion / Cookie Explosion

  • Du ahnst nicht, wie falsch Du liegst. Ohne den Algorithmus zu beschreiben, die Anzahl, von der hier immer gesprochen wird, ist


    max. Anz. = 2*(2 hoch (2 hoch (2 hoch (2 hoch (2 hoch 2))))) = 2 * (2 hoch (2 hoch 65536))

  • Ja diese max. Anzahl 2x mit x = 265536 + 1 ist unvorstellbar groß.


    Es gilt z.B. für den Exponenten x: x ist ungefähr 1019728 d.h. der Exponent x ist eine Zahl mit 19728 Stellen.


    Somit gilt 2x = 10log(2)*x . Mit log(2)*X ist ungefähr 3*1019727 = y folgt: 2x ist ungefähr 10y.

    Also eine Zahl mit ungefähr 3*1019727 Stellen.


    Schätzen wir mal die Anzahl der Atome im Universum grob ab:


    Unsere Sonne hat eine Masse von 2*1030 kg. Man schätzt, dass alleine unsere Milchstraße eine Masse von ca. 1012 Sonnenmassen besitzt. D.h. unsere Milchstraße hat ungefähr eine Masse von 2*1042 kg.

    Schätzungsweise gibt es 1011 Galaxien im Universum, somit beträgt die Gesamtmasse ca. 2*1053 kg.

    Angenommen, dass wir nur 1% der Masse "sehen" können, dann haben wir inklusive dunkler Materie eine Masse von ca. 2*1055 kg.

    Die meiste Materie im Universum ist Wasserstoff: 1 kg Wasserstoff sind ca. 6*1026 Atome.

    Somit hätten wir schätzungsweise 1,2*1082 Atome im Universum.


    Also selbst wenn wir auf jedes der Atome eine Stelle unserer Zahl schreiben könnten, dann hätte wir erst einen verschwindend kleinen Bruchteil der Stellen aufgeschrieben.

  • Die meiste Materie im Universum ist Wasserstoff: 1 kg Wasserstoff sind ca. 6*1026 Atome.

    Somit hätten wir schätzungsweise 1,2*1082 Atome im Universum.


    Also selbst wenn wir auf jedes der Atome eine Stelle unserer Zahl schreiben könnten, dann hätte wir erst einen verschwindend kleinen Bruchteil der Stellen aufgeschrieben.

    Du vergisst das Xmasium der Masse 0. Damit kannst Du Dir bei den gegebenen Massen beliebig viele Atome konstruieren, da kannst Du locker alle Stellen drauf aufschreiben. ;)


    Jetzt wäre nur noch zu klären, ob die Rentiere sich mit Plätzchen auf Xmasium-Basis zufrieden geben (wir wissen ja alle weder, wie Xmasium schmeckt, noch kennen wir die geschmacklichen Vorlieben der Rentiere). Wenn das nicht der Fall ist, fällt Weihnachten wohl in Zukunft aus. Das wäre schade, denn ohne Weihnachten gäbe es ja auch keinen Advent und somit keinen Mathe-Kalender mehr... :(

  • 0 0 0 0 0 0 0 1
    0 0 0 0 0 0 2 0
    0 0 0 0 0 2 1 0
    0 0 0 0 4 0 1 0
    0 0 0 0 0 4 = 22 0 0
    0 0 0 0 2 3 0 0
    0 0 0 4 0 3 0 0
    0 0 0 0 4 2 0 0
    0 0 0 8 0 2 0 0
    0 0 0 0 8 1 0 0
    0 0 0 16 0 1 0 0
    0 0 0 0 16 = 24 0 0 0
    0 0 0 2 15 0 0 0
    0 0 4 0 15 0 0 0
    0 0 0 4 = 22
    14 0 0 0
    0 0 8 0 14 0 0 0
    0 0 0 8 = 23
    13 0 0 0
    0 0 16 0 13 0 0 0
    0 0 0 16 = 24
    12 0 0 0
    . . .
    0 0 0 216 0 0 0 0
    . . .
    0 0 2216 = 265536
    0 0 0 0 0
    . . .
    0 2265536 0 0 0 0 0 0
    2*2265536


    So sieht die Konstruktion explizit aus (nur für den Fall, dass das so noch nicht klar war...) AugustaSibylla  

  • Ich habe zwar keine Ahnung von Graham & Co, konnte aber feststellen, dass auf dem 4. Feld 16 Plätzchen liegen und die letzte Ziffer immer konstant bleibt, wenn ich die Plätzchen um ein Feld "weiterschiebe", da es sich bei den auftretenden Potenzen immer um ganzzahlige Vielfache von 4 handelt - sieht man in der Tabelle von mr. x ganz schön.

    (Dass diese Vorhgehensweise optimal ist, können andere sicherlich besser zeigen als ich...)


    Und wenn man am Ende das Verdoppeln von Feld 7 auf Feld 8 richtig beachtet, kommt man auch ohne höhere Mathematik auf die richtige Lösung!!! :thumbsup:

  • Wenn Xmasium der Masse 0 überhaupt als Atom im Klassischem Sinn gilt:

    1. keine Kernladungszahl
    2. keine Massenzahl

    d.h. es besitzt nicht den klassischen Atomaufbau, also kann es sowieso nicht als Atom gezähöt werden...

    Mit der Argumentation könnte jemand, der nur rationale Zahlen kennt, argumentieren, dass z.B. Wurzel(2) oder pi nicht als Zahl im klassischen Sinn gelten, weil sie

    1. nicht als Bruch a/b (mit a und b als ganze Zahlen) geschrieben werden können

    2. nicht als Dezimalbruch eindeutig dargestellt werden können

    und somit nicht als Zahl gezählt werden können... ;)


    Wobei für Dich ja offenbar schon die 0 keine Zahl ist, wenn ein Atom mit Kernladungszahl 0 und Massenzahl 0 weder Kernladungs- noch Massenzahl besitzt. 8o :saint:


  • Wobei für Dich ja offenbar schon die 0 keine Zahl ist, wenn ein Atom mit Kernladungszahl 0 und Massenzahl 0 weder Kernladungs- noch Massenzahl besitzt. 8o :saint:

    Ja, schon allerdings sind Atome so beschrieben, dass sie Protonen besitzen. Also könnte Xmasium der Masse 0 zwar ein Teilchen sein, aber kein Atom, denn diese haben Kernladungszahlen > 0, sonst wäre auch schon ein einzalnes Neutron ein Atom mit Masse 1 und Ladung 0, soweit ich weis weden Netronen aber nicht zu den Atomen gezählt.:/



  • Ja, schon allerdings sind Atome so beschrieben, dass sie Protonen besitzen. Also könnte Xmasium der Masse 0 zwar ein Teilchen sein, aber kein Atom, denn diese haben Kernladungszahlen > 0, sonst wäre auch schon ein einzalnes Neutron ein Atom mit Masse 1 und Ladung 0, soweit ich weis weden Netronen aber nicht zu den Atomen gezählt.:/


    Das Thema hatten wir schon im Feedback-Thread zu der Xmasium-Aufgabe. Dort hatte wenn ich das richtig in Erinnerung habe jemand vorgeschlagen, dass es ja bislang unbekannte Kernteilchen mit negativer Masse geben könnte, die dem Xmasium seine ungewöhnlichen Eigenschaften verleihen. Über die Ladung ist ja sowieso keine Aussage gemacht, darüber können wir also bislang nichts sagen.


    Prinzipiell hast Du natürlich recht mit Deinen Argumenten, zumindest nach aktueller Lehrmeinung von Physik und Chemie. Aber es wäre ja nicht das erste Mal in der Geschichte, dass eine neue Entdeckung die aktuelle Lehrmeinung über den Haufen wirft. ;)

  • Nachdem ich die (optimale) Strategie gefunden hatte und auch beschreiben konnte, wie die Anzahl auf Feld 8 entsteht, kam das eigentliche Problem: Wie rechne ich die letzte(n) Stelle(n) , ohne die Zahl selber auszurechnen. Für nur den Einer hat ackerdemiker oben schon was grob skizziert, aber wie geht der Zehner?

  • Die Einerziffer einer Zahl ist ja einfach der Rest beim Teilen durch 10. In diesem Fall geht es um die Zahl z = 2*2n mit einem sehr großen und durch 4 teilbaren n. 2n hat die Endziffer 6, da n durch 4 teilbar ist: 24 = 16, 28 = 256, 212 = 4096, ... Jetzt muss man aber noch mit 2 malnehmen und bekommt somit 2 als Rest und damit die Lösung der Aufgabe.


    Zur Zehnerstelle: es geht ja um die Zahl z = 2*(2 hoch (2 hoch (2 hoch (2 hoch 4)))).


    Fangen wir hinten an: 24 gibt den Rest 16 auf 100. 216 gibt dann den Rest 36. Also gilt 216 = m*100+36. Nun geht es interessant weiter: 2 hoch (216) mod 100 = 2 hoch (m*100+36) mod 100 = (2100)m*236 mod 100 = ((2100)m mod 100 * 236 mod 100) mod 100. Nun gilt aber:

    2100 mod 100 = 76, 76m mod 100 = 76, 236 mod 100 = 36 und 76*36 = 36 mod 100. Beim weiteren Potenzieren ändert sich dieser Rest also nicht mehr. Zum Schluss wird noch mit 2 mal genommen, damit ergibt sich als Rest 72, Zehnerziffer also 7.

  • Etwas systematischer wird die Sache, wenn man sich überlegt, wie sich die 2er Potenzen in bezug auf 10er Potenzen verhalten.


    Modulo 10 haben wir eine 4er Periode: 21=2, 22=4, 23=8, 24=6. (= immer im modulo-Sinne.) D.h., dass die Einerstelle einer 2er Potenz 2n von n mod 4 abhängt. (Nur 20 ist hier ein Ausreißer.)


    Modulo 100 haben wir eine 20er Periode: 22 = 4, 23=8, 24=16, 25=32, 26=64, 27=28, ..., 222=4, ... . D.h., die Zehnerstelle von 2n hängt ab von n mod 20. (Hier wiederum sind 20 und 21 Ausreißer.)


    Modulo 1000 haben wir eine 100er Periode: 23 = 8, 24=16, 25=32, 26=64, 27=128, 28=256, ..., 2103=8, ... . D.h., die Hunderterstelle von 2n hängt ab von n mod 100. (Hier wiederum sind 20 , 21 und 22 Ausreißer.)


    Allgemein:

    Modulo 10m haben wir eine 4*5m-1er Periode, die mit 2m startet.


    Die Perioden in bezug auf 10, 100, 1000, 10000 ... sind also 4, 20, 100, 500 ...

    Die Perioden wiederum von 20, 100, 500, ... sind 4, 20, 100, ...

    Naja, ohne jetzt in weitere Einzelheiten zu gehen (es wird zu lang), mit Hilfe dieser Zusammenhänge lassen sich die letzten Stellen dieser Monsterzahl, um die es hier geht, bestimmen.


    Niemals bestimmen lassen sich alle Stellen dieser Zahl.

  • Ich habe mir die Zehnerziffer so überlegt:


    Zunächst lasse ich die letzte Verdopplung weg, d.h. ich betrachte die Zahl 2x mit x = 265536.

    Es genügt die Fälle zu betrachten, bei denen die Einerziffer eine 6 ist (durch die letzte Verdopplung wird daraus dann eine 2):

    Ich hab zunächst mal ein bischen herumprobiert und folgende Tabelle erstellt:

    n 4 8 16 32
    64 128
    die letzten beiden Ziffern von 2n
    16 56 36 96 16 56


    Das legt nahe, dass ein gewisser Zyklus vorliegt. Das Verdoppeln von n bedeutet ein Quadrieren der vorherigen Zahl (Potenzgesetze): Z.B. (28)2=28*2 = 216


    Wie hängen die letzten beiden Ziffern des Quadrates mit den letzten beiden Ziffern der Zahl die quadriert wird zusammen?


    Es gilt y = 100*k + r (r ist eine maximal zweistellige natürliche Zahl) ==> y2 = (100*k + r)2 = 10000*k2 + 2*100*k*r + r2 = 100*[100*k2 + 2*k*r] + r2

    D.h. die letzten beiden Ziffern von r2 sind identisch mit den letzten beiden Ziffern von y2.

    Somit genügt es immer nur die Zahl r zu quadrieren.

    So entsteht der Zkylus in der Tabelle. r = 16 ==> 162 = 256 ==>r = 56 ; 562 = 3136 ==> r = 36 ; 362 = 1296 ==> r = 96 ; 962 = 9216 ==> r = 16 und dann wiederholt sich das Ganze.

    Also nachdem man 4 Mal quadriert hat wiederholt sich r.


    Es gilt für n = 265536 : n = 16*265532 .

    D.h. die Hochzahl n wird 16 wird (Potenzgesetze) genau 65532 Mal verdoppelt , also wird die Zahl 216 genau 65532 Mal quadriert.


    Da 65532 durch 4 teilbar ist (Endziffernregel 32:4 = 8) hat 2x (mit x = 265536) genau die gleichen beiden letzten Ziffern wie 216 , also 36.


    Mit dem letzten Verdoppeln folgt also 2*36 = 72.


    Also ist die Zehnerziffer eine 7. :)

  • ...

    Fangen wir hinten an: 24 gibt den Rest 16 auf 100. 216 gibt dann den Rest 36. Also gilt 216 = m*100+36. Nun geht es interessant weiter: 2 hoch (216) mod 100 = 2 hoch (m*100+36) mod 100 = (2100)m*236 mod 100 = ((2100)m mod 100 * 236 mod 100) mod 100. Nun gilt aber:

    2100 mod 100 = 76, 76m mod 100 = 76, 236 mod 100 = 36 und 76*36 = 36 mod 100. Beim weiteren Potenzieren ändert sich dieser Rest also nicht mehr. Zum Schluss wird noch mit 2 mal genommen, damit ergibt sich als Rest 72, Zehnerziffer also 7.

    Der Trick ist also, dass man einen Teiler (hier 100) nimmt, bei dem der Rest unabhängig von m ist. ((2^100)^m mod 100) ist 76, für alle m.

    Für die Einer geht das so nicht, weil ((2^10)^m mod 10) von M abhängt. Aber man kann mod 20 nehmen, was ich so zufällig durch ausprobieren gefunden hatte, ohne Beweis. Danke an ce1, jetzt weiß ich warum es funktionierte.

  • Etwas systematischer wird die Sache, wenn man sich überlegt, wie sich die 2er Potenzen in bezug auf 10er Potenzen verhalten...

    Noch als kleine weiterführende Ergänzung, kleiner Fermatscher Satz bzw. Satz von Euler: aφ(n) = 1 (modulo n) für teilerfremde a,n.


    Damit lassen sich nach gleichem Schema generell die Reste von Potenzen, Potenztürmen oder größeren Pfeilmonstern schrittweise runterbrechen, solange die Primzahlzerlegungen bis zur Modulo-Basis noch bewältigbar sind. In unserem konkreten Beispiel bis 5 ist das ja der Fall :) Wegen der Teilerfremdheit betrachtet man nun erst mal die Zahl modulo 5m. φ(5m) = 4 5m-1, womit sich obige Perioden 4, 20, 100, 500 etc. erklären. Ist die Zweierpotenz nur groß genug, ist die Teilbarkeit durch 2m ohnehin klar, so dass sich per Chinesischem Restsatz auch die gleichen Perioden der Reste modulo 10m ergeben.

  • Noch als kleine weiterführende Ergänzung, kleiner Fermatscher Satz bzw. Satz von Euler: aφ(n) = 1 (modulo n) für teilerfremde a,n.


    Damit lassen sich nach gleichem Schema generell die Reste von Potenzen, Potenztürmen oder größeren Pfeilmonstern schrittweise runterbrechen, solange die Primzahlzerlegungen bis zur Modulo-Basis noch bewältigbar sind. In unserem konkreten Beispiel bis 5 ist das ja der Fall :) Wegen der Teilerfremdheit betrachtet man nun erst mal die Zahl modulo 5m. φ(5m) = 4 5m-1, womit sich obige Perioden 4, 20, 100, 500 etc. erklären. Ist die Zweierpotenz nur groß genug, ist die Teilbarkeit durch 2m ohnehin klar, so dass sich per Chinesischem Restsatz auch die gleichen Perioden der Reste modulo 10m ergeben.

    Damit kein falscher Ton in die Diskussion kommt: Ich wollte nicht behaupten, als seien diese Perioden-Eigenschaften meine Entdeckung. Es ist schon klar, dass es sich hier um ziemlich alte Erkenntnisse der elem. Zahlentheorie handelt.


    Und in diesem Sinne noch zusätzlich: 2 ist sog. Primitivwurzel zu 5 und, nach einem weiteren uralten Satz der elem. Zahlentheorie, auch Primitivwurzel zu allen Potenzen 5n. Daher ist 4*5n-1 die Ordnung von 2 in der Gruppe der zu 5n teilerfremden Restklassen.

    Damit sind die oben genannten Perioden auch die kleinsten, etwas, was, wenn ich mich nicht täusche, aus dem oben zitierten Satz von Euler allein nicht hervorgeht, (möglicherweise aber auch für unsere Belange hier gar nicht so wichtig ist :-)


    Was ich noch bemerkenswert fand, ist die Tatsache, dass in der Folge der immer gigantischer werdenden Zahlen 2^^n, n = 1,2, ... die letzten Ziffern sich mehr und mehr stabilisieren (oder wie soll man es ausdrücken?):


    ab 2^^3 ist die Endziffer 6,

    ab 2^^4 sind die Endziffern 36,

    ab 2^^5 sind die Endziffern 736 (nicht ganz sicher, ob die 7 stimmt),

    usw.