Beiträge von Ce1

    Alles klar! Danke für den Tip bzgl. der Ausgabe. Du wirst Recht haben, es liegt sicher an der lines-Einstellung und nicht am fehlenden Umbruch. Werd's gleich ausprobieren.

    So, das war jetzt wirklich die letzte Einlassung.


    Mach's gut und bis die Tage ...

    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".;)

    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.)

    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. :)

    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?

    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.

    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!)

    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.)

    Klingt wie bei Fermat: ... habe wunderbaren Beweis gefunden, leider fehlt mir der Platz ...


    Ich habe auch nach längerer Grübelei - gerade heute - und nach ausführlichem Testen einen Beweis dafür gefunden, dass "meine" Konstruktion funktioniert. Endlich, endlich. Die Stimmung ist gerettet!

    Jetzt sehe ich, dass du deinen Beweis öffentlich gemacht hast. Meine "Erkenntnisse" gehen in genau die Richtung deines Beweises. Allerdings habe ich es nicht aufgeschrieben. Die wesentliche Beobachtung ist zunächst mal, dass, so weit man auch geht, die Anzahl der rechten Summanden nie 4 überschreitet, damit also für die ersten drei Plätze diese Zahl immer mindestens 12 Plätze frei hat. Und je weiter man nach hinten geht, um so seltener werden die 3er, die vorne eben 13 Plätze frei haben, und damit die "Drölfzahlen" (habe ich das richtig verstanden?).

    Und um das zu beweisen, geht man durch die Fallunterscheidungen, die du angeführt hast.

    Wirklich witzig, aber ich war genau an dem Punkt, als ich deinen Beweis gefunden habe. Allerdings, wie schon angedeutet, die Details hätten noch einige Arbeit verlangt.


    Deine/eure Gedanken und Ideen zu "Freistellen" und "Drölfzahlen" muss ich mir noch genauer zu Gemüte führen. Ich werde mir jetzt mal ansehen, wie die Dinge liegen, wenn man statt 4 Atomen 2 oder 3 oder 5 oder so kombiniert.

    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.

    Interessante Idee. Allerdings gibt es - oder täusche ich mich? - eine Strategie, die ins Unendliche fortgesetzt, von allen Gewichten 16 Atome verbraucht, also keine Freistellen lässt.

    Strategie für die n-te Ziehung: für die ersten 3 Gewichte nehme man die kleinstmöglichen, ohne die Anzahl 16 zu überschreiten, für das 4. Gewicht den Rest, um in der Summe n zu haben. Das beginnt so:

    0 0 0 1

    0 0 0 2

    0 0 0 3

    ...

    0 0 0 5

    0 1 1 4 die 0en sind jetzt verbraucht

    1 1 1 4

    1 1 1 5

    1 1 1 6

    1 1 1 7

    1 2 2 6 nun auch die 1en

    2 2 2 6

    usw.

    Ich glaube, dieser Prozess lässt sich ins Unendliche fortsetzen, hab's aber nur bis n = 2000 getestet, nicht bewiesen.


    Dennoch: die Idee ist interessant, aber wie soll's formuliert werden? Beispielsweise könnte man fragen, ob die Anzahl von Freistellen eine obere Grenze hat (vielleicht 10?) und, wenn ja, welche.

    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.

    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.

    Ja, ist schon eine tolle Aufgabe.

    Deine Aufteilung (und die von Pi mal Daumen) ist sozusagen die gleichmäßigste, die man haben kann. Rechnerisch bekommt man sie so:


    z1 = n / 4

    z2 = (n - z1)/3

    z3 = (n - z1 - z2)/2

    z4 = n - z1 - z2 - z3


    alle Divisionen ganzzahlig.


    So kommt man ganz schnell auf die 16er-Lösung. Ich war mir auch sicher, dass es die Lösung der Aufgabe war, nur fehlte der Beweis. Und dann kam ein Zweifel: vielleicht ist das der Gag der Aufgabe; man denkt sofort, 16 muss es sein, aber es gibt doch eine geschickte Strategie, die mit 15 auskommt. Ich hab's dann probiert, mit 15 auszukommen, und siehe da, zunächst schien es fast, als würde man mit 15 hinkommen, denn erst nach 75 Schritten brach das System zusammen. Das hatte zwei gute Effekte. Erstens war wohl 16 doch richtig und zweitens wurde mir klar, wie man das auch beweisen kann. Es ist der Pi mal Daumen - Beweis von oben. Außerdem hat Math5d oben noch einen etwas anderen Beweis geliefert.

    Mathematisch wahrscheinlich eine der interessantesten Aufgaben in diesem Kalender.

    Vorschläge für die Zusatzaufgaben:


    Zusatzaufg. 1: Zehnerstelle ist 7

    (kann sein, dass ich mich verrechnet habe, aber im Prinzip ist es eine einfache Rechnung)


    Zusatzaufg. 2:

    max. Anzahl auf Feld8 = 2*2↑(2↑↑(2↑↑↑(2↑↑↑↑(2↑↑↑↑↑2))))

    (wenn man die Beschränkung, dass nur 3 Felder hintereinander belegt sein dürfen, fallen lässt)

    (Beweis fehlt mir allerdings)

    Frage an die Aufgabensteller: sieht die Formel nur schön aus, oder könnte sie auch noch stimmen?

    Genau den entscheidenden Satz hast du dann nicht zitiert: "jede tatsächlich mögliche Strategie kann dann auf keinen Fall weniger Atome pro Masse benötigen". Ich wollte also nicht sagen, dass eine optimale Strategie existiert, sondern nur erstmal ausrechnen, wie viele man bei einer solchen bräuchte. Jede nicht optimale Strategie braucht dann mehr. Wenn selbst optimal nur 75 Züge mit 15 Atomen/Masse möglich sind, sind es in der Realität auf jeden Fall auch nur so viele.

    Diese Anmerkung in Klammern ist mir nicht entgangen. Nur: es bleibt dabei: Du nimmst etwas an, dessen Existenz nicht bewiesen ist. Worauf du abzielst, ist mir schon klar: Wenn wir für diesen Fall eine bestimmte Abschätzung bekommen, dann erst recht bei allen anderen Strategien. Aber, wie gesagt, der Ausgangspunkt ...

    Und: "jede tatsächlich mögliche Strategie kann dann auf keinen Fall weniger Atome pro Masse benötigen" - wenn man m_max nicht verändert.


    Aber wir wollen hier nicht streiten, vielleicht hast du doch recht und ich sehe das irgendwann ein. Schon möglich.