2 Beweise gesucht: Unsterbliche Zahlen!

Neue Frage »

blackdrake Auf diesen Beitrag antworten »
2 Beweise gesucht: Unsterbliche Zahlen!
Hallo zusammen.

Ich habe mich mal mit der mathematischen Spielerei der "unsterblichen Zahlen" beschäftigt und festgestellt, dass das wohl eine ziemlich harte Nuss ist. Ich habe eine Theorie aufgestellt und suche nun nach 2 Beweisen.

Für die, die das noch nichts von "unsterblichen Zahlen" gehört haben:

Eine Zahl w aus den natürlichen Zahlen ist "unsterblich", wenn



wobei Kringel (°) der "Konkatenierungsoperator" (aneinanderhängen) aus der gedachten formellen Sprache und x eine natürliche Zahl ist.

Sprich: Wenn man eine Ausgangszahl w immer wieder mit sich selbst multipliziert, hat das Produkt immer einen Suffix w.


Einfachstes Beispiel hierfür ist die Zahl "6":

6 mit sich selbst multipliziert: 6, 36, 216, 1296, 7776, 46656, ... => es ist immer eine "6" am Ende, also ist 6 eine unsterbliche Zahl.

Ein weiteres einfaches Beispiel ist die Zahl "5":

5 mit sich selbst multipliziert: 5, 25, 125, 625, 3125, ... => es ist immer eine "5" am Ende, also ist 5 eine unsterbliche Zahl.

Soweit so gut.


Schwieriger wird es z.B. bei der Zahl "12890625". Sie ist möglicherweise unsterblich. Aber wer sagt mir, dass 12890625^n immer ein "12890625" am Ende hat für alle n Element natürlicher Zahlen? Da ich nicht beweisen kann, dass 12890625^n für alle n aus den natürlichen Zahlen mit 12890625 enden, kann ich nicht 100% BEWEISEN dass 12890625^ eine unsterbliche Zahl ist.

Daher suche ich folgenden Beweis:

1. Der Beweis, dass eine natürliche Zahl w tatsächlich unsterblich ist. Notwendig ist es, eine Aussage über den Suffix von w^n für alle möglichen n (Element natürlicher Zahlen) zu treffen.

=> Wie kann ich beweisen, dass bei einer potenziell unsterblichen Zahl "w" folgendes gilt: w^n endet für alle n aus den natürlichen Zahlen IMMER auf w?



Außerdem habe ich eine Methode gefunden, unsterbliche Zahlen mit einem Computerprogramm schneller zu suchen, als wenn man diesen Vorgang sequenziell (i=1,2,3,4,...) durchführen würde.

Ich habe als erstes ein Computerprogramm geschrieben, das eine sequenzielle Suche durchführt und bis zu einer gewissen "Genauigkeit" abzuschätzen, ob es eine unsterbliche Zahl ist oder nicht.

Die ersten 16 Zahlen die ich fand waren:

I(1) = 0
I(2) = 1
I(3) = 5
I(4) = 6
I(5) = 25
I(6) = 76
I(7) = 376
I(8) = 625
I(9) = 9376
I(10) = 90625
I(11) = 109376
I(12) = 890625
I(13) = 2890625
I(14) = 7109376
I(15) = 12890625
I(16) = 87109376

Dies brachte mich auf eine interessante Erkenntnis.

Schauen wir uns einmal die Glieder mit Endungen "5" und "6" an:

"5er-Stamm":

I(3) = 5
I(5) = 25
I(8) = 625
I(10) = 90625
I(12) = 890625
I(13) = 2890625
I(15) = 12890625

"6er-Stamm":

I(4) = 6
I(6) = 76
I(7) = 376
I(9) = 9376
I(11) = 109376
I(14) = 7109376
I(16) = 87109376

Seht ihr auch, was ich sehe? Sowohl bei dem 5er-Stamm als auch beim 6er-Stamm hat die nächstmögliche unsterbliche Zahl immer ein paar Stellen als Präfix hinzugefügt.

6, 76, 376, 9376, ...

bzw.

5, 25, 625, 90625, ...

Durch diese Erkenntnis kann meinen Suchalgorithmus ERHEBLICH optimieren.

Nehmen wir an, meine Theorie stimmt, dann könnte ich zu der nächstmöglichen Zahl von "87109376" folgende Aussage machen:

Da die nächstmögliche Zahl (im 6er-Stamm!) einen Präfix zu ihrer vorherigen unsterblichen Zahl haben muss, brauche ich die Zahlen 87109377 bis 187109375 nicht betrachten! Ich spare mir also das sequenzielle Prüfen von 99999998 Zahlen, da meine Theorie besagt, dass ausgehend von "87109376" die nächstmögliche Zahl im gleichen Stamm (6er) mindestens 187109376 sein muss. Ist 187109376 keine unsterbliche Zahl, dann werde ich bei 287109376 weitersuchen, dann bei 387109376, dann bei 487109376... sobald ich wieder eine unsterbliche Zahl gefunden habe, kann ich diese "Präfix-Suche" abbrechen und einen Präfix vom Präfix finden für die nächste unsterbliche Zahl suchen.

Und hier ist der zweite Beweis, den ich bis jetzt vergeblich suche:

2. Der Beweis, dass meine Theorie für einen Suchalgorithmus ALLE unsterblichen Zahlen erfasst.

Gibt es z.B. einen Gegenbeweis, der zeigt, dass mein Iterationsalgorithmus eine Zahl, die man mit der sequenziellen Suche finden würde, nicht erfasst?

Äquivalenter Beweis: Kann man mathematisch beweisen, dass wenn "w" eine unsterbliche Zahl ist, die nächstmögliche unsterbliche Zahl "a°w" ("a" ist der zu suchende Präfix) ist?



Ich hoffe, ich kann mit diesem Thema ein paar Mathematik-Interessierte begeistern und vielleicht können wir ein wenig Gedanken über Beweisansätze finden.

Grüße
Daniel


// EDIT: Ich habe mich bei der Definition vertan! Anstelle w^inf ist das Problem w^n für alle n.
René Gruber Auf diesen Beitrag antworten »

Man kann das ganze auch so darstellen:

Eine nach deiner Definition unsterbliche -stellige Zahl muss die Bedingung



erfüllen, umgestellt heißt das

.

Nun sind und teilerfremd, d.h. (*) ist genau dann erfüllt, wenn entweder



oder



erfüllt ist. Solche Zahlen kann man für konkretes per chinesischem Restsatz finden bzw. auch eine Rekursion über für solche Lösungen entwickeln.

P.S.: Du solltest in Betracht ziehen, auch "führende Nullen" zuzulassen: So erfüllt z.B. auch 0625 deine Forderungen. Diese Zahlen schließen dann auch die Lücken in deinen Folgen.
blackdrake Auf diesen Beitrag antworten »

Hallo René Gruber und danke für deine Antwort.

Bezüglich der "Nullen". Das hatte ich vergessen zu definieren. Ich denke, bei diesem Konkatenierungsoperator gilt das linksneutrale Element E=0 mit E°a = 0°a = a. 0625 ist ja schließlich das selbe wie 625. Oder bringt mir die führende Null einen Vorteil bei der suche von unsterblichen Zahlen?

Das mit dem Modulo habe ich mir schon gedacht, allerdings habe ich deinen Beweisansatz nur bis zur Hälfte verstanden.

Was sagt dein Ansatz, bei dem du 2 mögliche Modulo-Lösungen für n dargestellt hast konkret aus?

Gesucht (erster Beweis) ist ja:

(*)

Dein Ansatz würde nun eine Aussage über w^2 treffen. Und was ist mit w^3, w^4 ...? Oder gilt das dann genau so?

Gruß
Daniel


