Die Mathe-Redaktion [Home] - Neues auf einen Blick 08.06.2023 19:45 [Neues] [Forum] [Suche] - Registrieren/Login
 
Tools
GliederungspunktLatex-Bibliographie in HTML umwandeln
Mathematik: Collatzsieb
Released by matroid on Fr. 24. Juli 2020 20:45:42 [Statistics] [Comments]
Written by blindmessenger - 1243 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Collatzsieb

Einleitung

Es seien $X$ und $Y$ die Mengen $$X=\{24n+1:n\in\mathbb N\}\cup\{24n+17:n\in\mathbb N\}\cup\{48n+13:n\in\mathbb N\}\cup\{48n+29:n\in\mathbb N\}\cup\{96n+37:n\in\mathbb N\}\cup\{192n+181:n\in\mathbb N\}$$ $$Y=\{6n+1:n\in\mathbb N\}\cup\{6n+5:n\in\mathbb N\}$$ Aus der Menge $X$ entsteht durch Collatziteration die Menge $Y$. Aus der Menge $Y$ wiederum lässt sich die Menge $X$ heraussieben. So lässt sich ein Sieb für Collatzfolgen konstruieren. Im Folgenden wird gezeigt wie man dieses Sieb herleiten kann...

[Edit]
[To the bottom]

Definition

Durch folgende Funktion $f_c$ soll gezeigt werden wie aus bestimmten Restklassen $jn+k$ bestimmte andere Restklassen $f_c(jn+k)$ iteriert werden. \[ f_c(j\,n+k) = \frac{3\cdot(j\,n+k)+1}{2^i} \] Das bedeutet konkret, dass wir eine ungerade Zahl der Form $jn+k$ suchen die durch Multiplikation mit 3, Addition von 1 und Halbierungen zu einer anderen ungeraden Zahl der Form $f_c(jn+k)$ wird. Also genau die Collatzbildungsvorschrift von einer ungeraden Zahl zur nächsten.

Behauptung

$Y_2$ sei die Menge $$Y_2=\{18n+1:n\in\mathbb N\}\cup\{18n+5:n\in\mathbb N\}\cup\{18n+7:n\in\mathbb N\}\cup\{18n+11:n\in\mathbb N\}\cup\{18n+13:n\in\mathbb N\}\cup\{18n+17:n\in\mathbb N\}$$ Für bestimmte Kombinationen aus $i$, $j$ und $k$ besteht über die Funktion $f_c$ eine wohldefinierte Bijektion $f_c:X \to Y_2$:
\tikzstyle{block} = [ellipse, draw, text width=5em, text centered, rounded corners, minimum height=4em] \begin{center} \begin{tikzpicture}[node distance = 3.5cm, auto] \node [block] (init) {24n+1 \\ 24n+17 \\ 48n+13 \\ 48n+29 \\ 96n+37 \\ 192n+181}; \node [block, right of=init] (identify) {18n+1 \\ 18n+13 \\ 18n+5 \\ 18n+11 \\ 18n+7 \\ 18n+17}; \node[text width=5cm] at (2.4,2.2) {$X$}; \node[text width=5cm] at (5.8,2.2) {$Y_2$}; \draw[->] (0.8,1) -- (2.7,1); \draw[->] (0.8,0.6) -- (2.7,0.6); \draw[->] (0.8,0.2) -- (2.7,0.2); \draw[->] (0.8,-0.2) -- (2.7,-0.2); \draw[->] (0.8,-0.6) -- (2.7,-0.6); \draw[->] (0.8,-1) -- (2.7,-1); \end{tikzpicture} \end{center}

Beweis

