Anzeige
Seite 2 von 3 ErsteErste 123 LetzteLetzte
Ergebnis 11 bis 20 von 21

Thema: Collatz Vermutung - Teillösung

  1. #11
    Registriert seit
    05.07.2011
    Beiträge
    1.394

    Standard

    Anzeige
    Zitat Zitat von Nathan5111 Beitrag anzeigen
    Gibt es eine Zahl n+1 (ungerade), die in ihrer 'Entwicklung' keine Zahl kleiner als n enthält?
    D.h.:

    Bekannt sei, dass

    $$\exists n,k \,:\, T^k(n) = 1$$

    Gefragt ist, ob

    $$\not\exists k \,:\,T^k(n+1) \le n$$

    gilt.

    Das ist m.E. nur eine Umformulierung und hilft noch nicht weiter. Wenn letzteres gilt, dann existiert ein n+1, dessen Entwicklung entweder divergiert oder einen weiteren Zyklus generiert.
    Gruß
    Tom

    Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago.

  2. #12
    Registriert seit
    28.10.2006
    Beiträge
    348

    Standard

    Mich würde ja einmal interessieren, ob es eine näherungsweise Methode gibt, das vorwärts zu generieren... darüber denke ich schon länger nach.

    D.h. gegeben sind 1 als Startpunkt und die Startzahl n element N. Lässt sich für jede Verzweigung, die sich rückwärts aus n ... -> 1 ergibt, der wahrscheinliche Weg generieren? Wenn ja, sollte das ein Beweis für Collatz sein.

    Sehr interessant jedenfalls, auch für mich als Laien in der Materie.

    Grüsse,
    Frank

    PS: Alles Gute im neuen Jahr an Alle!

  3. #13
    Registriert seit
    05.07.2011
    Beiträge
    1.394

    Standard

    Zitat Zitat von Frankie Beitrag anzeigen
    Mich würde ja einmal interessieren, ob es eine näherungsweise Methode gibt, das vorwärts zu generieren... darüber denke ich schon länger nach.D.h. gegeben sind 1 als Startpunkt und die Startzahl n element N. Lässt sich für jede Verzweigung, die sich rückwärts aus n ... -> 1 ergibt, der wahrscheinliche Weg generieren? Wenn ja, sollte das ein Beweis für Collatz sein.
    Wie ich oben gezeigt habe, kann der Graph nicht nur näherungsweise sondern exakt konstruiert werden, vorwärts und rückwärts. Für einen Startpunkt n ist jedoch keine Abkürzung zur Iteration k bekannt. D.h. man muss für jedes n alle (potentiell unendlich viele) Schritte gemäß Ck(n) oder Tk(n) durchspielen. Auch die rekursive Konstruktion mittels C* oder T* ausgehend von 1 beweist nicht, dass dabei jede natürliche Zahl n auch erreicht wird. Es könnten Zahlen nicht erreicht werden, d.h. der Graph würde in nicht-zusammenhängende (und damit nicht-erreichbare) Sub-Graphen zerfallen, die entweder divergente Teile oder weitere Schleifen enthalten könnten. D.h. obwohl alle Schritte exakt bekannt sind, hilft das beim Beweis nicht.
    Geändert von TomS (05.01.2017 um 14:53 Uhr) Grund: Ergänzungen
    Gruß
    Tom

    Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago.

  4. #14
    Registriert seit
    08.04.2013
    Beiträge
    3.535

    Standard

    Hallo Tom,

    lässt sich so ein Graph auch irgendwie plotten oder ist eine Visualisierung sinnlos? Vielleicht theoretisch gar eine Animation, wie er sich entwickelt?

    Gruß,
    Dgoe

  5. #15
    Registriert seit
    20.01.2007
    Beiträge
    399

    Standard

    nur so als Einfall:

    kann man nicht versuchen, größere Zyklen zu konstruieren oder Bedingungen zu formulieren, die größere Zyklen erfüllen müssen, falls es sie gibt?

  6. #16
    Registriert seit
    22.02.2006
    Ort
    Hamburg
    Beiträge
    1.217

    Standard

    Hi Dgoe,
    Zitat Zitat von Dgoe Beitrag anzeigen
    lässt sich so ein Graph auch irgendwie plotten
    In Post #5 hat Tom bereits zwei Links genannt:
    Zitat Zitat von TomS Beitrag anzeigen
    Hier eine paar schöne Darstellung des Collatz-Graphen

    https://www.jasondavies.com/collatz-graph/
    http://swimmingthestyx.com/?p=44
    Gruß,
    Christian

    Meine Astro-Page: www.Jeffer.de

  7. #17
    Registriert seit
    08.04.2013
    Beiträge
    3.535

    Standard

    Boah!

    Fazinierend. Echt.

    Danke Christian.

  8. #18
    Registriert seit
    20.11.2014
    Beiträge
    225

    Standard

    nun so einfach ist es wohl nicht. Das Problem ist noch immer ungelöst und mithilfe von Computer sind sicherlich schon die ersten zig-Milliarden Zahlen berechnet worden. Nie ist man auf irgendwas anderes gekommen als die 4->2->1 Schleife.

    Das es auch anders sein könnte, sieht man, wenn man negative Zahlen nimmt. Wenn man mit einer negativen Zahl startet bleibt man im negativen Bereich. Man kann es sich dann auch leichter machen und alles mit -1 multiplizieren; dann ist man wieder im positiven. Allerdings ändert sich dann die Regel für ungerade Zahlen. Sie lautet dann:
    n->3n-1 Nun hat man auf einmal drei verschiedene Zyklen, die immer wieder vor kommen, und zwar: 1->2->1..., 5->14->7->20->10->5... und 17->50->25->74->37->110->55->164->82->41->122->61->182->91->272->136->68->34->17...

    Daran sieht man aber auch, dass auch bei großen Zahlen plötzlich andere Zyklen auftauchen können. Wer gerne mit grossen Zahlen rechnet, kann ja mal die normale Collatzfolge mit 27 beginnen. :-)

    Mit freundlichen Grüssen
    pane

  9. #19
    Registriert seit
    05.07.2011
    Beiträge
    1.394

    Standard

    Zitat Zitat von Dgoe Beitrag anzeigen
    ... lässt sich so ein Graph auch irgendwie plotten oder ist eine Visualisierung sinnlos? Vielleicht theoretisch gar eine Animation, wie er sich entwickelt?
    Das von mir verwendete Programm habe ich oben genannt. Es malt (noch) keine so schönen Bilder, aber es ist Freeware, unterstützt ein extrem simples Importformat und war in kürzester Zeit produktiv benutzbar; letzteres war mein Hauptkriterium.
    Gruß
    Tom

    Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago.

  10. #20
    Registriert seit
    05.07.2011
    Beiträge
    1.394

    Standard

    Anzeige
    Zitat Zitat von pane Beitrag anzeigen
    nun so einfach ist es wohl nicht. Das Problem ist noch immer ungelöst und mithilfe von Computer sind sicherlich schon die ersten zig-Milliarden Zahlen berechnet worden. Nie ist man auf irgendwas anderes gekommen als die 4->2->1 Schleife.
    So meinte ich das auch nicht.

    Konkret: Gegeben ist eine Abbildung C(n) oder T(n); damit kann das Problem lokal vollständig untersucht werden. Auch mittels der "Inversen" C* bzw. T* kann der Graph lokal vollständog generiert werden; Aber i) immer nur ohne Abkürzung, und ii) immer nur lokal.

    i) bedeutet, dass keine effizientere Berechnung für Tk(n) bekannt ist als Tk(n) selbst.

    ii) bedeutet, dass der Graph evtl. nicht zusammenhängend ist und dass dann T* nicht den gesamten Graphen generiert. Der Graph könnte prinzipiell in unendlich viele nicht-zusammenhängende Teilgraphen zerfallen, d.h. man müsste die Rekursion evtl. von unendlich vielen Startwerten aus beginnen, die man jedoch nicht kennen kann.

    Ich habe übrigens einen Hinweis gefunden, dass eine Verallgemeinerung des Collatz-Problems tatsächlich nicht entscheidbar ist; allerdings ist diese Verallgemeinerung nicht auf das Collatz-Problems selbst anwendbar.

    John H. Conway konnte zeigen, dass es eine verallgemeinerte Collatz-Folge gibt, in der n/2 und (3n+1)/2 durch n/k und (3n+1)/k ersetzt wird, die sich auf den Algorithmus einer Turing-Maschine abbilden lässt, was die mathematische Identität der beiden Probleme bedeutet. Nun weiß man, dass die Frage, ob es zu einem Ende des Algorithmus kommt (Halteproblem) nicht generell entscheidbar ist. Es könnte also sein, dass nicht nur die Lösung dieser verallgemeinerten Collatz-Folge unentscheidbar ist, sondern auch die einfachere Collatz-Vermutung. Damit hätte man ein besonders einfaches Beispiel eines unentscheidbaren Problems
    .

    Mehr als diesen Hinweis kenne ich jedoch nicht; weiß jemand mehr?
    Geändert von TomS (06.01.2017 um 00:53 Uhr)
    Gruß
    Tom

    Niels Bohr brainwashed a whole generation of theorists into thinking that the job (interpreting quantum theory) was done 50 years ago.

Ähnliche Themen

  1. Fermatsche Vermutung
    Von krzyzape im Forum Dunkle Materie & Dunkle Energie
    Antworten: 58
    Letzter Beitrag: 03.01.2010, 23:06

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •  
astronews.com 
Nachrichten Forschung | Raumfahrt | Sonnensystem | Teleskope | Amateurastronomie
Übersicht | Alle Schlagzeilen des Monats | Missionen | Archiv
Weitere Angebote Frag astronews.com | Forum | Bild des Tages | Newsletter
Kalender Sternenhimmel | Startrampe | Fernsehsendungen | Veranstaltungen
Nachschlagen AstroGlossar | AstroLinks
Info RSS-Feeds | Soziale Netzwerke | Flattr & freiwilliges Bezahlen | Werbung | Kontakt | Suche
Impressum | Nutzungsbedingungen | Datenschutzerklärung
Copyright Stefan Deiters und/oder Lieferanten 1999-2013. Alle Rechte vorbehalten.  W3C