(*) ich hatte mich in meiner ursprünglichen Definition vertan. w^unendlich war falsch. In der Tat suche ich für alle n.
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von blackdrake
Was sagt dein Ansatz, bei dem du 2 mögliche Modulo-Lösungen für n dargestellt hast konkret aus?

Er sagt aus, dass es genau zwei m-stellige unsterbliche Zahlen gibt, allerdings ggfs. mit den genannten führenden Nullen. Und außerdem bestätigt er deine Theorie, dass bei einer (m+1)-stelligen unsterblichen Zahl durch Wegstreichen der ersten Ziffer eine m-stellige unsterbliche Zahl entsteht.

Zitat:
Original von blackdrake
Dein Ansatz würde nun eine Aussage über w^2 treffen. Und was ist mit w^3, w^4 ...?

Das ist nun wirklich nur eine einzeilige Folgerung: Aus folgt für alle

,

damit ist die Frage schon geklärt.
blackdrake Auf diesen Beitrag antworten »

Zitat:
Original von René Gruber
dass bei einer (m+1)-stelligen unsterblichen Zahl durch Wegstreichen der ersten Ziffer eine m-stellige unsterbliche Zahl entsteht.


Oha, da fällt mir ja gerade etwas interessantes auf geschockt

Ich ging bisher immer davon aus, dass der gesuchte Präfix für die nächste Zahl beliebig ist.

Jetzt wird mir allerdings klar:

90625 -> wegstreichen der ersten Ziffer -> 0625 = 625 (vorherige unsterbliche Zahl)

Das heißt über das Präfix könnte ich jetzt theoretisch aussagen, dass es formell betrachtet

a = [1..9] [0]*

ist und nicht wie ursprünglich angenommen

a = [1..9] [0..9]* .

(* = null, eins oder mehrere Vorkommen)



Vielen Dank für deine Ansätze. Ich werde mich mal dahinterklemmen und versuchen, die Folgerungen nocheinmal nachzuvollziehen. (Diskrete Mathematik liegt 3 Semester zurück. Da ist mir der Chinesische Restsatz nicht mehr ganz geläufig)

Gruß
Daniel
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von blackdrake
Ich ging bisher immer davon aus, dass der gesuchte Präfix für die nächste Zahl beliebig ist.

Ganz im Gegenteil: Es gibt für jede der beiden Folgen (ich nenne sie mal 5er und 6er-Folge) immer nur jeweils genau einen Präfix, der zu einer neuen unsterblichen Zahl führt. Aber wie gesagt, dieser Präfix kann auch mal die Ziffer 0 sein.
 
 
blackdrake Auf diesen Beitrag antworten »

Hallo.

