Code anzeigen!
Problem/Aufgabenstellung in der Wikipedia
Der englische Artikel ist um Größenordnungen besser als der deutsche:
Wikipedia: Collatz conjecture
Man kann sich die Collatz-Reihen sehr einfach anschaulich vorstellen als
Verkettung von Reihenfragmenten, die in sich jeweils Zweier-Potenzreihen darstellen,
die jeweils mit einer ungeraden Zahlen multipliziert sind. Die betreffende ungerade
Zahl nenne ich mal im weiteren
"Restfaktor" - weil es gewisse gefühlsmäßige und
logische Ähnlichkeiten zu Restklassen gibt. Da ich kein studierter Mathematiker bin,
muß der Rest (;->) der Mathematikerwelt sich da beim Lesen zusammenreißen, basta!
An jeder ungeraden Zahl hängt also eine Zweier-Potenzreihe als "Fahne".
Zwischen den verschiedenen Zweierpotenzreihen gibt es Übergänge (
"Sprünge") jeweils an ihrem
untersten Glied (der jeweiligen ungeraden Zahl alias dem Restfaktor), zum Beispiel:
. .
. *3+1 . 208
64 / . / \ .
*2 -> / \ / . 40 104 \ .
32 \ . / \ . / 69
*2 -> / 21 20 \ . 52 .
16 . / 13 / \ .
*2 -> / \ . <- *4+1 10 . 26 \ .
8 \ . / \ . <- *4+1 / 17
*2 -> / 5 5 \ . 13
4 . 3
*2 -> / \ . <- *4+1
2 \ .
*2 -> / 1
1 |
| |
+------+ <- Hier entsteht die offenbar einzig existierende Schleife der Reihenverkettungen
Jedes zweite Glied einer solchen Zweierpotenzreihe ist genau unter der Bedingung,
daß die ungerade Zahl
ist, Ziel eines Übergangs aus einer
(zunächst mal beliebigen) ANDEREN Reihe (mit einer ANDEREN ungeraden Zahl am Ende).
Nennen wir diese Sprungziele mal der Anschaulichkeit halber
"Saugnäpfe",
die "Fahnen", an denen die Saugnäpfe hängen, eventuell anschaulicher
"Fangarme"!
Jede existierende ungerade Zahl erzeugt einen solchen Fangarm. Wir können sie auch
als "Generatorzahl" für ihren Fangarm bezeichnen. "Restfaktor" und "Generatorzahl"
sind zwei anschauliche Begriffe, die ich im folgenden für diese Sache verwenden werde.
An den Fangarmen hängen jeweils unendlich viele gerade Zahlen als Stützstellen.
Da es allerdings genau "
gleich viele gerade und ungerade" Zahlen gibt, müssen wir
hier die Bereiche mit in Betrachtung ziehen, auf die sich das jeweils bezieht:
Die erzeugten und am Fangarm hängenden geraden Zahlen reichen in die Unendlichkeit
hinaus und nehmen in ihrer
Dichte exponentiell ab. Wenn man die Betrachtung auf
einen Bereich bis zu einem Grenzwert beschränkt, werden zusammen mit den Fortsetzungen
der Potenzreihen immer geradeso sämtliche geraden Zahlen dieses Bereiches von den Fangarmen
abgedeckt. Das Gleichgewicht zwischen den geraden und ungeraden Zahlen ist also
trotz der 1 : unendlich - Beziehung exakt gewahrt.
Von 2/3 aller Fangarme (nicht denen mit durch 3 teilbarem Restfaktor) sind genau
50% aller Stützstellen - mithin also 1/3 sämtlicher erzeugten Stützstellen auf
Fangarmen - Ziele von "Sprüngen", also "Saugnäpfe".
Der "Sprung" (die Operation "*3 +1") - in der Skizze von rechts unten nach links oben -
darf auch umgedreht betrachtet werden. Er führt dann ausgehend von der Startreihe
(mit dem Restwert "1" und dem 4-2-1-Zyklus) zum unendlich fortgesetzten Einbinden
weiterer Reihen in einen Menge, die ihre
Iterationen allesamt bei der Startreihe
mit dem 4-2-1-Zyklus "abliefern".
Das ergibt auf den ersten Blick eine komplett dichte Abdeckung des Wertebereiches
mit Saugnäpfen - weil wegen dem in der Sprung-Operation enthaltenen "*3" zu den
ungeraden Zahlen innerhalb eines Bereiches exakt 1/3 aller geraden Zahlen im
entsprechend höher liegenden Wertebereich als Saugnäpfe benötigt werden.
Diese Dichte wird nach dem betrachteten Schema
gerade eben exakt bereitgestellt.
Zudem "transportieren" alle Reihen ihre "Nutzlast" (die Iteration) unendlich weiter,
solange sie die Iteration NICHT ABBRECHEN. DAS passiert genau dann, wenn eine
Iteration in einen "Zyklus" läuft. Ein solcher entsteht am unteren Ende der
"puren" Zweierpotenzreihe (mit der "1" als Restfaktor) in der Form "4-2-1".
"Kurze" Zyklen wie in der Zweierpotenzreihe mit Restfaktor "1" können nirgendwo
anders entstehen, was an der Sprungoperation "*3 +1" liegt: Die ergibt einen
Folgewert, der gerade zu groß für das nächste Folgenelement (*2) und
gerade zu klein für das übernächste Folgenelement (*4) in der eigenen Reihe ist.
AUSSER für den Zyklus "4-2-1". Dort reicht die "+1" gerade eben so zum Hochhieven
auf die 4.
Da es aus jener Reihe mit Restfaktor "1" also NIEMALS HERAUS geht, aber jede Menge
(genauer: unendlich viele) Reihen DORT REIN springen, wirkt diese Reihe als "Fänger".
JEDE der sekundär an dieser hängenden Reihen wirkt ihrerseits automatisch und zwingend
EBENFALLS als Fänger, der die Iterationen garantiert zum "4-2-1"-Zyklus leitet.
Jede Reihe, die an einer der sekundären Reihen hängt, wirkt ebenfalls als Fänger
des "4-2-1"-Zyklus und so weiter bis ins Unendliche.
Tatsächlich ergibt sich beim Experimentieren, daß jede beliebige Zahl, die man
zum Ausgangspunkt wählt, in dem Reihenwald irgendwann auf der 1er-Restreihe
im "4-2-1"-Zyklus landet.
Der Mathematiker "Collatz", der sich diese Spielerei ausgedacht hatte, hatte die
Vermutung geäußert, daß tatsächlich jede Iteration von jeder AUsgangszahl her
zwingend in den "4-2-1"-Zyklus laufen MUSS.
Das wird seither auch "Collatz-Vermutung" genannt.
Das Problem bei der Sache ist, daß die Dichte der Saugnäpfe und der Umstand, daß
es auf jeden Fall von jedem ungeraden Restwert aus einen Sprung auf eine
Nachbarreihe gibt und daß es zumindest EINE Reihe gibt, an der sich die Iteration
festsaugt sowie unendlich viele, die dieser zuarbeiten,
nicht ausreicht, um zu
beweisen, daß auch
zwingend jede Iteration dort in den "4-2-1"-Zyklus laufen
MUSS.
Es wäre nämlich gemeinerweise durchaus denkbar, daß sich Zyklen über mehrere Sprünge hinweg bilden könnten.
Zudem wäre es denkbar, daß es Reihen-Folgen geben könnte, deren Restfaktoren ins
unendliche wachsen, ohne jemals auf überhaupt irgendeinen Zyklus und seine Fangarme zu treffen.
Man kann das Problem auch ein wenig anders formulieren:
Wenn die Collatz-Vermutung stimmt, dann...
- müßte sich JEDE BELIEBIGE ungerade
Zahl (und über die Zweierpotenzschwänze auch jede gerade Zahl) aus einer
Folge von Operationen *2^i -1 /3 aus der "1" bilden lassen.
- dürfte es für die Operation x2 = x1 {*3 + 1 / 2^i}^n
keine ganzzahlige Lösung mit x2 == x1 geben - außer dem Zyklus "4-2-1".
(Der Inhalt der geschweiften Klammern stellt hier eine Operation dar, nicht
ein Zahlenobjekt, wie sonst üblich...)
Die Operation läßt sich auch ganz hübsch in eine herkömmliche Gleichung übersetzen
(wobei hier davon ausgegangen wird, daß eine ungerade Zahl der Ausgangspunkt ist):
x = Summe[i=1...n](3^(n-i) * 2^Summe[j=1...i-1](pj)) / (2^Summe[j=1...i](pj) - 3^n)
n: Anzahl der Iterationsgruppen, wobei jede davon aus einem Sprung in einen
der Potenzreihen-Schwänze einer anderen ungeraden Zahl und dem Hinabgleiten
an diesem Potenzreihenschwanz auf jene andere ungerade Zahl besteht
pj: Die Mengen der Schritte beim Hinabgleiten der Zweierpotenzrutschen
(Ja, mit MathML wird's hübscher aussehen, aber dazu muß ich mich da erst wieder
reinspielen...)
Zugehöriges
OpenOffice-Rechenblatt, auf dem ich mal mit Konfigurationen gespielt habe...
Das Interessante an dieser Beziehung: Je nach Verteilung der Schritte auf den
Zweierpotenzrutschen müßte es (falls sie überhaupt existieren) zwingend ganz
bestimmte festgenagelte Werte geben, die solche Zyklen bilden können.
Probiert man das mit dieser Gleichung durch, ergibt sich stets nur für den Fall,
daß die pj's alle gleich groß - und zwar "2" - sind, ein ganzzahliges x mit dem Wert "1".
Was dem Zyklus "4-2-1" (mit einer beliebigen Menge an Wiederholungen) entspricht.
JEDE andere Variante, die man PROBIERT, ergibt - selbst wenn man die Notwendigkeit
von ganzen Zahlen als Zwischenwerte der Iterationen außer Acht läßt - immer nur
gebrochene Werte für x. Zudem sind die erreichbaren Werte für x allein von der Menge der
Iterationsgruppen, die man betrachtet (dem "n") abhängig: Großen Zahlen ist es
also vollkommen unmöglich, - wenn überhaupt - kleine Zyklen zu bilden. Je größer
die Ausgangszahl, die zu einem Zyklus gehören soll, desto mehr Iterationsgruppen
muß ein eventuell möglicher Zyklus beinhalten! Kleine Zahlen hingegen MÜSSEN zwingend
- wenn überhaupt - kleine Zyklen bilden. Die Beziehung ist allerdings exponentiell:
Die Größe - möglicher - Zyklen ist proportional dem Logarithmus der beteiligten Zahlen.
Meine mathematischen Fähigkeiten reichen an der Stelle allerdings erstmal nicht aus,
um eine generalisierte Aussage zu Teilbarkeiten der Ausdrucksvarianten zu machen.
Es hat zwar den Anschein, als ob es nichts gibt außer jenem "4-2-1"-Zyklus, was
den Ausdruck glatt teilbar macht (also: mit Parametern aus dem Bereich der natürlichen
Zahlen und der Collatz-Reihenbildung gehorchend), aber das bedeutet leider mitnichten einen
BEWEIS, daß es keinen geben KANN (was der Sinn der "Collatz-Vermutung" ist).
Ein
praktischer Denkansatz: Bis zu Zahlen im Bereich von etwa 2^60 wurde per
Computerspielerei nachgewiesen, daß der gesamte Bereich bis dorthin lückenlos
vom 4-2-1-Zyklus gefangen wird. Das Durchspielen für extrem große Zahlen, deren
Stellenanzahl in die Megabytes geht, ist ebenfalls kein Problem, weil die Anzahl
der Iterationen bis zum Eintreffen auf dem 4-2-1-Zyklus nur logarithmisch mit der
Zahlengröße wächst. Alle willkürlich bislang herausgegriffenen Tests haben
ausnahmslos gezeigt, daß der 4-2-1-Zyklus immer erreicht wurde. Ergo ist die
Wahrscheinlichkeit, daß es mal irgendwo
auch nur EINE EINZIGE (!)
Zahl geben könnte, die aus dem Fangnetz dieses Zyklusses ausbricht, als
äußerst
extrem gering anzusetzen.
DAS setzen wir jetzt in Verbindung zu der Erkenntnis aus der (schon rein oberflächlich
durchgeführt dafür völlig ausreichenden) Gleichungsanalyse von eben: Um irgendwo einen
anderen Zyklus oder eine nach oben offene Reihen-Folge entstehen zu lassen, müssen gleich
mehrere Dutzend (!) Ausnahmen von dieser praktischen Beobachtung entstehen UND
diese müssen zwingend so entstehen, daß sie sämtlich miteinander solcherart in Kontakt
stehen, daß die Sprungoperationen innerhalb einer erwartungsgemäß zumindest nahezu unendlich
dicht von 4-2-1-Saugern abgedeckten Umgebung zielsicher zwischen eben diesen
Ausnahmen treffen und nicht ein einziger der Sprünge daneben geht!
Als Praktiker
darf man hier feststellen, daß dies nicht nur äußerst unwahrscheinlich ist, sondern praktisch unmöglich.
Nichtsdestotrotz ist das nach wie vor kein klassischer, zwingender Beweis der Unmöglichkeit.
Noch ein anderer Denkansatz: Gibt es irgendwelche Besonderheiten mit der Iterations-Folge
der ungeraden Zahlen, also der Rutsche hin zur Restreihe "1"?
Erstmal ein kleiner Test zum Reihenkonstruieren...
Stellen wir doch mal eine geordnete Folge der Restfaktoren auf (die Zeile entspricht
hier der Anzahl der Iterationsgruppen (Sprung + Binär-Rutsche)...
Welcher Anteil der Restfaktoren bis zu einem Grenzwert läßt sich abdecken, wenn
man Zwischenwerte nur bis zu diesem Grenzwert zuläßt und alles andere verwirft?
Aha... Immer etwa ein Zehntel.
Bis zu welchem Grenzwert laufen die Folgen, wenn für einen Bereich durchgehend
die Iterationen durchgespielt werden? Wieviele Iterationen benötigen die Werte?
Die Folgen der Restfaktoren laufen also von einem Ausgangspunkt immer wieder mal
bis zum rund 1-tausend-fachen des Ausgangswertes, um danach eine Zweierpotenzrutsche
hinabzusausen und irgendwo ins etablierte Fangnetz zu geraten.
Die Besetzung des Bereichs der geraden Zahlen, die aus den ungeraden Zahlen als
Schwänze herausregen, ist irgendwann auf jeden Fall dicht genug, um jedes Sprungergebnis
"*3 +1" wegzufangen.
Ähmmm... Könnte man das Problem eventuell auch noch von
jener Seite her aufziehen?
Also: Wenn wir jetzt nachweisen könnten, daß die Menge der auf den Fangarmen in einem
bestimmten vorausliegenden Zahlenbereich generierten geraden Zahlen
EXAKT GLEICH der Menge ALLER im selben Zahlenbereich existierenden
geraden Zahlen ist, dann könnten wir damit beweisen, daß alle Sprünge in
diesen Bereich hinein zwingend zu unserem Zielzyklus führen müssen.
Allerdings kommen wir mit dem Ansatz immer nur bis zum doppelten der Grenze des
soweit jeweils untersuchten Zahlenbereichs (weil die erstbeste ungerade Zahl aus
dem noch nicht untersuchten Bereich ihrerseits eine gerade Fangzahl generiert,
die eben genau doppelt so groß ist wie sie selbst)... Und das reicht nicht.
Oder??
Kommen wir wirklich nur bis zum doppelten? Weil: Da ja an jeder ungeraden Generatorzahl
unendlich viele gerade Zahlen hängen, müßte doch, je höher wir mit dem Grenzwert
kommen, die Abdeckung der geraden Zahlen aus den bereits untersuchten Bereichen
heraus immer dichter und weitreichender werden! Läßt sich daraus noch was anderes
ableiten als die Feststellung, daß die bloße Wahrscheinlichkeit des Vermeidens solcher
Saugnäpfe umso unwahrscheinlicher wird, je größer unsere untersuchten Bereiche werden?
Trifft letzteres überhaupt zu? Nein, wohl nicht:
Ab Grenzwert g(+1) gibt es bis 2*g von genau jeder ungeraden Zahl von 1 bis g
genau eine generierte gerade Zahl in diesem Bereich.
Im Bereich g*2+1 bis g*4 werden genau die Hälfte aller geraden Zahlen
von jenen Zweierpotenz-Schwänzen bereitgestellt und so weiter stetig
exponentiell abnehmend. Also: Die Anzahl der generierten geraden Zahen
bleibt in jedem solchen Zweierpotenz-Bereich gleich, aber die Menge der
insgesamt in diesem vorkommenden geraden Zahlen steigt natürlich proportional
der Zweierpotenz.
Also auf dem Weg kommen wir auch nicht weiter...
Wenn wir nach dem Prinzip der vollständigen Induktion vorgehen wollen::
- Wir weisen nach, daß in einem Bereich bis zu einer Grenze g alles unserer
Aussage genügt, daß jede Collatz-Iteration zu unserem Zielzyklus 4-2-1
führt.
- Wir wollen dann voraussagen, daß sämtliche Sprünge von ungeraden Zahlen aus, die
unseren bisher untersuchten Bereich überschreiten, bis zu einer gewissen
Grenze (die nur um eins (na ja: 2) höher sein muß als unsere bisherige Grenze)
zwangsläufig einen der soweit aus dem untersuchten Bereich generierten
Zweierpotenz-Schwänze treffen muß.
Neee. Fühlt sich eher wie eine Äquivalenz der weiter oben beschreibenen Gleichung
an, mit der ein Zyklus ermittelt wird. Weil wir zwischendurch mit einiger Wahrscheinlichkeit
auf Reihen treffen, die noch nicht aus dem bereits untersuchten Bereich generiert wurden.
Nochmal ein Anlauf, wieder auf pauschalisierter Betrachtung aufbauend:
- Von allen existierenden geraden Zahlen kommt ein Drittel als Sprungziel
der Operation "*3 +1" in Frage. Also: Alle diese Operationen enden immer
auf einem Element jener Menge der geraden Zahlen, die eben ein Drittel
aller überhaupt existierenden geraden Zahlen ausmachen.
- Wenn wir nachweisen, können, daß alle von der Generatorzahl "1" ausgehend
konstruierbaren "Fangarme" mit ihren "Saugnäpfen" eben genau ein Drittel
aller geraden Zahlen ausmachen müssen, dann hätten wir den gesuchten Beweis
erbracht, daß alles in den 4-2-1-Zyklus münden muß...
Wir kommen wir jetzt zum Beweis jenes Drittels...?
- Von der Startreihe mit Restfaktor "1" aus sind genau die Hälfte aller
Stützpunkte der Potenzreihe "Saugnäpfe".
- Jeder der Saugnäpfe erzeugt eine weitere, neue Reihe mit einem anderen Restfaktor.
Nennen wir die mal "Ableger".
- Von deren Restfaktoren ist genau ein Drittel durch 3 teilbar (trivial).
Jene Reihen mit durch 3 teilbaren Restfaktoren erzeugen gar keine
"Saugnäpfe". Alle anderen erzeugen wieder genau 50% Saugnäpfe.
Also: Von allen geraden Zahlen, die den soweit untersuchten ungeraden
Restfaktoren alias Generatorzahlen zugeordnet sind, bilden genau 2/3 * 1/2 = 1/3
"Saugnäpfe" alias Sprungziele für die Operation "*3 +1".
- Wir stellen weiterhin fest, daß das Erzeugen von Ablegern eine sich unendlich
fortsetzende Sache ist.
Wir sehen daraus, daß die Menge der
erzeugten Saugnäpfe gleich der Menge der
notwendigen
Sprungziele ist - daß es also ein
GLEICHGEWICHT gibt zwischen den mit zunehmenden
Zahlenwerten zunehmend benötigten Sprungzielen und jenen Saugnäpfen, die diese Sprungziele
dahingehend abdecken, daß die Iterationen zum 4-2-1-Zyklus hin abgeleitet werden.
Allerdings erstmal ohne scharf umrissene Bereichsgrenze!
Es wäre deshalb noch immer nicht undenkbar, daß es zwei scharf getrennte Bereiche
gäbe, innerhalb derer die Sprünge jeweils in sich komplett abgedeckt werden können, ohne jemals
einen "Seitensprung" in den Nachbarbereich machen zu müssen. Das sieht zwar für
einen Praktiker ganz eindeutig nach Unmöglichkeit aus - angesichts des Nachweises
der kompletten Dichtheit des "Hauptbereiches" bis zu Zahlen über 2^50 hinaus und
nicht eines einzigen wenigstens zufälligen Gegentreffers mit riesigen Zahlen mit
Exponenten bis in den Megabytebereich hinein. Aber der Theoretiker darf immer noch
behaupten: Tatsächlich bewiesen ist das Gegenteil noch lange nicht!
Läßt sich irgendwie ableiten, daß kein Element jenes Drittels der geraden Zahlen
fehlen kann oder darf, wenn wir von der "1"er-Reihe ausgehend Ableger konstruieren und das
unendlich fortsetzen?...
Ich streiche jetzt erstmal die Segel: Mir reicht die Einsicht in die letzte pauschale
Gleichgewichts-Betrachtung zusammen mit den ebenfalls pauschalen Abschätzungen
zur Bestimmungsgleichung von Zyklen (daß für große Zahlen auch aus dem Stand heraus
große Zyklen benötigt werden, also das sporadische Auftreten einzelner Abweichungen
vom normalen Verhalten schlicht nicht möglich ist)
vollkommen hin, um
aus Praktiker-Sicht zu sehen:
Es geht nicht anders!
Die Theoretiker dürfen von mir aus weiter kämpfen um eine saubere Beweisführung...