Anzeige
Seite 1 von 3 123 LetzteLetzte
Ergebnis 1 bis 10 von 21

Thema: Collatz Vermutung - Teillösung

  1. #1
    Registriert seit
    07.08.2009
    Ort
    Neubrandenburg, Deutschland
    Beiträge
    2.172

    Standard Collatz Vermutung - Teillösung

    Anzeige
    Hallo,

    Zitat Zitat von Wikipedia
    Bei dem Problem geht es um Zahlenfolgen, die nach einem einfachen Bildungsgesetz konstruiert werden:

    Beginne mit irgendeiner natürlichen Zahl n > 0.
    Ist n gerade, so nimm als nächstes n/2.
    Ist n ungerade, so nimm als nächstes 3n + 1.
    Wiederhole die Vorgehensweise mit der erhaltenen Zahl.
    Die Vermutung ist, dass alle Zahlen am Ende auf die 1 hinauslaufen.

    Komischerweise sehe ich im Wikipediaartikel keinen Hinweis auf eine offensichtliche Teillösung:
    Folgende unendliche Reihen bestätigen die Vermutung:
    \[ \sum_{x=0}^\infty x \in \N 2^x] laufen alle gegen 1 weil die Zahl aussschließlich aus Zweierfaktoren aufgebaut ist und immer nur /2 gerechnet wird wie 16->8->4->2->1
    \[ \sum_{x=0}^\infty x \in \N 3*2^x] bestehen nur aus 2er Faktoren und einem 3er Faktor. 3 und von da ->10->5->16->8->4->2->1
    daraus folgt \[ \sum_{x=0}^\infty x \in \N y*2^x] für alle y die die vermutung bestätigen

    Rechnet man rückwärts, kann man von allen diesen Reihen sich die raussuchen die durch 3 teilbar sind (unendlich viele) +1 rechnen.

    Ich geh mal davon aus, das man das so ähnlich in einschlägiger Literatur finden wird?

    mfg
    Geändert von Kibo (31.12.2016 um 20:22 Uhr)
    101010

  2. #2
    Registriert seit
    05.07.2011
    Beiträge
    1.398

    Standard

    Du meinst sicher nicht

    $$ \sum_{x=0}^\infty x \in \mathbb{N} 2^x $$

    $$ \sum_{x=0}^\infty x \in \mathbb{N} 3*2^x $$

    Was soll das sein? Wozu die Summe?

    Du meinst schlichtweg die Zahlen

    $$a_n = 2^n,\;n \in \mathbb{N}$$

    $$b_n = 3 \cdot 2^n,\;n \in \mathbb{N}$$

    Ja, dafür landest du direkt bei

    $$2^n \to 2^{n-1} \to\ldots\to 2 \to 1$$

    $$3 \cdot 2^n \to 3 \cdot 2^{n-1} \to\ldots\to 6 \to 3 \to \ldots$$

    Die Vemutung besagt jedoch, dass dies für beliebige Zahlen gilt. Dies für spezielle Zahlen zu zeigen hilft also erst mal nicht weiter.
    Gruß
    Tom

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

  3. #3
    Registriert seit
    15.10.2008
    Ort
    Nürnberg
    Beiträge
    410

    Standard

    Mit "Geogebra" lässt es sich so einrichten.

    n=111 (ihr könnt auch eine andere Zahl wählen). Dann erzeugt ihr eine Schaltfläche. Ich nenne sie "nächste Aktion".

    In deren Skriptingteil (bei Mausklick) gebt ihr ein:

    Wenn[Mod[n, 2]==0, SetzeWert[n, n/2], SetzeWert[n, 3n+1]]

    Wenn ihr jetzt "ewig" auf der Schaltfläche rum klickt, ohne auf die 1 zu kommen, dann habt ihr die Vermutung widerlegt. Da müsst ihr aber aufpassen, dass ihr keine Zweierpotenz erwischt, sonst habt ihr verloren.

  4. #4
    Registriert seit
    07.08.2009
    Ort
    Neubrandenburg, Deutschland
    Beiträge
    2.172

    Standard

    Hallo Tom, ebenfalls hallo Julian,

    du hast Recht, dass ich keine Summe meine.
    Ich meine im ersten Absatz die Menge alle Zweipotenzen, wie Julian wohl auch vermutet hat: 2^1, 2^2, 2^3....2^∞ sind alles Zahlen die definitv bei 1 landen.

    Alle Produke mit 3 und diesen Zahlen landen ebenfalls bei 1.

    Alle Produkte aus einer Zahl die bei 1 landet und einer der eben genannten Zahlen landet ebenfalls bei 1.

    Ich bitte die falsche Notation zu Entschuldigen, ich finde leider kaum noch Zeit zum Posten, das geht nur noch "zwischen durch".

    mfg
    101010

  5. #5
    Registriert seit
    05.07.2011
    Beiträge
    1.398

    Standard

    Ich habe mich mal ein bisschen umgesehen.

    Statt der Abbildung

    $$ C : n \to C(n) = \left\{ \begin{array}[lcl] nn/2 & : & n = 0 \, \text{mod} \, 2 \\ 3n+1 & : & n = 1 \, \text{mod} \, 2 \end{array} \right. $$

    betrachtet man evtl. besser

    $$ T : n \to T(n) = \left\{ \begin{array}[lcl] nn/2 & : & n = 0 \, \text{mod} \, 2 \\ (3n+1)/2 & : & n = 1 \, \text{mod} \, 2 \end{array} \right. $$

    da hier die sicher mögliche zweite Iteration für die gerade Zahl 3n+1 bereits eingebaut ist.

    Es gilt ja: wenn n ungerade, dann wird 3n+1 berechnet; dieses ist jedoch sicher gerade, da für ungerades n=2k+1 gilt und damit 3n+1 = 3(2k+1)+1 = 6k+2 gerade.


    Hier eine paar schöne Darstellung des Collatz-Graphen

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


    Die Vermutung kann wie folgt äquivalent formuliert werden:
    1) Für jede positive Zahl n endet die durch C (bzw. T) definierte Folge nach endlich vielen Schritten bei 1
    2) Es existiert kein weiterer Loop neben 4,2,1,4,...
    3) Der Collatz-Graph ist zusammenhängend
    4) Generiert man den zusammenhängenden Teil des Collatz-Graphen ausgehend von 1, so überdeckt dieser die natürlichen Zahlen


    Der Collatz-Graph kann mittels der Äquivalenzrelation

    $$ a \sim b \, \Leftrightarrow\, \exists z \in \mathbb{Z}: b = 2^z a$$

    komprimiert werden. Zwei Zahlen a,b seien äquivalent, d.h. a ~ b, wenn eine ganze Zahl z existiert, so dass die o.g. Gleichung für a,b erfüllt ist.

    Da jede beliebige natürliche Zahl n mittels einer ungeraden Zahl p und einem Exponenten k = 0,1,2,... geschrieben werden kann als

    $$n = 2^k p, \, p = 1 \, \text{mod} \, 2$$

    kann man - ohne Information zu verlieren - einen "reduzierten" Collatz-Graphen konstruieren, indem man im originalen im Graphen alle Zahlen der Äquivalenzklasse [p] zu p

    $$[p] = \{p,2p,2^2p,2^3p,\ldots\}$$

    durch p ersetzen, d.h. alle geraden Zahlen sowie die trivialen Kanten

    $$ 2^kp \to 2^{k-1}p \to\ldots\to 2p \to p$$

    eliminiert. Der so reduzierte Graph ist definiert über den Äquivalenzklassen [p], repräsentiert durch die ungeraden Zahlen p.
    Geändert von TomS (02.01.2017 um 08:40 Uhr)
    Gruß
    Tom

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

  6. #6
    Registriert seit
    05.07.2011
    Beiträge
    1.398

    Standard

    Ich habe jetzt mal begonnen, den Collatzgraphen zu generieren.


    Zunächst ein Versuch, dies für alle n unterhalb einer gewissen Schranke N durchzuführen, d.h. C(n) zu iterieren. Das Ergebnis sieht sehr ungleichmäßig aus, da der Graph sozusagen Lücken aufweist. Die Elemente werden nämlich nicht alle bis zu einer gewissen Größe Z(N) generiert, sondern es werden i) alle Elemente bis einschließlich N ii) sowie teilweise größere mittels C(n) generiert; oberhalb von N sind also nur einige Elemente vertreten.


    Dann ein Versuch, reduzierte Graphen zu erzeugen; dazu definieren ich eine Funktion F(n) wie folgt:

    $$ F : n \to F(n) = \left\{ \begin{array}[lcl] x \frac{n}{2^{\nu(n)}} & : & n = 0 \, (\text{mod} \, 2) \\ \frac{(3n+1)}{2^{\nu(3n+1)}} & : & n = 1 \, (\text{mod} \, 2) \end{array} \right. $$

    Die Funktion nu zählt dabei wie häufig der Primfaktor 2 in n vorkommt, d.h. liefert für die o.g. Darstellung von mittels k, p genau k zurück:

    $$ \nu(2^k\,p) = k$$

    $$ n / 2^{\nu(n)} = p$$

    Damit erhalte den über die Äquivalenzklassen [p] und repräsentiert durch die ungeraden Zahlen p definierten reduzierten Graphen.


    Das C++ Programm ist noch sehr überschaubar; kann ich gerne zur Verfügung stellen. Die Graphik erzeuge ich mittels des Programms yEd; das C++ Programm liefert eine Ausageb im *.tgf Format.


    Den gesamten Collatzgraphen erhält man m.E. jedoch besser umgekehrt mittels Rekursion, d.h. anstatt dass man den Nachfolger mittels C(n) o.ä. sucht, konstruiert man rekursiv die jeweils möglichen Vorgänger:

    $$ C^\ast : n \to \left\{ \begin{array}[lcl] x \{2n\} & : & n = 0,1,2,3,5 \, (\text{mod} \, 6) \\ \{2n, (n-1)/3\} & : & n = 4 \, (\text{mod} \, 6) \end{array} \right. $$

    $$ T^\ast : n \to \left\{ \begin{array}[lcl] x \{2n\} & : & n = 0,1 \, (\text{mod} \, 3) \\ \{2n, (n-1)/3\} & : & n = 2 \, (\text{mod} \, 3) \end{array} \right. $$
    Geändert von TomS (04.01.2017 um 21:05 Uhr)
    Gruß
    Tom

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

  7. #7
    Registriert seit
    05.07.2011
    Beiträge
    1.398

    Standard

    Ich habe jetzt mal begonnen, den Collatzgraphen zu generieren.


    Zunächst ein Versuch, dies für alle n unterhalb einer gewissen Schranke N durchzuführen, d.h. C(n) zu iterieren. Das Ergebnis sieht sehr ungleichmäßig aus, da der Graph sozusagen Lücken aufweist. Die Elemente werden nämlich nicht alle bis zu einer gewissen Größe Z(N) generiert, sondern es werden i) alle Elemente bis einschließlich N ii) sowie teilweise größere mittels C(n) generiert; oberhalb von N sind also nur einige Elemente vertreten.


    Dann ein Versuch, reduzierte Graphen zu erzeugen; dazu definieren ich eine Funktion F(n) wie folgt:

    $$ F : n \to F(n) = \left\{ \begin{array}[lcl] x \frac{n}{2^{\nu(n)}} & : & n = 0 \, (\text{mod} \, 2) \\ \frac{(3n+1)}{2^{\nu(3n+1)}} & : & n = 1 \, (\text{mod} \, 2) \end{array} \right. $$

    Die Funktion nu zählt dabei wie häufig der Primfaktor 2 in n vorkommt, d.h. liefert für die o.g. Darstellung von mittels k, p genau k zurück:

    $$ \nu(2^k\,p) = k$$

    $$ n / 2^{\nu(n)} = p$$

    Damit erhalte den über die Äquivalenzklassen [p] und repräsentiert durch die ungeraden Zahlen p definierten reduzierten Graphen.


    Das C++ Programm ist noch sehr überschaubar; kann ich gerne zur Verfügung stellen. Die Graphik erzeuge ich mittels des Programms yEd; das C++ Programm liefert eine Ausageb im *.tgf Format.


    Den gesamten Collatzgraphen erhält man m.E. jedoch besser umgekehrt mittels Rekursion, d.h. anstatt dass man den Nachfolger mittels C(n) o.ä. sucht, konstruiert man rekursiv die jeweils möglichen Vorgänger:

    $$ C^\ast : n \to \left\{ \begin{array}[lcl] x \{2n\} & : & n = 0,1,2,3,5 \, (\text{mod} \, 6) \\ \{2n, (n-1)/3\} & : & n = 4 \, (\text{mod} \, 6) \end{array} \right. $$

    $$ T^\ast : n \to \left\{ \begin{array}[lcl] x \{2n\} & : & n = 0,1 \, (\text{mod} \, 3) \\ \{2n, (n-1)/3\} & : & n = 2 \, (\text{mod} \, 3) \end{array} \right. $$
    Gruß
    Tom

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

  8. #8
    Registriert seit
    05.07.2011
    Beiträge
    1.398

    Standard

    Mit der Relation F* zur rekursiven Generierung des reduzierten Graphen habe ich Probleme. Zunächst mal enthält der reduzierte Graph keine geraden Zahlen, d.h. man kann zwar F(n) für beliebige n definieren, muss diese jedoch im Graphen explizit ausschließen. Die erste Zeile entfällt demnach, es wird nie ein F*(n) = 2n oder 2k n gebildet, bzw. diese müssen übersprungen werden. Die zweite Relation würde ich dann wie folgt formulieren:

    $$ F^\ast : n \to \{ (2^k\,n-1)/3\, : n = 0 \, (\text{mod} \,2 ) \,\wedge\, k = \nu(3n+1)\} $$

    Ist das sinnvoll? Kann man das vereinfachen?
    Gruß
    Tom

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

  9. #9
    Registriert seit
    05.07.2011
    Beiträge
    1.398

    Standard

    Zitat Zitat von TomS Beitrag anzeigen
    $$ F^\ast : n \to \{ (2^k\,n-1)/3\, : n = 0 \, (\text{mod} \,2 ) \,\wedge\, k = \nu(3n+1)\} $$

    Ist das sinnvoll? Kann man das vereinfachen?
    Ich denke, ja:

    $$ F^\ast : n \to \{ (2^k\,n-1)/3\, : n = 0 \, (\text{mod} \,2 ) \} $$

    ist ausreichend.

    Ich habe jetzt das Programm für die rekursive Erzeugung des Graphen mittels F* fertig. Soweit ich das überprüfen konnte, sieht es vernünftig aus. Der mittels F bzw. F* definierte Graph ist eine "Vergröberung" des mittels C bzw. C* definierten Graphen. Konkret: wenn dieser einen Subgraphen

    $$ G_C = \cdots \longrightarrow \! \bigcirc \! \longrightarrow \! \bullet \! \longrightarrow \cdots \longrightarrow \! \bullet \! \longrightarrow \! \bigcirc \! \longrightarrow \cdots $$

    enthält, in dem kleine ausgefüllte Punkte für gerade Zahlen und große Kreise für ungerade Zahlen stehen, dann lautet der Subgraph in der Vergröberung

    $$ G_F = \cdots \longrightarrow \! \bigcirc \! \longrightarrow \! \bigcirc \! \longrightarrow \cdots $$

    Ich kann das (noch) nicht wasserdicht beweisen, aber ich sehe das allen meinen Überlegungen und Ergebnissen des Programmes an. Wenn überhaupt, dann existieren noch kleinere Fehler, aber das Prinzip ist klar.

    Damit ist es möglich, die Collatz-Vermutung wie folgt äquivalent umzuformulieren:
    3') Der auf den ungeraden natürlichen Zahlen vergröberte Collatz-Graph G ist zusammenhängend
    4') Generiert man den zusammenhängenden Teil des vergröberten Collatz-Graphen ausgehend von 1, so überdeckt dieser die ungeraden natürlichen Zahlen

    Die geraden Zahlen sind zumindest für die Darstellung obsolet (nicht jedoch für die Berechnung, denn sie treten wie in der obigen Formel auch bei der Definition des vergröberten Graphen auf)
    Gruß
    Tom

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

  10. #10
    Registriert seit
    08.09.2007
    Ort
    Varusschlacht
    Beiträge
    1.246

    Standard

    Anzeige
    Hallo Tom,

    ich habe mich vor einigen Jahren auch mal spielerisch mit Collatz beschäftigt. Meiner Meinung nach müsste ein Beweis wie folgt aussehen:

    Bis zu einer Zahl n (gerade) ist die Vermutung experimentell bewiesen.

    Gibt es eine Zahl n+1 (ungerade), die in ihrer 'Entwicklung' keine Zahl kleiner als n enthält?

    Ich bin 'leider' nur Physiker, nicht Mathematiker, daher würde ich auch sehr gerne auch mal Ralf dazu hören wollen.
    Raum IST, Zeit IST.

Ä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