Ich habe nun den Großteil deiner Folgerungen nachvollzogen und nun auch die Lösungsformel(n) für eine unsterbliche Zahl der Länge m mit Hilfe des chinesischen Restsatzes (Onlinetool http://www.arndt-bruenner.de/mathe/scrip...herRestsatz.htm sei Dank) angewandt.

Mein fehlender Beweis #1 (Beweis, das eine Zahl wirklich unsterblich ist) habe ich mit der Formel



erreicht.

Beweis #2, der alle unsterblichen Zahlen in den natürlichen Zahlen findet, habe ich auch bis auf wenige Kleinigkeiten verstanden.

Auch habe ich nun nocheinmal in der Praxis gesehen, dass für m=4 die Lösung des Chin. Restsatzes 625 ergibt, da hier der Präfix "0" war (Oder in anderen Worten: Es gibt keine unsterbliche Zahl der Länge m=4 für die 5er-Folge).

Insbesondere habe ich in der Praxis die "Zuordnung" gesehen:

Deine Gleichung bildet die "6er-Folge" ab.

Während die Gleichung die "5er-Folge" abbildet.


Was ich jetzt in Handarbeit in der Praxis getan habe, würde ich liebend gerne in eine Formel packen. Ich möchte daher gerne zwei Funktionen definieren:

1. findet die unsterbliche Zahl der Länge mit dem "Stamm" 5.
2. findet die unsterbliche Zahl der Länge mit dem "Stamm" 6.

führt den Chinesischen Restsatz aus mit



führt den Chinesischen Restsatz aus mit




Nachdem ich den Chinesische Restsatz nochmal in Wikipedia nachgeschlagen habe:

Zur Lösung von




wird angewandt:

mit


Daraus folgt für mein Problem:

Für die 6er-Reihe :



Und für die 5er-Reihe :



Bei beiden jeweils:




Das Problem, das ich nun habe, ist, dass ich mit dem nichts anfangen kann. (Bitte nicht hauen ^^)

Ich habe vor einiger Zeit ggT's mit dem euklidischen Algorithmus berechnet, allerdings immer mit konkreten Zahlen und nie mit Variablen wie z.B. "m". Daher weiß ich nicht genau, wie ich vorgehen muss und ob überhaupt eine Aussage über den ggT getroffen werden kann.

Ferner verstehe ich die Aussage nicht. (y brauche ich oben nochmal)

Nehme ich einmal das einfachste Beispiel mit konstantem :



Der ggT von 2 und 5 ist gleich 1, also



Und nun? Wenn ich nach y auflöse:



dann habe ich eine Unbekannte in meiner endgültigen Formel und kein exaktes Ergebnis.

Ich habe für z einfach mal 1 eingesetzt, in Hoffnung, dass dann die kleinste Zahl herauskommt. Allerdings wäre dann meiner Rechnung nach M6(1) = 4 und nicht M6(1) = 6 verwirrt

Wie gesagt, ich hatte den Chinesischen Restsatz bisher immer nur mit konkreten Zahlen und nie mit Variablen gerechnet, deswegen hänge ich hier noch fest.

Gruß
Daniel
blackdrake Auf diesen Beitrag antworten »

Hallo,

Kann es sein, dass



ist?

Beweis?

Wenn es stimmt, dann kann ich aufgrund



sagen, dass



Ein Rätsel bleibt mir dann trotzdem noch, was y und z sind und wieso ich etwas falsches herausbekomme, wenn ich z=1 einsetze, nach y auflöse und damit den Restsatz auflöse.



Ich bin mir bei "z" auch nicht sicher, ob diese Variable zeigen soll, dass es für den Chin. Restsatz für M5(u) bzw. M6(u) mehrere Lösungen gibt (die im Modul den selben Rest haben). Ich gehe aber davon aus, dass M5(u) und M6(u) genau eine Lösung haben. (Beweis, dass es nur ein mögliches z gibt?)

Gruß
Daniel
wisili Auf diesen Beitrag antworten »

Zitat:
Original von blackdrake
Der ggT von 2 und 5 ist gleich 1


Somit lässt sich 1 linear aus 2 und 5 ganzzahlig kombinieren (siehe):

1 = 3*2 + (-1)*5, sodass also y=3 und z=-1 gilt.

Bei höheren Zahlen dient der Euklidische Algorithmus nicht nur dazu, den ggT zu ermitteln, sondern (der erweiterte Euklidische Algorithmus) verhilft zu den (hier sog.) Faktoren y und z.
René Gruber Auf diesen Beitrag antworten »

@blackdrake

Ja klar ist , denn welcher Primfaktor soll denn schon in beiden Potenzen gemeinsam drin sein? Augenzwinkern

Zitat:
Original von blackdrake
Ein Rätsel bleibt mir dann trotzdem noch, was y und z sind und wieso ich etwas falsches herausbekomme, wenn ich z=1 einsetze, nach y auflöse und damit den Restsatz auflöse.


Du hast da wohl was grundsätzlich falsch verstanden: bedeutet nur, dass diese Gleichung ganzzahlige Lösungen hat, z.B. . Es bedeutet NICHT, dass du eine der beiden Zahlen willkürlich wählen kannst und dann nach Auflösung der Gleichung die andere Zahl automatisch ganzzahlig ist.

Eine systematische Methode zum Finden einer solchen Lösung bietet der Erweiterte Euklidische Algorithmus (EEA).


EDIT: Sorry, hab nicht gesehen, dass schon ein anderer geantwortet hatte.
blackdrake Auf diesen Beitrag antworten »

Hallo ihr beide,

vielen Dank für den Hinweis.

Die Primfaktorzerlegung
2*2*2*2*... = 2^u
und
5*5*5*5*... = 5^u
zeigt ja deutlich, dass 2^u und 5^u immer teilerfremd sind für alle u, da kein gemeinsamer Primfaktor hinzukommen kann. Hammer

Das Lemma von Bézout kommt mit jetzt in Bezug auf den EEA auch bekannt vor (Allerdings habe ich den EEA auch bisher nur mit konkreten Zahlen gerechnet).

Die Frage ist nun, wie ich den EEA auf eine mir unbekannte Ausgangssituation a=2^u und b=5^u anwende.

Meine aktuelle Formel der Folgen (unter Berücksichtigung der neuen Tatsache dass d(u)=1 für alle u) lautet:





Alleine durch die lineare ganzzahlige Kombination komme ich ja nicht weiter, da sie ja mehrere Werte annehmen kann, z.B. (y=3, z=-1) oder (y=-2, z=1) , allerdings nur y in M5(u) bzw. M6(u) auftaucht.

Es wundert mich allerdings nun, dass die allgemeine Lösung des Chinesischen Restsatzes (aus Wikipedia, siehe Oben) keine Bedingung an das Tupel (y,z) stellt, obwohl diese doch notwendig wäre? Das Lemma von Bézout besagt ja, dass es ganzzahlige (y,z) gibt, sodass die Gleichung erfüllt ist. Aber es gibt nur (exakt?) ein (y,z) Tupel, für das der Chinesische Restsatz die korrekte Lösung ergibt:





Ich sehe irgendwie kein Muster für meine Folge 6, 76, 376, ... sodass ich y für alle u bestimmen könnte.



PS:

Ist die Schreibweise

(1)

in meinem Fall Äquivalent zu

(2)

?

Schreibweise (1) scheint auszudrücken, dass es mehrere Lösungen für im Modul gibt, während Schreibweise (2) eine Lösung, nämlich die kleinste ausdrückt (aber ist es auch KORREKT, dass wirklich nur für 1 Zahlsteht?). Allerdings widerspricht dies doch der Aufgabenstellung, oder?

Bei M5(u) bei der deutlich kleiner 0 wird, muss ich noch schauen, in wie fern dies auf eine einfache Zahl ohne Modul zu bringen ist. Das sehe ich wahrscheinlich, sobald ich weiß, was "y" ist.


Gruß
Daniel
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von blackdrake
Ich sehe irgendwie kein Muster für meine Folge 6, 76, 376, ... sodass ich y für alle u bestimmen könnte.

Da gibt's auch kein sonderlich einfach beschreibbares Muster für die vorn neu hinzukommende Ziffer. Aus der Theorie weiß man aber, dass es genau eine Möglichkeit für diese Ziffer gibt. Da es nur 10 Möglichkeiten für diese Ziffer gibt, ist eine einfache Möglichkeit die folgende: Einfach beim Übergang von zu



alle 10 Möglichkeiten durchprobieren und die eine nehmen, für die richtig ist. Glaub mir, die Einzelanalyse über die Module und bringt nur viele nette Formeln, aber keine einfachere oder schnellere Berechnungsmöglichkeit der neuen Ziffer. Augenzwinkern
blackdrake Auf diesen Beitrag antworten »

Hallo.

Das ist leider ernüchternd für mich, nachdem ich die Formeln des chinesischen Restsatzes für meinen Fall so weit vereinfachen konnte. Ich hatte mir erhofft, dass es zu dem Problem

führt den Chinesischen Restsatz aus mit



bzw.

führt den Chinesischen Restsatz aus mit



jeweils eine nette Formel gibt, zumal ich ja nur dieses "y" aus dem chinesischen Restsatz bestimmen muss.

Ist es also nicht möglich, diesen chinesischen Restsatz durch eine Formel zu lösen? Gibt es außer Ausprobieren keine Formel für M5(u) oder M6(u) als Lösung?


Die manuelle Methodik zum Auflisten aller M6(u) war, im Onlinetool http://www.arndt-bruenner.de/mathe/scrip...herRestsatz.htm die konkreten Werte für u=1,2,3,4,... einzugeben. Allerdings sind die hier Werte für 2^u und 5^u konkrete Zahlen.

Gruß
Daniel
René Gruber Auf diesen Beitrag antworten »

Also gut, du hast es nicht anders gewollt: Es geht um die Bestimmung von in .

Dann muss es ganze Zahlen mit



geben. Setzen wir da nun ein, zunächst mal in die Zweierpotenzen:



Modulo 2 betrachtet ergibt das

,

das ist die erste Bedingung. Jetzt die Fünferpotenzen



Dies modulo 5 betrachtet ergibt bzw. mit multipliziert . Aufgeschlüsselt nach ist dann vielleicht



noch einsichtiger, das wäre dann die zweite Bedingung. Beide Formeln (1)(2) zusammen ergeben dann die eindeutige Lösung im Bereich , sowie die Folgewerte und .


Beispielrechnung für die ersten :

* Start ist , also .

Damit ist sowie wegen dann , das macht , die nächste Zahl ist also

* Nächster Schritt: mit .

Damit ist sowie wegen dann , das macht , die nächste Zahl ist also

* Nächster Schritt: mit .

Damit ist sowie wegen dann , das macht , die nächste Zahl ist also

* Nächster Schritt: mit .

Damit ist sowie wegen dann , das macht , die nächste Zahl ist also

...

Ich empfinde das nicht einfacher als das Durchprobieren, wie sieht's bei dir aus? Augenzwinkern
blackdrake Auf diesen Beitrag antworten »

Wow, geschockt

vielen Dank Gott

das ist ja faszinierend! Natürlich sind diese Formeln heftig kompliziert (zumindestens für mich), aber ich liebe es, wenn man am Ende etwas auch wirklich eindeutig bestimmen kann, ohne zu probieren (auch wenn es aus Programmierer-Sicht wohl doch effizienter wäre, einfach in einer Iteration zu probieren).

Ich muss wirklich sagen, dass die "unsterblichen Zahlen" mich jetzt, wo ich die Formeln sehe, noch viel mehr interessieren, als es zuvor war. Leider ist mein Wissensstand in Mathematik nicht ganz so groß, weswegen ich für das Verständnis noch ein paar Male drüberschauen und nachdenken muss.

Könntest du mir vielleicht den großen Gefallen tun und mir erklären, welche Dinge sich in deiner Beweisführung ändern, wenn wir M5(u) betrachten? (Vielleicht den obigen Post Copy-Pasten und die Stellen abändern, die für M5(u) anders sind.)

Es würde mich brennend interessieren, wie die Formeln sich dort verhalten und sie vergleichen.

Ich habe die Vermutung, dass



dann so aussieht:



Ist das richtig? Ich glaube aber, dann verändert sich außerdem die Definition von r und t bzw r' und s'.

Als ich versuchte, davon auszugehen, dass die Definitionen die selben sei, kam ich bei M5(1) zu:



Also r=2 und s=1 . Bei u=1 bekomme ich dann t=2s=2 (korrekt) . Dann wären allerdings r' = 1 und s'=2/5 , was ja nicht sein kann, weil s' eine ganze Zahl sein muss. Die Formeln sind dann wohl für M5(u) anders.


Gruß
Daniel


PS: In deinem vergangene Post hast du versehentlich "m" statt "u" einmal verwendet.
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von René Gruber
Dann muss es ganze Zahlen mit


wird zu

Zitat:
Dann muss es ganze Zahlen mit


Der Rest der Iteration müsste nahezu gleich bleiben.


Zitat:
Original von blackdrake
PS: In deinem vergangene Post hast du versehentlich "m" statt "u" einmal verwendet.

Gut möglich, weil ich so "dumm" war, meine Betrachtungen auf dein umzustellen, da sind mir wohl beim Suchen+Ersetzen einige durch die Lappen gegangen.
wisili Auf diesen Beitrag antworten »

Bei der 5-er-Folge scheint eine Rekursion möglich:

René Gruber Auf diesen Beitrag antworten »

In der Tat, da man für



darstellen kann. Bei den Fünferpotenzen ist es noch klarer zu erkennen.
blackdrake Auf diesen Beitrag antworten »

Zitat:
Original von René Gruber
Der Rest der Iteration müsste nahezu gleich bleiben.


Bei meiner Vermutung mit dem "+1" an der anderen Stelle lag ich dann also richtig.

(Editiert)

Ich hab's jetzt auch endlich verstanden!

Bei dem Unterschied



zu



sowie



zu



kürzen sich jeweils "+1" weg. Genau so bei der zweierpotenz. Daher sollten alle Formeln gleich.

Mein Fehler mit dem 2/5 war ein Rechenfehler, den ich mitgenommen hatte.

Ich komme aber irgendwie trotzdem nicht auf das korrekte s' für M5(1).

Da t=2, r=2, s=1: .

Es muss aber s' = 6 sein, da in M5(2) gelten wird t=s und t=6 sein soll. verwirrt

Zitat:
Original von René Gruber
Gut möglich, weil ich so "dumm" war, meine Betrachtungen auf dein umzustellen, da sind mir wohl beim Suchen+Ersetzen einige durch die Lappen gegangen.


Normalerweise ändere ich nie die Variablen, aber an dem einen Punkt hatte sich das Längen-m mit dem m aus der Restsatz-Formel geschnitten...
blackdrake Auf diesen Beitrag antworten »

Hallo,

ich habe mal heute schnell ein Java-Programm geschrieben, das die M5(u) Formel mithilfe des Chin. Restsatzes (Parameter Mp=1, P=2^u, Mq=0, Q=5^u) durchführt. Im Moment geht es noch sehr flott, aber ich denke, dass der Algorithmus noch erheblich optimiert werden kann. Im Moment gehe ich in 10.000 Schritten voran und speichere dann immer ab. Dadurch habe ich immer ein Zwischenergebnis, im Falle, dass der Speicher des Servers zu Ende geht oder es zu einem Ausfall kommt.

http://beta.viathinksoft.de/~daniel-mars.../livestatus.php

Eine interessante Entdeckung habe ich nocht gemacht:

Das "t", das immer hinzugefügt wird, ist bei M5 und M6 immer das 10er-Komplement. Also t=9-t' bzw. t'=9-t .

Daher gilt die Formel



z.B. für :



Somit ist es einfach möglich, M5(u) und M6(u) ineinander umzurechnen und man muss nur das größte M5(u) finden und das M6(u) ist dann einfach zu erlangen. (Auch ohne BigInteger-Funktionalität, da man ja Stellenweiße, bis auf die letzte Stelle immer nur das 10er-Komplement bilden muss)


=> Ich wäre aber immer noch an den Formeln zur Bestimmung für "t" bei M5(u) interessiert. Da bin ich noch nicht drauf gekommen.
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von blackdrake

Ja so ist das - die einfachsten Dinge fallen einem manchmal erst sehr spät ein. Teufel

Na klar gilt da, diese Symmetrie folgt ja schon aus der Gleichung , wo mit auch sofort Lösung ist. Hammer

Damit ist eigentlich folgender Algorithmus vorgezeichnet: Es sei

,

dann brauchen wir bei der Berechnung von über die von wisili genannte Kongruenz ja nur noch die neue Ziffer zu berechnen, was über das Cauchyprodukt



möglich sein sollte.

Beispiel: , dann ist und folglich



also . Das soll eigentlich nur demonstrieren, dass man nicht das vollständige Quadrat ausrechnen muss, was ja bei großem eine enorme Stellenzahl braucht, sondern sich von Stelle zu Stelle hangeln kann, ohne großen Platzbedarf für die Gesamtzahl. Damit sollte es dir auch möglich sein, in einem Algorithmus schnell z.B. zu ermitteln und somit auch . Augenzwinkern


Damit ist erledigt, und dann auch über dein mit wachem Auge erkanntes . Für die einzelnen Ziffern von



hat das schlicht für alle zur Folge. Eine Ausnahme bildet da mit nur die letzte Ziffer.


Schönes Wochenende (bin erst Montag wieder da) Wink
wisili Auf diesen Beitrag antworten »

-- Edit: Ich wollte noch anmerken, dass nicht das volle Quadrat gebraucht wird, aber R. Gruber hat das schon getan.
blackdrake Auf diesen Beitrag antworten »

Hallo.

Vielen Dank für eure Hilfe.

Ich habe leider immer noch ein paar Probleme. Mein Ziel ist es, effektiv die größtmögliche M5/M6-Zahl mithilfe eines JAVA-Programms zu ermitteln und einen Server diese Zahl über lange Zeit hinweg fortführen zu lassen.

Ich habe etliche Versuche und zahlreiche Benchmark-Tests geschrieben und fasse mal zusammen, was ich so alles habe:

1. Versuchs-Reihe: Sequenzielle Suche

Es werden die Zahlen 1,2,3... durchlaufen. Logischerweiße ganz und gar nicht effektiv.

FEHLGESCHLAGEN

2. Versuchs-Reihe: Errechnen mithilfe des chinesischen Restsatzes

Ich suche mir ein großes u aus und löse den Chin. Restsatz:

führt den Chinesischen Restsatz aus mit



PROBLEM: M6(650000) errechne ich in 56:24 Minuten. Das ist zwar relativ flott (ich habe kein Problem damit, das Programm ein paar Jahre laufen zu lassen, zumal der Server 24/7 online ist). Das Problem ist allerdings, sobald ich ein M5(u) errechnet habe, kann ich nicht auf M5(u+1) schließen, ohne nochmal KOMPLETT von vorne zu beginnen! Dieses nicht-iterative Vorgehen ist zum Scheitern verurteilt. :-(

3. Versuchs-Reihe: Durchprobieren möglicher "t"

Ich habe versucht, für eine gegebene unsterbliche Zahl z zu bestimmen, welches die nächste unsterbliche Zahl ist durch anfügen der Zahlen 0..9:

1°z, 2°z, 3°z, 4°z, 5°z, 6°z, 7°z, 8°z, 9°z, 0°z

(° = Konkatentation)

bzw.



bzw. (meine bevorzugte Notation)



Eine dieser durchprobierten t-Konkatenation muss die Formel:



erfüllen und ist damit die nächste unsterbliche Zahl.

PROBLEM: Der Algorithmus ist super-langsam, da das Quadrat vollständig errechnet wird.

4. Versuchs-Reihe: Lösen mithilfe der "t"-Bestimmung von René

Mithilfe der Formeln von René Gruber

,



und

konnte ich das erste Mal ein iteratives Vorgehen erreichen.

Ich kann also von Zahl M6(u) auf Zahl M6(u+1) schließen (unter der Berücksichtigung, dass mein Programm die Parameter r' und s' gespeichert hat).

PROBLEM: Der Algorithmus wird extrem langsam. Die Ausführungszeit von M6(2000) im Vergleich zu M6(1000) ist 17-fach langsamer! Die Errechnung großer Zahlen ist wohl daher nicht erfolgsversprechend. (Ich habe in viel Kleinarbeit etliche Performance-Verbesserungen durch z.B. Bit-Verschiebungen bei 2er-Potenzen etc. erzielt, allerdings ist es nur geringfügig besser geworden)

Ich glaube, es hat etwas damit zu tun hat, dass die Parameter r und s gigantisch groß werden. Ich habe lange überlegt, ob diese r und s Parameter irgendwie durch ein Modulo verringert werden können, bin aber auf keine Idee gekommen.

5. Versuchs-Reihe: Das Lösen mithilfe der Formel von René von heute





Ich habe diese Formel in ein Java-Programm verfasst, komme allerdings auf ein anderes Ergebnis!

Ich komme bei u=6 und M5(5)=90625 auf M5(6)=2890625 mod 10^6 und nicht wie René auf 4890625. (Fehler im Post?)

Ich konnte den Algorithmus trotzdem anwenden, um zu prüfen, ob das Ende stimmt. Allerdings habe ich die Vermutung, dass ich die Formel trotzdem falsch verstanden oder angewandt habe.

Diese Couchy-Formel scheint irgendwie nicht für alle u zu funktionieren. Denn bei dem Versuch, einen Nachfolger für die Zahl

z=557423423230896109004106619977392256259918212890625

zu finden, stürzt das Programm ab. Es findet keinen Nachfolger. Möglicherweise kommen zu diesem Zeitpunkt nun zwei Nullen hintereinander, wodurch das Couchy-Produkt gleich bleibt und man weitere Glieder bräuchte, um zu bestimmen, was vor den 2 Nullen stehen würde! (Alle vorherigen unsterblichen Zahlen konnten mit dem Algorithmus gut erkannt/berechnet werden! Ebenfalls funktioniert es, wenn ich das Quadrat vollständig bestimme!)

Ein weiteres Problem bei dieser Formel ist, dass sie im Moment sehr langsam ist, da ich die 3-Summenformeln bei jedem neuen u nocheinmal komplett neu berechne. Es wäre günstiger, wenn ich zu der alten Folge immer nur ein Glied hinzufügen müsste, was mir durch Probieren/Experimentieren allerdings nicht gelungen ist.

Ein weiteres Problem an der Formel ist, dass durch diese hintereinandergeschriebene Summenformel, manchmal auf ein mit n<0 zugegriffen werden will. Ich habe das Programm angewiesen, diesen Zugriff mit "0" zu quittieren.






Mein Wunsch/Ziel ist es, die Zahl M6(u+1) bzw. M5(u+1) mithilfe des Wissens über M6(u) bzw. M5(u) effektiv zu berechnen. Die Geschwindigkeit des Algorithmus soll bei großen u nicht exponentiell abfallen, sondern annähernd linear bleiben. (Sprich: Parameterzahlen wie r oder s aus Versuchs-Reihe #4 sollten nicht ins unendliche wachsen. Man sollte nach Möglichkeit mit kleinen Werten kontinuierlich weiterrechnen können.).

Hat jemand eine weitere Idee oder eine Verbesserungsidee zu den anderen Versuchsreihen?

Kannst du, wisili oder René, mir erzählen, was es mit dem Couchy-Produkt auf sich hat (evtl. wo mein Fehler liegt)? Wie kann ich mit diesem Produkt sinnvoll und effektiv von M5(u) auf M5(u+1) auf M5(u+2) kommen, ohne viel zu rechnen und mit der Garantie, dass das Programm nie stehen bleibt (z.B. weil viele Nullen aufeinander folgen würden)?

PS: Über eine algorithmische Notation/Hinweise würde ich mich freuen.

Gruß und schönes Wochenende
Daniel




(Falls jemand was damit anfangen kannsmile

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
	private static BigInteger x(String z, int u) {
		BigInteger x = BigInteger.ZERO;
		for (int k = 0; k <= u - 1; k++) {
			for (int m = 0; m <= k; m++) {
				x = x.add(a(z, m).multiply(a(z, k - m)).multiply(
						BigInteger.TEN.pow(k)));
			}
		}
		return x;
	}

	private static BigInteger y(String z, int u) {
		BigInteger y = BigInteger.ZERO;
		for (int m = 1; m <= u - 1; m++) {
			y = y.add(a(z, m).multiply(a(z, u - m)).multiply(
					BigInteger.TEN.pow(u)));
		}
		return y;
	}

	private static boolean isImmortable(String z) {
		int u = z.length() + 1;

		BigInteger x = x(z, u);
		BigInteger y = y(z, u);

		BigInteger za = x.add(y).mod(BigInteger.TEN.pow(u + 1));

		String rr = z.substring(z.length()-(u-1));
		
		return za.toString().endsWith(rr);
	}
René Gruber Auf diesen Beitrag antworten »

Bin doch etwas eher da, und die Effizienz hat mir auch keine Ruhe gelassen. Big Laugh


Es geht durchaus schneller, wenn man mal alles mal ganz genau unter die Lupe nimmt: Betrachtet man



also das von mir oben "abgebrochene" Cauchy-Produkt zur Berechnung von , dann ergibt sich die Rekursion

,

( wie "temporär") letzteres wegen .

Wir splitten jetzt auf: In die letzten Stellen, die die in Verlaufe der Rekursion schon bekannte Zahl bilden, sowie den Übertrag , d.h. , die letzte Ziffer von ist dann übrigens die neu gewonnene Ziffer . Mit (*) ergibt sich







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

Damit ergibt sich folgende leicht und schnell zu programmierende Rekursion:

Zitat:
Initialwerte

Iteration sowie für alle

Mal die ersten paar Iterationsschritte ausführlich aufgeschrieben:











soweit erstmal die Schritte bis zu . Als C-Progrämmchen könnte die Berechnungsprozedur so aussehen

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
/* Berechnet a[0]..a[n-1], also bis einschliesslich M_5(n) .                                    */
/* Es wird vorausgesetzt, dass das Feld a auf einen genuegend grossen Platz fuer n Bytes zeigt! */
void BerechneUnsterblich (unsigned char *a, int n)
{
  int r,s,u,m,k;
  if (n <= 0) return;
  a[0] = 5;
  if (n <= 1) return;
  a[1] = 2;
  r = 2;
  u = 1;
  while (u < n-1)
  {
    r = (r-a[u])/10 + a[u];
    s = 0;
    for (m = 1, k = u; m < k; m++,k--) s += a[m]*a[k];
    r += 2*s;
    if (m == k) r += a[m]*a[m];
    a[++u] = r % 10;
  }
}

Die Berechnung mit dauert damit nur noch ca. 2,8 Sekunden auf meinem PC, die Ziffern poste ich jetzt aber nicht, sondern "nur" die letzten 1000:

12781254001336900860348890843640238757659368219796
26181917833520492704199324875237825867148278905344
89744014261231703569954841949944461060814620725403
65599982715883560350493277955407419618492809520937
53026852390937562839148571612367351970609224242398
77700757495578727155976741345899753769551586271888
79415163075696688163521550488982717043785080284340
84412644126821848514157729916034497017892335796684
99144738956600193254582767800061832985442623282725
75561107331606970158649842222912554857298793371478
66323172405515756102352543994999345608083801190741
53006005605574481870969278509977591805007541642852
77081620113502468060581632761716767652609375280568
44214486193960499834472806721906670417240094234466
19781242669078753594461669850806463613716638404902
92193418819095816595244778618461409128782984384317
03248173428886572737663146519104988029447960814673
76050395719689371467180137561905546299681476426390
39530073191081698029385098900621665095808638110005
57423423230896109004106619977392256259918212890625


P.S.: Bezugnehmend auf

Zitat:
Original von blackdrake
Ich habe diese Formel in ein Java-Programm verfasst, komme allerdings auf ein anderes Ergebnis!

Ich komme bei u=6 und M5(5)=90625 auf M5(6)=2890625 mod 10^6 und nicht wie René auf 4890625. (Fehler im Post?)

Das Cauchyprodukt oben bei mir ist nicht vollständig ausgeführt: Es dient einzig und allein zur Berechnung der einen (!) nächsten Ziffer vor 90625, und das ist Ziffer 8. Dass die noch weiter vorn liegenden Ziffern auch schon stimmen, habe ich nie behauptet und íst - wie an deinem Beispiel zu sehen - auch nicht zutreffend. Die Berechnung dieser Ziffern bleibt dann den nächsten Iterationsschritten vorbehalten. Aber vielleicht hat sich diese Frage auch sowieso schon mit dem obigen Teil meines jetzigen Posts erledigt. Augenzwinkern

Zitat:
Original von blackdrake
Ein weiteres Problem an der Formel ist, dass durch diese hintereinandergeschriebene Summenformel, manchmal auf ein mit n<0 zugegriffen werden will.

In der Formel erfolgt ganz sicher kein Zugriff auf Elemente mit . Schieb also nicht Sachen auf die Formel, wenn du die Formel falsch programmiert hast. Augenzwinkern
blackdrake Auf diesen Beitrag antworten »

Hallo René,

vielen vielen vielen Dank für deine Überlegungen und diesen tollen Algorithmus! Durch die C-Vorlage war die Implementierung in Java auch sehr schnell und ich musste nur noch die Load- und Save-Funktionen einbauen. Ich bin begeistert von der gigantischen Geschwindigkeit dieses Algorithmus, die auch bei großem u nicht wesentlich abfällt. Der iterative Algorithmus ist erstaunlicherweise sogar schneller als der chinesische Restsatz (für ein festes u) und ich kann mit (annähernd) "kleinen" Zahlen rechnen, was starke Performance mit sich bringt (trotz Java VM).

Du warst mir eine riesen Hilfe Mit Zunge

Der aktuelle Fortschritt bei meinem "Computing Projekt" kann weiterhin online nachverfolgt werden:
http://beta.viathinksoft.de/~daniel-mars...ing/immortable/

Mein Ziel ist es, hoffentlich die Zahl MAX_INTEGER (2147483647) zu erreichen. Danach werde ich mal weitersehen, ob es technisch noch weiter geht. Ich werde wohl in den nächsten Tagen noch ein wenig am Programm schrauben - darunter auch ein wenig "schnickschnack" wie regelmäßige Backups der Testdaten und regelmäßige Stichproben der aktuellen Zahl (= vollständiges Quadrat berechnen, um irgendwelche Schreib- oder Rechenfehler bei fehlerhaften Fortsetzung auszuschließen) einbauen. Es ist denke ich noch wichtig, dass ich das "r" (das leicht, aber dafür sicher anwächst und größer ist als "u") in einen "BigInteger" zu verwandeln, der nach oben nicht begrenzt ist und auch nicht überläuft. Ansonsten dürfte ja nichts überlaufen. (Dass "u" überläuft ist wohl Zukunftsmusik, und dann ist es fragwürdig, ob vorher nicht eine andere Systemresource erschöpft ist)

Viele Grüße und eine schöne Woche Wink
Daniel



(An alle, die ich für die "Unsterblichen Zahlen" interessieren konnte: Ich bin OpenSource-Entwickler und teile meine Quelltexte/Serverscripts auch gerne)
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von blackdrake
Es ist denke ich noch wichtig, dass ich das "r" (das leicht, aber dafür sicher anwächst und größer ist als "u") in einen "BigInteger" zu verwandeln, der nach oben nicht begrenzt ist

Darüber habe ich mir auch schon Gedanken gemacht: Eine Worst-Case-Abschätzung ergibt , d.h. selbst mit 32Bit-Integer-Zahlen funktioniert der Algorithmus sicher bis zu ca. 23 Millionen. Mit 64Bit-Integer ist man bereits jenseits von Gut und Böse. Für dein Ziel würde ich mir an deiner Stelle aber einen leistungsstarken Computer zulegen und dabei den obigen Algorithmus parallelisieren: Denn mit dem obigen Programm würde ich trotz stark optimiert compilierten Codes mindestens 40 Jahre (!) brauchen. Diese Schätzung basiert auf dem leicht erkennbaren Algorithmusaufwand , und ist sogar leider als zu optimistisch einzuschätzen, da der Algorithmus für datenmäßig noch voll im L2-Cache des Prozessors abläuft, was bei nicht mehr der Fall ist - es könnten also auch 100 Jahre sein, was allerdings nun auch keine Rolle mehr spielen dürfte. Augenzwinkern

Parallelisierungsansätze gibt es natürlich bei der inneren Berechungsschleife

code:
1:
    for (m = 1, k = u; m < k; m++,k--) s += a[m]*a[k];
was für große sicher recht gut und ohne große Verluste geschehen kann.
blackdrake Auf diesen Beitrag antworten »

Hallo René.

Schön, dass ich da zufällig auch einen PC-Experten getroffen habe ^^

Das mit dem quadratischen Anstieg habe ich gerade beim Vergleichen herausgefunden Big Laugh Die Hochrechnung wollte ich dann später machen. Uuu, 40 Jahre sind ja heftig ;-)

Zum Vergleich dazu, betrug die Hochrechnung des Chin. Restsatzes für MAX_INTEGER bei 170 Tagen. (Allerdings ohne Garantie, dass der Arbeitsspeicher das bis zum Ende aushält) -- aber wie gesagt ohne Mehrwert, weil man nicht iterativ weiterrechnen kann.

Nun, ich freue mich jedenfalls, dass das Programm iterativ läuft und auch noch viel schneller ist als alles, was ich je zuvor in diesem Gebiet versucht hatte (die unsterblichen Zahlen hatten mich schon länger beschäftigt und meine ersten Versuche waren arg ... seltsam).

Du meinst also, als Parallelisierungsidee/Distributed Computing, dass die inneren Schleifen im Vorhinein von verschiedenen Rechnern berechnet werden, irgendwo abgelegt werden und dann einfach nur noch vom "Master-Prozess" verwendet werden?

Gruß
Daniel
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von blackdrake
Du meinst also, als Parallelisierungsidee/Distributed Computing, dass die inneren Schleifen im Vorhinein von verschiedenen Rechnern berechnet werden, irgendwo abgelegt werden und dann einfach nur noch vom "Master-Prozess" verwendet werden?

Wenn du das "vorher" nur auf die innerste Schleife beziehst, also nicht auf die äußere while-Schleife, dann stimmt es. Die innere Schleife umfasst etwa u/2 Iterationen, wobei Daten eingehen, die in der Berechnung nicht aufeinander aufbauen. Also könnte man z.B. auf einem Vierkernprozessor jeden Kern etwa u/8 dieser Multiplikationen (und Aufsummierungen) übernehmen lassen und dann die Ergebnisse wieder zusammenführen - so in etwa habe ich mir das gedacht. Allerdings bringen dich 4 Kerne statt 1 Kern bei 40 Jahren auch nicht so entscheidend weiter. Jetzt könnte man natürlich weiterphilosophieren mit GPU-Computing usw., aber das kenne ich nur vom Lesen, nicht aus praktischer Erfahrung. Augenzwinkern

Zitat:
Original von blackdrake
Zum Vergleich dazu, betrug die Hochrechnung des Chin. Restsatzes für MAX_INTEGER bei 170 Tagen.

Den genauen Algorithmus dazu kenne ich nicht, aber offenbar ist der nicht , sondern nur o.ä.

Das wäre dann für große natürlich die bessere Wahl.


P.S.: Mit deinem Java geht es etwas gemächlich zu, bist jetzt (29.11.2010, 17:20) auf

http://beta.viathinksoft.de/~daniel-mars...ing/immortable/

erst bei ca. . Dafür hatte mein obiges Programm (kompiliert mit Visual C++ .NET 2008) bei auch nur einem Kern ca. 20 Minuten gebraucht. Augenzwinkern
blackdrake Auf diesen Beitrag antworten »

Zitat:
Original von René Gruber
Also könnte man z.B. auf einem Vierkernprozessor jeden Kern etwa u/8 dieser Multiplikationen (und Aufsummierungen) übernehmen lassen und dann die Ergebnisse wieder zusammenführen


Achso... jetzt erst hab ich das verstanden. Ja, das wäre sicherlich sinnvoll, dass man die Schleife zerteilt und für große u auf verschiedene Kerne legt. Leider hat mein Root-Server nur 1 Kern (2793 MHz, 512 MB RAM).

Zitat:
Original von blackdrake
Dafür hatte mein obiges Programm (kompiliert mit Visual C++ .NET 2008) bei auch nur einem Kern ca. 20 Minuten gebraucht. Augenzwinkern


Mh... nun, das kann verschiedene Gründe haben. Ich denke
1) Weil es Java ist und unter einer VM läuft (Aber ich liebe die Programmiersprache so sehr...)
2) Ich nutze nicht so ein schön performantes byte-Array "a", sondern einen Vector (eine Art Liste) mit Integers. Das gute daran ist, dass ich das "a" immer wieder um ein Element erweitern kann, allerdings geht das wohl sehr zu Lasten der Runtime.
3) Meine Wahl, nach allen 10.000 Stellen zwischenzuspeichern ("a" in einen String wandeln, diesen in eine Datei schreiben etc) war wohl etwas zu knapp bemessen. Ich hätte lieber alle 100.000 Stellen speichern sollen.

