Die Mathe-Redaktion - 28.03.2017 12:02 - Registrieren/Login
Auswahl
Schwarzes Brett
Fragensteller hat Anwort gelesen, aber bisher nicht weiter reagiert2017-03-27 21:53 bb
MPCT 2017 Planung
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Feb. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 421 Gäste und 24 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Über die maximale Länge von Collatz-Folgen
Freigegeben von matroid am So. 19. Juni 2016 22:22:19
Verfasst von Marbin -   667 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

<math>$${\Large \textbf{Über die maximale Länge von Collatz-Folgen}}</math>

Um überhaupt eine Aussage über die Länge von Collatz-Folgen treffen zu können, benötigen wir zunächst eine äquivalente Aussage der Collatz-Vermutung. Bei der Collatz-Vermutung geht es um eine Familie von Zahlenfolgen <math>C_{a_{0}}</math> jeweils mit Startglied <math>a_{0}</math>, und die Nachfolger werden nach folgender Vorschrift gebildet:

<math>
(1.1)~~~
\large
a_{i+1}=\gamma \left(a_{i} \right):=
\begin{cases}
3\cdot a_{i}+1, & \textup{falls }a_{i}\textup{ ungerade} \\
\frac{a_{i}}{2}, &\textup{falls }a_{i}\textup{ gerade}
\end{cases}
</math>

Wird eines der Folgeglieder <math>a_{i}</math> nun 1, so wird die Folge abgebrochen. Schauen wir uns als Beispiel zuerst die Folge <math>C_{3}</math> an, sie lautet

3, 10, 5, 16, 8, 4, 2, 1

und terminiert somit nach sieben Schritten (sprich <math>\gamma ^{7}(3)=1</math>). Die Collatz-Vermutung ist nun die einfache Aussage, dass alle Folgen <math>C_{a_{0}}</math> endlich sind, dass also für beliebige Startwerte die iterierte Anwendung irgendwann 1 liefert. Dies eine ungelöste Frage, im Folgenden wird also keine Lösung präsentiert, aber einige Betrachtungen zu der Problematik.

Zuerst stellen wir fest, dass sich die Frage für gerade Startwerte <math>C_{2\cdot k}</math> auf die für ungerade Startwerte zurückführen lässt (es werden am Anfang erst einmal alle Faktoren 2 herausgeteilt). Daher werden wir nur noch ungerade Startwerte betrachten. Wir nennen die ungeraden Startwerte <math>N</math>.
Eine Möglichkeit, sich den Folgen zu nähern, ist es, die vorkommenden Operationen zu betrachten. Jeder Folge lässt sich eine Zeichenkette aus <math>v</math> für verdreifachen (+1) und <math>h</math> für halbieren zuordnen, je nachdem, welche Operationen gemacht werden. Für <math>C_{3}</math> wäre die entsprechende Zeichenkette <math>vhvhhhh</math> und für <math>C_{7}</math> wäre es <math>vhvhvhhvhhhvhhhh</math>. Die Länge der Zeichenkette gibt also die Länge der Folge minus Eins an. Eine Beobachtung ist nun, dass auf jedes <math>v</math> sofort ein <math>h</math> folgt. Dies ist der Fall, da nur dann verdreifacht wird, wenn <math>a_{i}</math> ungerade ist und dann <math>3\cdot a_{i}+1</math> als Summe zweier ungerader Zahlen stets gerade ist. Somit können wir zu einer Folge <math>C_{N}</math> eine weitere Folge <math>x_{1},x_{2},...</math> assoziieren, wobei <math>x_{i}</math> jeweils die maximale Anzahl der unmittelbar aufeinander folgenden Zeichen <math>h</math> angeben. Für <math>C_{3}</math> wären dies <math>x_{1}=1,~x_{2}=4</math> und dann ist die Folge auch schon vorbei. Die Anzahl der Zeichen <math>v</math> ist somit für ungerade Startwerte gleich der Anzahl der vorkommenden <math>x_{i}</math>, wir bezeichnen sie im Folgenden mit <math>y</math>. Bei <math>C_{3}</math> ist also <math>y=2</math>.
Für jede terminierende Folge können wir uns nun mithilfe von <math>x_{1},x_{2},...,x_{y}</math> den Startwert zurückrechnen, indem wir die Operationen umdrehen. Wir starten mit einer 1, multiplizieren sie mit <math>2^{x_{y}}</math>; subtrahieren 1 und dividieren durch 3; multiplizieren mit <math>2^{x_{y-1}}</math>; subtrahieren 1 und dividieren durch 3; usw., bis wir mit <math>2^{x_{1}}</math> multiplizieren und noch ein letztes Mal 1 subtrahieren und durch 3 dividieren. Wir setzen nun <math>x=x_{1}+x_{2}+...+x_{y}</math> und erhalten:

