Programmieraufgaben - Collatz-Reihen

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: Jedes zweite Glied einer solchen Zweierpotenzreihe ist genau unter der Bedingung, daß die ungerade Zahl NICHT durch 3 teilbar 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...

Startwert: (max. 1 Millionen) Los!

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?

Grenzwert: (max. 10'000) Los!

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