Ich spiele mit dem Gedanken, mein Java-Programm (das wirklich sehr gut geworden ist, automatisch lädt, speichert, backups macht und Integritätstests der Daten bei jedem Programmstart etc) in C99 (GCC) zu portieren (vielleicht auch C++, wenn ich mutig/lebensmüde bin...) Dort soll es ja auch eine BigInteger-Unit geben (die ich zwar im Moment nicht für das "r", dafür aber für den isImmortable()-Test brauche, der verhindern soll, dass an einer fehlerhaft geschriebenen Datei (falsch) weitergerechnet wird. Ich denke, das Problem mit dem Array löse ich, indem ich ein mit malloc() belegten Speicher alle 1.000.000 Stellen neu anlege, kopiere und erweitere. (Jeweils um 1 MB dann) Das dürfte wohl performant sein. Mal schauen.

Das mit den 40 Jahren hab ich wie gesagt nicht gedacht, aber daher ist mir das Ziel auch nicht mehr so wichtig. Hauptsache ist: Ich schreibe ein (noch) performanteres Programm und erfreue mich daran, dass der Server 24/7 eine immer größere Zahl erzeugt ^^ (Im Moment sind es 2,5 Mio stellen 18,5 Stunden. Das ist jede Menge Asche :-p )

PS: Vorteil ist, dass ich durch das Definieren eines Dateiformats jederzeit mein Rechen-Programm wechseln/erweitern kann, ohne dass ich die Suche nochmal von vorne beginnen muss.

PPS: Wenn du erlaubst, setze ich deinen Namen auch in das Copyright, wenn ich den Code mal OpenSource mache. Ohne dich gäbe es diese tolle Formel und den damit verbundenen performanten Quellcode zur Berechnung nicht. :-)