<math>
(1.2)~~~
N=\cfrac{2^{x_{1}}\cdot \cfrac{2^{x_{2}}...\cdot \cfrac{2^{x_{y-1}}\cdot \cfrac{2^{x_{y}}-1}{3}-1}{3}-1}{3}-1}{3}
</math>

<math>
=\cfrac{2^{x_{1}}\cdot \left (2^{x_{2}}\cdot\cfrac{2^{x_{3}}...\cdot \cfrac{2^{x_{y-1}}\cdot \cfrac{2^{x_{y}}-1}{3}-1}{3}-1}{3}-1-\cfrac{3}{2^{x_{1}}}\right)}{3^{2}}
</math>

<math>
=\cfrac{2^{x_{1}+x_{2}}\cdot \left (2^{x_{3}}\cdot\cfrac{2^{x_{4}}...\cdot \cfrac{2^{x_{y-1}}\cdot \cfrac{2^{x_{y}}-1}{3}-1}{3}-1}{3}-1-\cfrac{3}{2^{x_{1}}}-\cfrac{3^{2}}{2^{x_{1}+x_{2}}}\right)}{3^{3}}
</math>

<math>
=\cfrac{2^{x_{1}+x_{2}+...+x_{y-1}+x_{y}}\cdot \left (1-\left ( \cfrac{3^{0}}{2^{x_{y}}}+\cfrac{3^{1}}{2^{x_{y-1}+x_{y}}}+...+\cfrac{3^{y-1}}{2^{x_{1}+x_{2}+...+x_{y-1}+x_{y}}} \right ) \right )}{3^{y}}
</math>

<math>
=\cfrac{2^{x}\cdot \left ( 1-\sum_{i=0}^{y-1} \cfrac{3^{i}}{2^{\sum_{j=y-i}^{y}x_{j}}}\right )}{3^{y}}.
</math>

Die Collatz-Vermutung ist somit äquivalent zu der Aussage, dass es für jede ungerade Zahl <math>N</math> gewisse <math>x_{1},x_{2},...,x_{y}</math> und <math>x=\sum_{i=1}^{y}x_{i}</math> gibt, so dass

<math>
(1.3)~~~N=\cfrac{2^{x}\cdot \left ( 1-\sum_{i=0}^{y-1} \cfrac{3^{i}}{2^{\sum_{j=y-i}^{y}x_{j}}}\right )}{3^{y}}.
</math>

Aus (1.3) erhalten wir sofort die Ungleichungen

<math>(1.4)~~~N<\cfrac{2^{x}}{3^{y}}</math>

und

<math>(1.5)~~~\cfrac{y}{x}<\cfrac{\ln\left ( 2\right )}{\ln\left ( 3\right )}.</math>

Sei <math>c=\frac{y}{x}</math>, so erhalten wir aus (1.4) eine erste Abschätzung über die Länge von Collatz-Folgen:

<math>(1.6)~~~x+y>\cfrac{\ln\left(N\right)\cdot \left (c+1\right)}{\ln\left(2\right)-c\cdot \ln\left(3\right)}.</math>

Um <math>N</math> nach oben abzuschätzen, können wir <math>2^{x}\cdot \sum_{i=0}^{y-1} \cfrac{3^{i}}{2^{\sum_{j=y-i}^{y}x_{j}}}</math> nach unten abschätzen. Dazu setzen wir einfach alle <math>x_{i}=1</math> und erhalten