Durch bestimmte Fallbetrachtungen lässt sich die wohldefinierte Bijektion $f_c:X \to Y_2$ direkt beweisen: $$\large {1. \ Fall:} $$ \[ f_c:(24\,n+1) \to (18\,n+1) \] $$i=2 \ \ \ \ j=24 \ \ \ \ k=1$$ \[ f_c(24\,n+1) = \frac{3\cdot(24\,n+1)+1}{2^2} = 18\,n+1 \] $$\large {2. \ Fall:} $$ \[ f_c:(24\,n+17) \to (18\,n+13) \] $$i = 2 \ \ \ \ j = 24 \ \ \ \ k = 17$$ \[ f_c(24\,n+17) = \frac{3\cdot(24\,n+17)+1}{2^2} = 18\,n+13 \] $$\large {3. \ Fall:}$$ \[ f_c:(48\,n+13) \to (18\,n+5) \] $$i = 3 \ \ \ \ j = 48 \ \ \ \ k = 13$$ \[ f_c(48\,n+13) = \frac{3\cdot(48\,n+13)+1}{2^3} = 18\,n+5 \] $$\large {4. \ Fall:} $$ \[ f_c:(48\,n+29) \to (18\,n+11) \] $$i = 3 \ \ \ \ j = 48 \ \ \ \ k = 29$$ \[ f_c(48\,n+29) = \frac{3\cdot(48\,n+29)+1}{2^3} = 18\,n+11 \] $$\large {5. \ Fall:}$$ \[ f_c:(96\,n+37) \to (18\,n+7) \] $$i = 4 \ \ \ \ j = 96 \ \ \ \ k = 37$$ \[ f_c(96\,n+37) = \frac{3\cdot(96\,n+37)+1}{2^4} = 18\,n+7 \] $$\large {6. \ Fall:}$$ \[ f_c:(192\,n+181) \to (18\,n+17) \] $$i = 5 \ \ \ \ j = 192 \ \ \ \ k = 181$$ \[ f_c(192\,n+181) = \frac{3\cdot(192\,n+181)+1}{2^5} = 18\,n+17 \]

Collatzsieb

Für die Behauptung gilt $$X\subset Y_2$$ Da ausserdem gilt
\tikzstyle{block} = [ellipse, draw, text width=5em, text centered, rounded corners, minimum height=4em] \begin{center} \begin{tikzpicture}[node distance = 3.5cm, auto] \node [block] (init) {18n+1 \\ 18n+5 \\ 18n+7 \\ 18n+11 \\ 18n+13 \\ 18n+17}; \node [block, right of=init] (identify) {6n+1 \\ 6n+5}; \node[text width=5cm] at (2.4,2.2) {$Y_2$}; \node[text width=5cm] at (5.8,2.2) {$Y$}; \node[text width=5cm] at (4.1,0) {$=$}; \node[text width=5cm] at (4.1,2.2) {$=$}; \end{tikzpicture} \end{center}
gilt also auch $$X\subset Y$$ Unter dieser Voraussetzung lässt sich eine Art Collatzsieb erzeugen wie folgt
\tikzset{ state/.style={circle,draw,minimum size=6ex}, arrow/.style={-latex, shorten >=1ex, shorten <=1ex},arrowlabel/.style={sloped, above}} \begin{document} \begin{tikzpicture}[node distance=5em] \node [state] (X) {$X$}; \node [state, right=of X] (Y) {$Y$}; \node[text width=5cm] at (3.4,-0.8) {sieben}; \node[text width=5cm] at (3.2,0.8) {iterieren}; \node[text width=5cm] at (3,1.8) {Collatzsieb}; \node[text width=5cm] at (1.5,-1.8) {$X$ \ wird\ über\ $f$\ zu\ $Y$\ iteriert.}; \node[text width=5cm] at (1.8,-2.8) {$X$\ lässt\ sich\ aus\ $Y$\ sieben.}; \draw [arrow, bend left] (X) to (Y); \draw [arrow, bend left] (Y) to (X); \end{tikzpicture}
Collatzsieb am Beispiel der Zahlen bis 61:
\tikzstyle{block} = [ellipse, draw, text width=5em, text centered, rounded corners, minimum height=4em] \begin{center} \begin{tikzpicture}[node distance = 3.5cm, auto] \node [block] (init) {1\\13\\ 17\\25 \\ 29\\37 \\ 41\\49 \\ 61 \\...}; \node [block, right of=init] (identify) {1\\5 \\ 13\\19 \\ 11\\7 \\ 31\\37 \\ 23\\... }; \node [block, right of=identify] (identify2) {1\\ - \\ 13\\ - \\ - \\ - \\ - \\37 \\ - \\... }; \node [block, right of=identify2] (identify3) { 1\\ - \\ 5\\ - \\ - \\ - \\ - \\7 \\ - \\...}; \node [block, right of=identify3] (identify4) { 1\\ - \\ - \\ - \\ - \\ - \\ - \\ - \\ - \\... }; \node[text width=5cm] at (3.6,2.2) {iterieren}; \node[text width=5cm] at (7.3,2.2) {sieben}; \node[text width=5cm] at (10.6,2.2) {iterieren}; \node[text width=5cm] at (14.3,2.2) {sieben}; \node[text width=5cm] at (2.4,3.3) {$X$}; \node[text width=5cm] at (5.9,3.3) {$Y$}; \node[text width=5cm] at (9.4,3.3) {$X$}; \node[text width=5cm] at (12.9,3.3) {$Y$}; \node[text width=5cm] at (16.4,3.3) {$X$}; \draw[->] (init) to (identify); \draw[->] (identify) to (identify2); \draw[->] (identify2) to (identify3); \draw[->] (identify3) to (identify4); \end{tikzpicture} \end{center}