Gruß
Daniel
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von blackdrake
Wenn du erlaubst, setze ich deinen Namen auch in das Copyright, wenn ich den Code mal OpenSource mache.

Das macht aus zweierlei Gründen wenig Sinn:

Erstens ist mein Boardname René Gruber nur ein Pseudonym. Und zweitens baut die Iteration auch nur auf der Idee von wisili auf. Wenn du aber statt mir dem ganzen Matheboard ein kleines Dankeschön in deinem Copyright widmest, dann sind wohl alle zufrieden. Augenzwinkern
blackdrake Auf diesen Beitrag antworten »

Hallo.

Ok, werde ich machen. Vielen Dank euch beiden für euere große Hilfe. :-)

<Offtopic>PS: Ich habe das Programm nun in C++ portiert und rechne nun mit einem Geschwindigkeitsabfall von 11 Sekunden pro 100.000 Stellen. (Bei meinem ersten Java-Programm mit Listen waren es 199 sec/100.000digits und bei der optimierten Java-Version waren es 30 sec/100.000digits.) Jetzt ist es High-Speed. (Trotzdem dauert es bis MAX_INT noch bis 2091 ;-) ) Erstaunlich: Die C++ Version ohne Compileroptimierung hat 43 sec/100.000digits erbracht, also langsamer als die Java-Version!</Offtopic>

