Mathematik: Über die maximale Länge von Collatz-Folgen
Released by matroid on So. 19. Juni 2016 22:22:19 [Statistics]
Written by Marbin - 883 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)
<math>$${\Large \textbf{ber die maximale Lnge 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.

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
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]

 
 
Aufrufzähler 883
 
Aufrufstatistik des Artikels
Insgesamt 44 externe Seitenaufrufe zwischen 2016.06 und 2021.04 [Anzeigen]
DomainAnzahlProz
https://google.de1329.5%29.5 %
https://duckduckgo.com511.4%11.4 %
https://www.ecosia.org12.3%2.3 %
https://google.com1943.2%43.2 %
https://google.ch24.5%4.5 %
http://m.facebook.com24.5%4.5 %
https://suche.web.de12.3%2.3 %
http://www.bing.com12.3%2.3 %

Häufige Aufrufer in früheren Monaten
Insgesamt 26 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2021 (19x)https://google.com/
202011-11 (7x)https://google.de/

[Top of page]

"Mathematik: Über die maximale Länge von Collatz-Folgen" | 1 Comment
The authors of the comments are responsible for the content.

Re: Über die maximale Länge von Collatz-Folgen
von: Wario am: So. 25. Oktober 2020 18:32:03
\(\begingroup\)
Ein Beispiel wäre schön. Angenommen N=25. Was ist dann die maximal zu erwartende Länge der Collatzfolge von N?\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]