Interpretation

Die Menge $Y$ sind die Zahlen die überhaupt durch eine Collatziteration entstehen können. Wenn es eine Menge $X$ gibt die auf diese Menge abbildet und gleichzeitig die Menge $X$ wieder Teilmenge von $Y$ ist dann lässt sich ein Sieb konstruieren. Für Collatz bedeutet das, dass nach jeder Iteration exakt die Zahlen $6n+1$ und $6n+5$ herausgesiebt werden können unabhängig davon wie oft iteriert wird und ohne dass eine Zahl der Menge fehlt. Welche Schlussfolgerungen kann man daraus ziehen? Vielleicht kann man zeigen, dass dieser Sachverhalt im Widerspruch steht zu einem nichttrivialen Zyklus steht oder man könnte behaupten, dass Collatz nicht beweisbar ist, da egal wie oft iteriert wird, immer wieder die Zahlen $6n+1$ und $6n+5$ (ohne Ausnahme) stehen bleiben.
[Edit]
\(\endgroup\)
[Show outline only]
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


Write a comment

Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]
 


 
 
Aufrufzähler 1243



[Top of page]



"Mathematik: Collatzsieb" | 5 Comments
The authors of the comments are responsible for the content.

Re: Collatzsieb
von: thureduehrsen am: Fr. 24. Juli 2020 21:23:54
\(\begingroup\)Hallo Jonas, schön, dass du an der Aufgabe noch drangeblieben bist. Für mich wächst das in mehr Arbeit aus, als ich im Moment leisten kann. Im Ansatz ist mir klar, was du hier machst, aber dem letzten Absatz "Interpretation" kann ich noch (!) nicht folgen. mfg thureduehrsen\(\endgroup\)
 

Re: Collatzsieb
von: blindmessenger am: Sa. 25. Juli 2020 09:42:21
\(\begingroup\)Hallo Thure, ja danke auch nochmal für Deine Hilfe hierbei... Die Interpretation soll erstmal nur zum Denken anregen... Nur eine Idee... Ob man da wirklich etwas gewinnen kann? Ich weiß es nicht... Gruß Jonas\(\endgroup\)
 

Re: Collatzsieb
von: juergenX am: Mo. 27. Juli 2020 23:25:01
\(\begingroup\)Super das Thema Collatz lässt dich wie auch mich und andere (?) nicht los. Warum ist es so, dass ein scheinbar so einfach erzeugter attractor aus 2 Anweisungen (hoffe das ist das richtige wort) verblüffende Resultate erzeugt. Es sind auch alle Primzahlen in der Art $6n \pm1$ darstellbar, aber nicht umgekehrt z.B. 25 cong 1 mod 6 aber nicht prim. Durch jeden Schritt z.B. 3 nach 5 oder 7 nach 11 nach 13 wird eine Folgenzahl anderer Primfaktorzerlegung erzeugt. Und es erscheint bestimmte Schluesselzahlen zu geben, die gehaeuft auftreten z.B. 9232 die zu eine baldigen Ende der Iteration führen. Ich suchte noch ander hohe Zahlen die eine geringen delay haben und suche noch andere Ideen dazu. Aber es ist sehr viel Programmieraufwand. Beste Gruesse, Juergen \(\endgroup\)
 

Re: Collatzsieb
von: blindmessenger am: Di. 28. Juli 2020 18:46:48
\(\begingroup\)Hallo Jürgen, ja... Im Collatz kann man sich verlieren... 😉 Immer am Ball bleiben oder auch nicht wie der Profi sagen würde... 😉 Gruß Jonas \(\endgroup\)
 

Re: Collatzsieb
von: xiao_shi_tou_ am: Di. 11. August 2020 11:04:32
\(\begingroup\)Hi. Da ich mich jetzt im Rahmen einer Vorlesung auch etwas mit dem Collatz Problem beschäftigt habe interessiert mich der Artikel. Ich verstehe ihn aber noch nicht. Falls ich meine Fragen nicht selbst klären kann melde ich mich nochmal. \(\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-2023 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]