Nun denn, ich komme nun alleine weiter und habe zu dem Thema auch (bis jetzt) keine Fragen mehr. Es ist sehr interessant und bleibe an dem Projekt auf jeden Fall dran. Quelltext gibt's auch schon auf der ("unoffiziellen") Seite.



PS: Die Zeit "2091" konnte ich mit der folgenden Formel ermitteln:



wobei f''(a) der Geschwindigkeitsabfall in Sekunden pro 100k Digits ist, bzw. die 2te Ableitung der Zeit seit Rechenbeginn für den Schritt a ist (1 Schritt = 100.000 Stellen). Dieser Geschwindigkeitsabfall ist für alle a konstant (und wird kleiner, wenn der Algorithmus/PC schneller ist). f(a) ist die hochgerechnete Zeit seit Rechenbeginn für einen Schritt a.

Für meinen (neuen) Algorithmus ist damit:



Gruß
Daniel
blackdrake Auf diesen Beitrag antworten »

Hallo,

ich wollte mich mal wieder dazwischenmelden, da ich wieder mich ein bisschen mit dem "Projekt" beschäftige. Die ganze Zeit über hat mein Server fleißig gerechnet und schon 126.600.000 Stellen der ...25 Zahl gefunden.

Ich habe ein paar Überlegungen zu unsterblichen Zahlen in verschiedenen Basen angestellt und habe folgende Theorie, leider ohne Beweis:

Theorie für jede beliebige Basis (VERSION 2)

der Länge ist zu der Basis unsterblich, wenn gilt:



...


bzw.





wobei
1)
und
2) Primfaktoren von , bei denen gleiche Primfaktoren zu einem einzelnen Faktor durch Multiplikation zusammengefasst werden (*), sind
und
3) der kleinste kanonische Wert dieser Kongruenzgleichung ist.

(*) Beispiel - Basis hat die Primfaktoren 2*2*2*3=24 . Allerdings kommt die 2 drei Mal vor. Daher werden diese drei Faktoren zu "8" zusammengefasst. Das Ergebnis ist 3*8=24. Somit ist und .

Anderes Beispiel: Basis b=36 hat die Primfaktoren 2*2*3*3 . Hier kommt die 2 und die 3 mehr als einmal vor. Sie werden zusammengefasst. Das Ergebnis ist 4*9=36 . Somit ist und .


Hat eine Basis nicht mindestens 2 ungleiche Primfaktoren, so hat sie nur die trivialen unsterblichen Zahlen 0 und 1, da es nur 1 Kongruenzgleichung gibt.

=> PROBLEM 1: Kann man das beweisen? Gibt es Widerspriche oder ist etwas nicht für alle Fälle beachtet? Ich kann leider aus der bisherigen Erkenntnis mit nicht auf diese allgemeine Kongruenzgleichung schließen.