<math>(1.7)~~~2^{x}\cdot \sum_{i=0}^{y-1} \cfrac{3^{i}}{2^{\sum_{j=y-i}^{y}x_{j}}}\geq 2^{y-1}\cdot \sum_{i=0}^{y-1}\left (\cfrac{3}{2} \right)^{i}.</math>

Berechnung der Summe der geometrischen Reihe ergibt:

<math>(1.8)~~~2^{y-1}\cdot \sum_{i=0}^{y-1}\left (\cfrac{3}{2} \right)^{i}=3^{y}-2^{y}.</math>

Somit gilt <math>2^{x}\cdot \sum_{i=0}^{y-1} \cfrac{3^{i}}{2^{\sum_{j=y-i}^{y}x_{j}}}\geq 3^{y}-2^{y}</math>, und wir erhalten aus

<math>(1.9)~~~2^{x}\cdot \sum_{i=0}^{y-1} \cfrac{3^{i}}{2^{\sum_{j=y-i}^{y}x_{j}}}=2^{x}-3^{y}\cdot N</math>

die Ungleichung

<math>(1.10)~~~N\leq \cfrac{2^{x}+2^{y}}{3^{y}}-1.</math>
Nehmen wir nun an, es existiert eine asymptotische Schranke <math>a>1</math> und <math>a\in \mathbb{R}^{+}</math>, so dass für alle <math>N</math>

<math>(1.11)~~~y<N\cdot a</math>

und eine asymptotische Schranke <math>b<1</math> und <math>b\in \mathbb{R}^{+}</math>, so dass für alle <math>N</math>

<math>(1.12)~~~b<\cfrac{3^{y}\cdot N}{2^{x}},</math>

so erhalten wir

<math>(1.13)~~~x<\cfrac{N\cdot a\cdot \ln\left (3\right )+\ln\left (N\right )-\ln\left (b\right )}{\ln \left ( 2 \right )}.</math>

Interessant in diesem Hinblick ist die Grenzwertbetrachtung

<math>
(1.14)~~~\lim_{N \to\infty}  \cfrac{N\cdot a\cdot \ln \left ( 2 \right )}{N\cdot a\cdot \ln\left (3\right )+\ln\left (N\right )-\ln\left (b\right )}~~~\underset{=}{\textup{l'Hospital}}~~~\lim_{N \to\infty}  \cfrac{a\cdot \ln \left ( 2 \right )}{a\cdot \ln\left (3\right )+\cfrac{1}{N}}=\cfrac{\ln \left ( 2 \right )}{\ln \left ( 3 \right )}.
</math>

Die maximale Länge einer Collatz-Folge ist nun gegeben durch

<math>(1.15)~~~x+y<\cfrac{N\cdot a\cdot \ln\left (3\right )+\ln\left (N\right )-\ln\left (b\right )}{\ln \left ( 2 \right )}+N\cdot a</math>

oder vereinfacht

<math>(1.16)~~~x+y<\cfrac{\ln\left (\cfrac{N\cdot 6^{N\cdot a}}{b}  \right)}{\ln \left(2\right )}.</math>

Wir vermuten, dass <math>a=\frac{\ln\left(3\right)}{\ln\left(2\right)}</math> und <math>b=\frac{3}{4}</math>, jedoch sehen wir uns außerstande, dies heute und an dieser Stelle zu beweisen.


Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: automatisch eingefügt und unbearbeitet :
Über die maximale Länge von Collatz-Folgen [von Marbin]  
$${Large textbf{}} Um überhaupt eine Aussage über die Länge von Collatz-Folgen treffen zu können, benötigen wir zunächst eine äquivalente Aussage der Collatz-Vermutung. Bei der Collatz-Vermutung geht es um eine Familie von Zahlenfolgen C_{a_{0}} jeweils m
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 667
 
Aufrufstatistik des Artikels
Insgesamt 5 externe Besuche zwischen 2017.03 und 2017.03 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com360%60 %
http://m.facebook.com240%40 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 2 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2017.03.23-2017.03.26 (2x)https://www.google.de/

[Seitenanfang]

" Mathematik: Über die maximale Länge von Collatz-Folgen" | 0 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]