Beispiel mit der Basis 6

Primfaktoren sind , , .

Dann ist unsterblich zur Basis wenn gilt




Mit erhalten wir die Tupel :

(1,0)

(Die Zahl im Index ist meine Notation für die Basis abweichend von 10.)

(0,1)

(1,1)

(0,0)

sowie die bekannte Symmetrie

(Anmerkung zur Formalität: Die Notation z.B. stehe in meinem Beitrag für "die unsterbliche Zahl zur aktuellen Basis und Länge mit den Parametern und , formal .)



Ein Test, ob wirklich unsterblich ist: , korrekt, da auf 213 endend.

Algorithmus zur Findung aller unsterblichen Zahlen bei Basis 30

Es war bei Basis 6 und 10 einfach, das "Komplementär" zu finden, da es nur 2 "Stämme" (Permutationen von ) gab und die Summe beider immer 101, 1001, 10001 etc. ergab).

Ein neues Problem ergibt sich bei Basis 30. Hier gibt es insgesamt 6 Stämme (ohne die 2 Trivialen 0 und 1 Stämme) bei 8 Permutationen.

Primfaktoren:



ist zur Basis unsterblich wenn für und gilt:





Folgende Zahle sind unsterblich bei (Anwendung des chinesischen Restsatzes mit allen Permutationen ):

(0,0,0)
(0,0,1)
(0,1,0)
(0,1,1)
(1,0,0)
(1,0,1)
(1,1,0)
(1,1,1)

Es wird auch deutlich, dass es hier 8 "Stämme", davon 2 triviale 0 und 1 gibt:

0, 1, 6, 10, 15 (F), 16 (G), 21 (L), 25 (P)


Auch hier ergibt sich wieder, dass (für die jeweilige Basis)

Also

Hier ergibt sich nun das Problem, dass ich zur Berechnung aller 6 (bzw. inklusive der trivialen Stämme: 8) Stämme mindestens 2 Stämme berechnen muss.

Ein beispielhaftes Vorgehen zum Finden aller Stämme wäre:

1.
2.
3.
4.
5.
6.
7.
8.

Man kann natürlich auch rechnen etc.

Dass man schreiben könnte, folgt aus .

Der Algorithmus für Basis 30 (PROBLEM 2)

Für die Berechnung des Stammes , also zur Berechnung der Gleichung





kann ich den fortführbaren Algorithmus von René verwenden. Es muss lediglich die Basis 10 mit 30 ausgetauscht werden:



Dies würde es ermöglichen, das Computerprogramm nun auch einen unendlich langen Stamm, der auf Q7F endet, zu finden.

=> Problem 2: Das Problem besteht nun aber bei der Findung der anderen Stämme. (Mit einem möglichst performanten und iterativen Algorithmus)

Dass man aus diesem einen Stamm alle anderen findet, ist wohl unmöglich, wenn ich mich nicht irre, da man zwar rechnen kann



allerdings gibt keinen Aufschluss über oder .

Allgemein gilt: Bei einer Basis mit n unterschiedlichen Primfaktoren gibt es Permutationen und somit Stämme (inklusive der 2 trivialen Stämme , der nur 1 ergibt und , der nur 0 ergibt) . Es müssen n-1 Stämme gefunden werden, um alle möglichen Stämme zu finden.

Ich muss daher noch einen zweiten Stamm parallel berechnen. Das Problem ist, dass der obige Algorithmus bei diesen Gleichungen nicht funktioniert. Ich bin mir nicht sicher, ob es daran liegt, dass nun "0 mod 2" und nicht "1 mod 2" gefordert ist oder ob die Gleichung allgemein nicht funktioniert für einen zweiten Stamm.

Zur Findung aller Stämme brauche ich also eines der folgenden Stämme: oder oder .

=> Problem 3: Kann man einen ähnlichen Algorithmus, der auf dem vorhandenen Wissen mit den Cauchy-Produkten, aufbaut finden, der eine solche Gleichung allgemein lösen kann? -- Wichtig ist, dass der Algorithmus iterativ ist.


Ich freue mich über jede Art von Hinweisen, Lösungsansätzen und Hilfen. Fragen und Vorschläge sind willkommen.


Grüße
Daniel Marschall


PS: Ein paar Tools, die sehr hilfreich sind
- Basenkonverter: http://www.kaagaard.dk/service/convert.htm
- Chin. Restsatz-Tool: http://www.arndt-bruenner.de/mathe/scrip...herRestsatz.htm
- Primfaktorzerlegung: http://www.mathetools.de/primfaktorzerlegung/

(Edit: Komplette Überarbeitung aufgrund neuer Erkenntnisse)
René Gruber Auf diesen Beitrag antworten »

Ich hab jetzt (noch) nicht alles durchgelesen, aber eine kleine Kritik der Notation:

Zitat:
Original von blackdrake
wobei

So geschrieben versteht man darunter gewöhnlich eine reelle Zahl mit .

Was du meinst, ist aber sicher .
blackdrake Auf diesen Beitrag antworten »

Zitat:
Was du meinst, ist aber sicher .


Die Kritik ist gerechtfertigt. Ich habe den Notationsfehler behoben. Vielen Dank für den Hinweis.
blackdrake Auf diesen Beitrag antworten »

Hallo.

Ich habe in der Zwischenzeit ein Java-Programm geschrieben, dass die Basen 2 bis 1.000 durchläuft und für die Zahlen 2 bis 1.000.000 prüft, ob sie zu der Basis immortal sind. Ich erhoffe mir dadurch mehr Überblick und eventuell doch noch eine Gesetzmäßigkeit zu finden.

Das Programm baut auf die für Basis 10 gültige Aussage, die mit Hilfe der vollständigen Induktion gefunden werden konnte (s.o.), auf. Ich denke, dass diese Aussage für alle Basen gilt.


Bisheriger Satz für Basis 10: Endet auf , so enden alle auf und somit ist unsterblich.




Allgemeiner formuliert: Endet auf , so enden alle auf und somit ist zur Basis unsterblich.






Anmerkung zur Notation / Definition

- : Es gibt genau ein definiertes . (Ich weiß nicht, wie üblich die Notation mit dem Ausrufezeichen ist)

- Neue Notation: : Zahl dargestellt zur Basis

- : konkateniert mit (Basen sollten gleich sein. Sind sie das nicht, wird die höchste Basis als Konkatenierungsergebnis gewählt)

- Definition: : Die Menge aller zur Basis unsterblichen Zahlen (Lies: Immortal-b-Zahlen).



Hier meine Ergebnisse und der Programmquelltext

- Ergebnisse (Basis 2-1000): http://beta.viathinksoft.de/~daniel-mars...arch_result.txt

- Quelltext (Java): http://beta.viathinksoft.de/~daniel-mars...mortSearch.java


Anmerkung: Da ich mit Basen arbeite, die größer als 36 sind und somit keine Buchstaben verwendet werden können, habe ich die Notation "(Stellenwert)(Stellenwert)(Stellenwert)..." gewählt. z.B.

Ich freue mich über jede Art von Hinweisen und Lösungsansätzen. Kritik zu der Formalität ist auch erwünscht, da ich immer versuche, möglichst formal korrekt zu sein.

Gruß
Daniel Marschall

(Edit: Kompletter Editierung dieses Posts. Ich hatte zuvor etwas behauptet, was falsch war, da ich in meinem Programm einen unbemerkten Integer-Überlauf hatte.)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »