Matroids Matheplanet Forum Index
Forumbereich moderiert von: Wauzi
Mathematik » Zahlentheorie » Collatz-Graph erstellen
Druckversion
Druckversion
Antworten
Antworten
Seite 1   [1 2]   2 Seiten
Kein bestimmter Bereich Collatz-Graph erstellen
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Themenstart: 2020-10-24






Es geht nochmal um den Collatz-Graph und seine graphische Umsetzung. Mir ist klar, wie man den Pfad zur Startzahl (25) programmiert.
Jetzt ist nur die Frage, warum sind hier die Nebenpfade für ausgrechnet 18, 15, 24, 21 eingetragen? Hat das irgendeinen Grund oder eine Systematik oder ist das Willkür?
An sich müsste es ja diverse Weitere Nebenpfade geben.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wally Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 02.11.2004, Mitteilungen: 8928, aus: Dortmund, Old Europe
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.1, eingetragen 2020-10-24

Ich rate mal:

man möchte alle Startwerte von 1 bis 25 erfaseen.

Viele Grüße

Wally



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.2, vom Themenstarter, eingetragen 2020-10-24

Ach so, ja ich denke es ist klar:

Man muss von jedem Element des Hauptpfades zu einer Startzahl zurückrechnen, die kleiner als die Startzahl des Hauptpfades ist. Gibt es so eine Nebenstartzahl ergibt sich ein Nebenpfad, sonst nicht.

[Die Antwort wurde vor Beitrag No.1 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.3, vom Themenstarter, eingetragen 2020-10-24

2020-10-24 21:22 - Wally in Beitrag No. 1 schreibt:
man möchte alle Startwerte von 1 bis 25 erfaseen.

Oder so, was wahrscheinlich einfacher sein dürfte.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.4, vom Themenstarter, eingetragen 2020-10-24

2020-10-24 21:22 - Wally in Beitrag No. 1 schreibt:
man möchte alle Startwerte von 1 bis 25 erfaseen.

Aha, man muss also den Graph von 1 bis 25 bzw. von rechts noch links aufbauen und alle möglichen Nebenpfade berücksichtigen, die zu einer Startzahl kleiner oder gleich 25 führen.
Ja, das sollte gehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.5, vom Themenstarter, eingetragen 2020-10-24

Ich überlege gerade, wie man das effizient macht:

Günstig könnte eine Rohdatentabelle sein, die, bei der Startzahl 25, 25 teilweise leere Zeilen hätte.

Wegen den Spalten wäre die Frage:
Über die Längen der auftretenden Nebenpfade 1,...,25 weiß man vermutlich nichts, ja?

Also z.B. die Startzahl 21 hat einen Pfad der Länge 7, aber ausrechnen kann man das nicht?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 11.09.2008, Mitteilungen: 6615, aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.6, eingetragen 2020-10-25

Ausrechnen kann man das schon, man muss ja nur von der 21 loslaufen und gemäß der Vorschrift weitere Glieder ausrechnen, bis man bei 1 ist.

Meiner Meinung nach ist es einfacher, nacheinander die Startzahlen 1, 2, 3, ..., 25 durchzuprobieren und solange zu rechnen, bis man zu einer kleineren Zahl kommt. Für diese kleiner Zahl kennt man dann schon den weiteren Verlauf.
[Man kann etwas Aufwand sparen, wenn man sich erreichte Zahlen merkt, die zwar größer als die Startzahl sind, aber moch in dem Bereich liegen, den man untersuchen möchte (hier: 1-25).]
Würde man stattdessen versuchen von rechts beginnend alle Weg zu finden, die bei einer Zahl kleinergleich 25 starten, dann müsste man erheblich mehr Pfade betrachten, z.B. ...-4096-2048-1024-512-256-128-64-32-16-8-4-2-1.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.7, vom Themenstarter, eingetragen 2020-10-25

Wenn man sich den Graph um -90° gedreht vorstellt, dann wäre das eine Tabelle mit 6 (oder 9?) Spalten (in leeren Zellen kann 0 stehen).

Kann man sagen, dass bei Collatz-Folgen die Pfadlänge der Startzahl (25) stets größer ist, als die Pfadlängen der kleineren Startzahlen (1,2,...,24)?



PS:
Ich bräuchte eine Bedigung für die Startzahlen der Nebenpfade, das müssten
sein:
25
18
24
15
10
40 <--- die 40 irritiert.
16
21
16





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.8, vom Themenstarter, eingetragen 2020-10-25

2020-10-25 01:14 - Kitaktus in Beitrag No. 6 schreibt:
Ausrechnen kann man das schon, man muss ja nur von der 21 loslaufen und gemäß der Vorschrift weitere Glieder ausrechnen, bis man bei 1 ist.

Ja, ich meinte das so:
Kann ich von einer Startzahl (etwa 25) ausrechnen wie lang der Collatz-Pfad sein wird, ohne die Collatzfolge (für 25) bestimmt zu haben?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 11.09.2008, Mitteilungen: 6615, aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.9, eingetragen 2020-10-25

2020-10-25 02:45 - Wario in Beitrag No. 7 schreibt:
Kann man sagen, dass bei Collatz-Folgen die Pfadlänge der Startzahl (25) stets größer ist, als die Pfadlängen der kleineren Startzahlen (1,2,...,24)?
Im allgemeinen gilt das offensichtlich nicht. Die Pfadlänge von der Startzahl 24 ist beispielsweise nicht größer als die von allen kleineren Startzahlen.

2020-10-25 14:20 - Wario in Beitrag No. 8 schreibt:
Kann ich von einer Startzahl (etwa 25) ausrechnen wie lang der Collatz-Pfad sein wird, ohne die Collatzfolge (für 25) bestimmt zu haben?
Mir ist kein Verfahren bekannt, um diese Pfadlänge wesentlich schneller zu berechnen als durch Bestimmung der Folge.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.10, vom Themenstarter, eingetragen 2020-10-26



a) Erinnerung: Ich möchte eine passende Tabelle erstellen, in der die Zahlen der Pfade an richtiger Position nach Zeile und Spalte stehen (und leere Zellen 0 erhalten).

b) Also ich bin ziemlich überzeugt, dass man den Graph von rechts nach links, d.h. mit 1 beginnend, aufbauen muss.
Das ist doch eindeutig ein Binärbaumdiagramm mit Wurzel 1.
Eine Tabelle a) wäre sonst eine ziemlich schwierige Sache. Man könnte die Collatzfolgen von 25,24,...,1 bestimmen, ok. Aber dann müsste man anfangen Nebenpfade zu bestimmen (also Nullen einbringen) und die Spalten passend ordnen. Das dürfte aufwendig werden.


c) Es braucht gescheite Abbruchbediungungen für die Nebenpfade und ja/nein-Bedingungen für die Existenz eines Nebenpfades.

Wie könnte man diese definieren?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.11, vom Themenstarter, eingetragen 2020-10-26

2020-10-26 17:20 - Wario in Beitrag No. 10 schreibt:
b) Also ich bin ziemlich überzeugt, dass man den Graph von rechts nach links, d.h. mit 1 beginnend, aufbauen muss.
...

c) Es braucht gescheite Abbruchbediungungen für die Nebenpfade und ja/nein-Bedingungen für die Existenz eines Nebenpfades.

Wie könnte man diese definieren?

Wahrscheinlich geht das nicht ganz trivial.
Nach dem
lautet die Umkehrfunktion der Collatzfolge:
$ R (n) = \begin {cases} \{2n \} & {\text {if}}~ n \equiv 0,1 \\[4px] \left \{2n, {\frac {2n- 1} {3}} \right \} & {\text {if}}~ n \equiv 2 \end {cases} {\pmod {3}}$

Wie könnte man eine Abbruchbedingung ergänzen?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
juergenX Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 08.07.2019, Mitteilungen: 305
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.12, eingetragen 2020-10-27

Die Frage nach der Länge der Collatzketten wird teils behandelt in



Das "Delay" ist die Länge der Kette.
Der "Glide" ist die Anzahl der Schritte, bis die Folge unter den Startwert fällt.

Das längste bekannte Delay ist demnach D(1,339302,163616,345727) mit der Länge 2330
Am kürzesten sind offensichtlich die reinen 2er Potenzen $c=2^n$, Delay(c)=n, Glide(c)=1.

Zum Glide record siehe

 



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.13, vom Themenstarter, eingetragen 2020-10-27

2020-10-27 15:09 - juergenX in Beitrag No. 12 schreibt:
Das längste bekannte Delay ist ...

Wahrscheinlich ist mein Problem weit trivialer.


(Ausschnitt)


Die Darstellung unten ist leicht anders.
Sie hat den Vorteil, dass man sich den Hauptpfad (für 25) als eine einzige Tabellenspalte denken kann (wenn man sich das Geschwobel unten ab 16 etwas anders denkt).
Die Nebenpfade sind dann Zusatzspalten, deren Zellen teilweise ungefüllt sind.  

Ich will das als Tabelle, weil mir dazu dann diverse weitere Auswertungsmöglichkeiten einfallen, sobald ich die Tabelle einmal habe.


Unter dem Link wird auch ein Pythoncode angegeben. Dieser ist aber m.E. auch geschwobelt, weil er vermutlich einfach dieses eine Bild erzeugen möchte. Ich will etwas erstellen, wo man nur eine beliebige Startzahl N (z.B. 25, 27, 5, ...) eingibt und es den korrekten Collatzgraph mit allen Nebenpfaden für 1,2,...,N ausgibt, d.h. ohne manuelle Detailkorrekturen etc.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
juergenX Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 08.07.2019, Mitteilungen: 305
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.14, eingetragen 2020-10-27

2020-10-26 19:31 - Wario in Beitrag No. 11 schreibt:
Wahrscheinlich geht das nicht ganz trivial.
Wie könnte man eine Abbruchbedingung ergänzen?



wie man leicht sieht sind, diese Knotenpunkte in Rückwärtsrechnung alle $\equiv 4 \mod 6$, was hieße dass alle Collatz folgen durch eine dieser gehen, wenn die Vermutung stimmt.
Das wäre umgekehrt ein Abbruchkriterium bei Vorwärtsberechnung.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.15, vom Themenstarter, eingetragen 2020-10-27

2020-10-27 20:34 - juergenX in Beitrag No. 14 schreibt:
2020-10-26 19:31 - Wario in Beitrag No. 11 schreibt:
Wahrscheinlich geht das nicht ganz trivial.
Wie könnte man eine Abbruchbedingung ergänzen?



wie man leicht sieht sind, diese Knotenpunkte in Rückwärtsrechnung alle $\equiv 4 \mod 6$, was hieße dass alle Collatz folgen durch eine dieser gehen, wenn die Vermutung stimmt.
Das wäre umgekehrt ein Abbruchkriterium bei Vorwärtsberechnung.


Das scheint als "Bedingung für Knotenpunkt" für die Startzahl 25 nicht auszureichen:
<math>



\def\gobblefour#1#2#3#4{}
\def\C#1{%
\number\numexpr#1\relax
\ifnum#1>1, \else\expandafter\gobblefour\fi
\expandafter\C\expandafter{\the\numexpr\ifodd\numexpr#1\relax3*(#1)+1\else #1/2\fi\relax}}
\begin{document}

%\C{4}
%
%\C{5}
%
%\C{123}
%
\noindent\textsf{Collatzfolge fr 25:} \\
\C{25}

\bigskip\bigskip
\foreach \c in {25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8,
4, 2, 1}{
\pgfmathsetmacro\correct{%
\c==22
|| \c==40 || \c==16 || \c==10
? "{(Knoten)}" : ""
}
\pgfmathsetmacro\test{mod(\c-4,6)==0 ?
"$\rightarrow \bmod(\c-4,6)=0$" : ""}
\noindent\c~\text{\test~ \textbf{\color{red}\correct}} \\
}

% \begin{tikzpicture}
</math>



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
juergenX Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 08.07.2019, Mitteilungen: 305
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.16, eingetragen 2020-10-27

25 ist auch noch eine $\equiv 1 \mod4$ Zahl,

wie z.B. $101 \mapsto 304 \mapsto  152 \mapsto  76$  \\ oops Zufall ;)

alle $\equiv 1 \mod4$ Zahlen wie 101 oder 25 folgen den Schritten:

$m = 4n+1 \mapsto 12n+4  \mapsto 6n+2  \mapsto 3n+1$
$3n+1 < 4n+1$

fallen also in 3 Schritten unter sich selbst.
Wenn wir alle Folgen unterhalb m betrachtet haben, können wir bei $4n+1$  Zahlen in einer Folge abbrechen.

Edit
Wenn wir alle Folgen unterhalb m betrachtet haben, können wir bei $4n+1$  Startzahlen die Berechnung abbrechen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.17, vom Themenstarter, eingetragen 2020-10-28

2020-10-27 22:12 - juergenX in Beitrag No. 16 schreibt:
25 ist auch noch eine $\equiv 1 \mod4$ Zahl,

wie z.B. $101 \mapsto 304 \mapsto  152 \mapsto  76$  \\ oops Zufall ;)

alle $\equiv 1 \mod4$ Zahlen wie 101 oder 25 folgen den Schritten:

$m = 4n+1 \mapsto 12n+4  \mapsto 6n+2  \mapsto 3n+1$
$3n+1 < 4n+1$

fallen also in 3 Schritten unter sich selbst.
Wenn wir alle Folgen unterhalb m betrachtet haben, können wir bei $4n+1$  Zahlen in einer Folge abbrechen.

Edit
Wenn wir alle Folgen unterhalb m betrachtet haben, können wir bei $4n+1$  Startzahlen die Berechnung abbrechen.

Abgesehen davon, dass ich es wenig nachvollziehen kann:
Es geht mir nicht darum für spezielle Zahlen, die besondere Eigenschaften erfüllen, den Collatzgraphen zu bestimmen, sondern für beliebige Startzahlen.


Ich habe aber eine neue Theorie:

· Wäre es möglich den Collatzgraphen für N,...,1 (z.B. N=25) mit irgendwelchen Kniffen und korrekten Abbruchbedingungen zu bestimmen, wäre das Collatzproblem vermutlich gelöst.

· Daher vermute ich, dass man im Ausgangspunkt alle Collatzfolgen für 1,...,N braucht, am besten als Tabelle mit N (25) Spalten; und da jetzt sukzessive Spalten rausstreicht: aus der Hauptspalte N und dann nach und nach aus den Nebenspalten.

Darauf folgt dann noch eine umständliche Tabellenordnungsarbeit.






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 16.02.2013, Mitteilungen: 3685, aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.18, eingetragen 2020-10-28

Hallo Wario,

ich möchte ein paar kleine Anmerkungen loswerden, auch wenn sie vielleicht für dein Vorhaben nicht so wichtig sind.

Ein Vorgänger der 4 ist auch die 1 (denn dies ist ja der einzige bisher bekannte Zyklus).  

Jeder Ast, der mit einem Wert S beginnt, führt sozusagen "geradeaus" zu den Werten der Form S * 2^n mit n=1,2,... Das kommt so, wie du die Werte angeordnet hast, nicht so gut heraus, zumal manchmal der entsprechende Wert ausgelassen ist (weil er eben zu groß wurde) und stattdessen "geradeaus" auf den Wert (S-1)/3 weitergeführt ist, ohne dass man schon rein optisch sieht, dass hier etwas "besonderes" passiert. Insbesondere gibt es damit auch keine Äste, die irgendwo enden.

Die Äste, deren Startwert den Faktor 3 beinhaltet, also 0 mod 3 ist, haben auch nur diese eine eindeutige Fortsetzung, denn diese Eigenschaft reproduziert sich beim Multiplizieren mit 2.

Die anderen Äste haben im "Geradeauszweig" Werte, die immer abwechselnd 1 mod 3 oder 2 mod 3 sind (was ebenfalls eine Folge der Multiplikation mit 2 ist), und damit in jedem zweiten Knoten des Geradeauszweiges je einen Abzweig.  

Grüße und viel Erfolg für dein Projekt.
Gerhard/Gonz



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.19, vom Themenstarter, eingetragen 2020-10-28

2020-10-28 13:16 - gonz in Beitrag No. 18 schreibt:
 Insbesondere gibt es damit auch keine Äste, die irgendwo enden.

Ich weiß nicht, ob ich das alles verstehe.
Heißt das, wenn man bei 1 beginnt und mit der Rückwärtsfolge arbeitet, es könnte nach beliebig vielen Schritten in einem Nebenast wieder ein Wert auftreten, der kleiner als die vorgegebene Startzahl (z.B. 25, in dem Fall eher die Endzahl) ist?


PS: Ich bin übrigens mal so weit.

<math>\pgfplotstableset{
every head row/.style={after row=\hline},
}

% Collatz Sequence
\def\gobblefour#1#2#3#4{}
\def\C#1{%
\number\numexpr#1\relax
\ifnum#1>1, \else\expandafter\gobblefour\fi
\expandafter\C\expandafter{\the\numexpr\ifodd\numexpr#1\relax3*(#1)+1\else #1/2\fi\relax}}

% Length of Sequence
\newcounter{arraycard}
\def\Length#1{%
\setcounter{arraycard}{0}%
\foreach \x in #1{     \stepcounter{arraycard}   }%
\thearraycard%
}

\setlength{\tabcolsep}{3.33pt}
\begin{document}
\pgfmathtruncatemacro\N{25}% Startnumber

\pgfmathtruncatemacro\Len{0}% Startvalue
\pgfplotsinvokeforeach{1,...,\N}{%#1
\pgfmathtruncatemacro\n{#1}
% Collatz
\xdef\CollatzCol{\C{\n}}
% Lengths
\foreach[count=\tmpCount] \x in \CollatzCol { \xdef\tempLen{\tmpCount} }
\pgfmathtruncatemacro\Len{\tempLen > \Len ? \tempLen : \Len}
% Columns
\edef\nextcol{\noexpand\pgfplotstableset{
create on use/#1/.style={  create col/set list={\CollatzCol}  }
}
\noexpand\pgfplotstablenew[columns={1,...,\n}]{\noexpand\Len}\noexpand\collatztable
}\nextcol
% Row counter - optional
\pgfplotstableset{
create on use/No/.style={  create col/set list={1,...,\Len}  }
}
\pgfplotstablenew[columns={No}, ]{\n}\rowcount
}%%

%Maximum Length: \Len
% show it:
\pgfmathtruncatemacro\Ns{\N-1}% Startnumber minus 1
\pgfplotstabletypeset[columns={No, \N,\Ns,...,1},
columns/No/.style={ column type/.add={}{|},
},
empty cells with={--},
font=\footnotesize,
]\collatztable

% \begin{tikzpicture}
% axis}
</math>

Das eigentliche Grauen steht noch aus, also diese Sortier- und Streichungsarbeit.






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 11.09.2008, Mitteilungen: 6615, aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.20, eingetragen 2020-10-29

2020-10-28 18:04 - Wario in Beitrag No. 19 schreibt:
Heißt das, wenn man bei 1 beginnt und mit der Rückwärtsfolge arbeitet, es könnte nach beliebig vielen Schritten in einem Nebenast wieder ein Wert auftreten, der kleiner als die vorgegebene Startzahl (z.B. 25, in dem Fall eher die Endzahl) ist?
Ausschließen kann man das nach dem bisherigen Wissensstand wohl nicht.
Das ist genau der Punkt, warum ein Aufbau der Tabelle von rechts nach links so schwierig ist.
Stell Dir vor, Du hättest jetzt nicht mit 25 sondern mit 27 gearbeitet.
Du baust den Baum von rechts nach links auf, aber die 27 lässt einfach auf sich warten. Du weißt auch nicht, in welchem der vielen Nebenäste (mit nicht durch drei teilbaren Zahlen) Du suchen musst.

Baust Du den Baum dagegen von links nach rechts auf, dann musst Du nur genau die Werte berechnen, die auch im Baum vorkommen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.21, vom Themenstarter, eingetragen 2020-10-29

2020-10-29 02:33 - Kitaktus in Beitrag No. 20 schreibt:
2020-10-28 18:04 - Wario in Beitrag No. 19 schreibt:
Heißt das, wenn man bei 1 beginnt und mit der Rückwärtsfolge arbeitet, es könnte nach beliebig vielen Schritten in einem Nebenast wieder ein Wert auftreten, der kleiner als die vorgegebene Startzahl (z.B. 25, in dem Fall eher die Endzahl) ist?
Ausschließen kann man das nach dem bisherigen Wissensstand wohl nicht.
Das ist genau der Punkt, warum ein Aufbau der Tabelle von rechts nach links so schwierig ist.
Stell Dir vor, Du hättest jetzt nicht mit 25 sondern mit 27 gearbeitet.
Du baust den Baum von rechts nach links auf, aber die 27 lässt einfach auf sich warten. Du weißt auch nicht, in welchem der vielen Nebenäste (mit nicht durch drei teilbaren Zahlen) Du suchen musst.

Baust Du den Baum dagegen von links nach rechts auf, dann musst Du nur genau die Werte berechnen, die auch im Baum vorkommen.

Gut, dann ist die Tabellenmethode jetzt das Ziel.

Ich hätte dazu jetzt fast ein Zwischenergebnis angegeben. Aber muss noch kleinere Syntax- und Expansionsprobleme lösen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Iterator Junior Letzter Besuch: im letzten Monat
Mitglied seit: 29.05.2020, Mitteilungen: 17
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.22, eingetragen 2020-10-30

2020-10-28 00:40 - Wario in Beitrag No. 17 schreibt:

Ich habe aber eine neue Theorie:

· Wäre es möglich den Collatzgraphen für N,...,1 (z.B. N=25) mit irgendwelchen Kniffen und korrekten Abbruchbedingungen zu bestimmen, wäre das Collatzproblem vermutlich gelöst.

Dein Ansinnen in allen Ehren, aber viele haben versucht den Collatz-Baum rückwärts aufzubauen und sind daran gescheitert.
Dü müsstest dazu zeigen, dass alle natürlichen Zahlen darin enthalten sind. Insbesondere müsstest du zeigen, dass es keine isolierten Teilbäume gibt, die entweder gegen Undendlich gehen oder eine isolierte Schleife bilden.

Das Problem ist, dass sich überall beliebig lange Teilfolgen einmischen. Du kannst so beliebig lange Folgen konstruieren bzw. in Vorwärtsrichtung auch beliebige Folgen, die jede natürliche Zahl übertreffen. Andererseits kann man aber auch zeigen, dass es unendlich viele Folgen gibt, die so gegen 1 gehen. Theoretisch kann man auch über unendlich viele Folgen sprechen, die ähnlich gegen 1 gehen. Aber selbst das reicht nicht aus, Aussagen über jede natürliche Zahl zu treffen. Theoretisch kann man so statistisch über "fast alle" Collatz-Folgen argumentieren, die gegen 1 gehen. Das hat zB. Terence Tao gemacht. Aber selbst das reicht nicht aus, über alle Folgen sprechen zu können. Alles deutet auf eine Komplexität hin, dass man über ein "Gödel-Problem" spricht. Danach wäre es unmöglich, Aussagen über alle n zu treffen, so dass sich diese überhaupt beweisen lassen. Das ist vermutlich auch der Grund, warum Tao davon abrät, sich tiefer mit dem Collatz-Problem zu beschäftigen. Es frisst nur unnötige Zeit, da es nicht axiomatisch beweisbar ist. Auch wenn (fast) alle der Überzeugung sind, dass das Collatz-Theorem wahr ist. 🙂



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.23, vom Themenstarter, eingetragen 2020-10-30

2020-10-30 20:13 - Iterator in Beitrag No. 22 schreibt:
Dein Ansinnen in allen Ehren, ...

Du hast Beitrag 17 (21) nicht ganz gelesen oder mich falsch verstanden: Ich habe gesagt (und begründet), dass ich die Tabellenmethode verfolgen werde.

Im Übrigen ist die Lösung des Collatz-Problems hier nicht das Ziel, es geht alleine darum, den sogen. Collatz-Graphen für beliebige Startzahlen (automatisiert) zu erstellen, nicht mehr aber auch nicht weniger.



Frage: Kennt jemand vielleicht eine Seite, die online Collatzgraphen erstellt? Oder zumindest ein paar weitere fertige Beispiele als Bild, ähnlich des Bildes Beitrag 0?
Damit ich vergleichen kann.

Ich habe leider nur das Beispielbild für den Fall N=25.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Iterator Junior Letzter Besuch: im letzten Monat
Mitglied seit: 29.05.2020, Mitteilungen: 17
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.24, eingetragen 2020-10-30

Okay, das ist doch realtiv einfach.

Hast du eine ungerade Zahl u ungleich 1 und nicht durch 3 teilbar, dann bekommst du alle Zweige mit den vorhergehenden geraden (g') und ungeraden (u') Zahlen mit:

g'=2*u*4^n, u'=(2*u*4^n-1)/3 (n>=0)

Mit jeder geraden Zahl g ist natürlich auch g'=2*g ein Vorgänger.

 







Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.25, vom Themenstarter, eingetragen 2020-10-30

2020-10-30 22:07 - Iterator in Beitrag No. 24 schreibt:
Okay, das ist doch realtiv einfach.

Hast du eine ungerade Zahl u ungleich 1 und nicht durch 3 teilbar, dann bekommst du alle Zweige mit den vorhergehenden geraden (g') und ungeraden (u') Zahlen mit:

g'=2*u, u'=(2*u-1)/3 oder g'=(3*u+1)*4^n, u'=[(3*u+1)*4^n-1}/3

Ist es eine gerade Zahl 2*g dann ist g'=4*g.

Die Pfade müssen aber an der richtigen Stelle beginnen und abbrechen. Daher schätze ich, dass das so nicht geht bzw. nicht das Gewünschte liefert.

Erinnerung: Der Collatzgraph zu einer Startzahl N ist dasjenige Baumdiagramm, dass alle Pfade der Collatzfolgen für 1,2,3,...,N enthält.

Z.B. N = 25



PS: Falls jmd. weitere Beispiele aus Skripten hat wäre das hilfreich.
2020-10-30 21:01 - Wario in Beitrag No. 23 schreibt:
Frage: Kennt jemand vielleicht eine Seite, die online Collatzgraphen erstellt? Oder zumindest ein paar weitere fertige Beispiele als Bild, ähnlich des Bildes Beitrag 0?
Damit ich vergleichen kann.

Ich habe leider nur das Beispielbild für den Fall N=25.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Iterator Junior Letzter Besuch: im letzten Monat
Mitglied seit: 29.05.2020, Mitteilungen: 17
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.26, eingetragen 2020-10-30

Ich hatte noch einen kleinen Fehler, den habe ich korrigiert.

Du kannst ja jetzt mal testen, zB. mit 5.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.27, vom Themenstarter, eingetragen 2020-10-30

2020-10-30 22:36 - Iterator in Beitrag No. 26 schreibt:
Ich hatte noch einen kleinen Fehler, den habe ich korrigiert.

Du kannst ja jetzt mal testen, zB. mit 5.


Mir ist so oder so unklar, wie daraus am Ende z.B. dieses Bild

entstehen soll.
Wenn Du das zeigen bzw. programmieren kannst, gut.

Ich gehe von der Annahme aus, dass man eingangs alle Collatzfolgen für 1,2,...,N braucht und aus diesen dann durch Ausschluss und Umordnung den Collatzgraphen bildet.  Daher verfolge ich erstmal weiter die "Tabellenmethode".



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Iterator Junior Letzter Besuch: im letzten Monat
Mitglied seit: 29.05.2020, Mitteilungen: 17
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.28, eingetragen 2020-10-30

In Collatz Folgen 1..N treten aber i.a. Zahlen >> N auf.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.29, vom Themenstarter, eingetragen 2020-10-30

2020-10-30 23:14 - Iterator in Beitrag No. 28 schreibt:
In Collatz Folgen 1..N treten aber i.a. Zahlen >> N auf.

Das ist aber auch bekannt.

Dann muss die Definition vermutlich so lauten:

Der Collatzgraph zu einer Startzahl N ist dasjenige Baumdiagramm, dass alle Pfade der Collatzfolgen enthält, deren Pfadenden 1,2,3,...,N sind.

(vielleicht kann es jmd. besser formulieren)


Ich will wirklich nur dieses Bild erstellen für allgemeine Startnummern (so schwer es zu glauben sein mag).
Nicht etwa Allgemeines oder Weiteres zu Collatzfolge, sofern das für das Problem nicht relevant ist.  



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.30, vom Themenstarter, eingetragen 2020-11-01

Ich kann für eine Startzahl $N$ aus den Collatzfolgen für $1,...,N$ diejenigen Isolieren, aus denen sich der Collatzgraph zusammensetzt.
Z.B. für $N=20$ sind das $T_1=\{ 19,18,15,12 \}$

Aber ich habe Probleme mit der Zeilen- bzw. Zellenreduzierung und deren anschließende Anordnung.

Vorschläge?


<math>
\pgfmathtruncatemacro\N{20}% Startnumber
%Tables
\pgfmathtruncatemacro\Np{\N-1}% Startnumber minus 1
\setlength{\tabcolsep}{3.33pt}
\pgfplotstableset{
every head row/.style={after row=\hline},
%every last row/.style={after row=\hline},
font=\footnotesize,
1000 sep={\,},
min exponent for 1000 sep=4,
%column type=l,
columns/No/.style={  string type,  column type/.add={}{|},    },
empty cells with={--},
}


% Collatz Sequence ==================
\def\gobblefour#1#2#3#4{}
\def\C#1{%
\number\numexpr#1\relax
\ifnum#1>1, \else\expandafter\gobblefour\fi
\expandafter\C\expandafter{\the\numexpr\ifodd\numexpr#1\relax3*(#1)+1\else #1/2\fi\relax}}
% =============================

\begin{document}
\section{Collatz-Table for $\boldsymbol{N=\N}$}
\pgfmathtruncatemacro\MaxLen{0}% Startvalue for Length
\pgfplotsinvokeforeach{1,...,\N}{%#1
\pgfmathtruncatemacro\n{#1}
% Collatz
\xdef\CollatzCol{\C{\n}}
% Lengths =================
\pgfmathtruncatemacro\Len{dim({\CollatzCol})}
% Show: Sequence of\n  has the length \Len \\
\pgfmathtruncatemacro\MaxLen{\Len > \MaxLen ? \Len : \MaxLen}
% Maximum of Column
\pgfmathtruncatemacro\Max{max(\CollatzCol)}
\foreach[count=\Pos] \k in \CollatzCol {
\pgfmathsetmacro\test{\k==\Max ?  \Pos :  0}
\ifnum\test=0 \else \xdef\MaxPos{\test} \fi
}
\pgfmathtruncatemacro\MaxPosNo{\MaxPos-1}
% Save Values Len, Max, MaxPos, MaxPosNo
\edef\savevalues{
\noexpand\tikzset{  declare function={
{Len#1}= \Len;
{Max#1}= \Max;
{MaxPos#1}= \MaxPos;
{MaxPosNo#1}= \MaxPosNo;
}    }
}\savevalues
% Columns  =================
\edef\nextcol{\noexpand\pgfplotstableset{
create on use/#1/.style={  create col/set list={\CollatzCol}  }
}
\noexpand\pgfplotstablenew[columns={1,...,\n}]{\MaxLen}\noexpand\collatztable
}\nextcol
% Row counter - optional  =================
\pgfplotstableset{
create on use/No/.style={
create col/set list={1,...,\MaxLen, $L$, Max, at}  }
}
\pgfplotstablenew[columns={No}, ]{\n}\rowcount
}%%

\pgfplotstableset{
every row no \MaxLen/.style={after row=\hline, before row=\hline},
}

%Maximum Length: \MaxLen
% Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\collatztable}

% Add Length Row:
\let\LenRowList=\empty
\foreach \col in {1,...,\N}{
\pgfmathparse{Len\col}
\ifx\empty\LenRowList{} \xdef\LenRowList{\pgfmathresult}%
\else \xdef\LenRowList{\LenRowList, \pgfmathresult}%
\fi}
%Show LenRow:  \LenRowList \par
%
\edef\createLenRow{
\noexpand\pgfplotstableread[col sep=comma, row sep=crcr]{
0, \LenRowList  \noexpand\\
}\noexpand\LenRow}\createLenRow
% Concatenate
\pgfplotstablevertcat{\collatztable}{\LenRow}
%Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\LenRow} \par
%Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\collatztable}

% Add MaxRow:
\let\MaxRowList=\empty
\foreach \col in {1,...,\N}{
\pgfmathparse{Max\col}
\ifx\empty\MaxRowList{} \xdef\MaxRowList{\pgfmathresult}%
\else \xdef\MaxRowList{\MaxRowList, \pgfmathresult}%
\fi}
%Show MaxRow:  \MaxRowList \par
%
\edef\createMaxRow{
\noexpand\pgfplotstableread[col sep=comma, row sep=crcr]{
0, \MaxRowList  \noexpand\\
}\noexpand\MaxRow}\createMaxRow
% Concatenate
\pgfplotstablevertcat{\collatztable}{\MaxRow}
%Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\MaxRow} \par
%Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\collatztable}

% Add MaxPosRow:
\let\MaxPosList=\empty
\foreach \col in {1,...,\N}{
\pgfmathparse{MaxPos\col}
\ifx\empty\MaxPosList{} \xdef\MaxPosList{\pgfmathresult}%
\else \xdef\MaxPosList{\MaxPosList, \pgfmathresult}%
\fi}
%Show MaxPos:  \MaxPosList \par
%
\edef\createMaxPosRow{
\noexpand\pgfplotstableread[col sep=comma, row sep=crcr]{
0, \MaxPosList  \noexpand\\
}\noexpand\MaxPosRow}\createMaxPosRow
% Concatenate
\pgfplotstablevertcat{\collatztable}{\MaxPosRow}
%Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\MaxPosRow}
%Show:
\pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\collatztable}


%\newpage
\section{Column reduced Table}

% \def\Main{\N, \Np,..., 2, 1} % old
\def\Main{1,...,\N}

\let\Exclude=\empty % create list
\let\Target=\empty % create list
\newif\ifexcludeelem
\excludeelemfalse

% Exclude List
\foreach \col in {\N,...,1}{%% \Main reverse
\pgfmathtruncatemacro\MaxLenCol{Len\col}%
\pgfmathtruncatemacro\MaxLenColNo{\MaxLenCol-1}% Last temp-row No.
%Show: Len\col = \MaxLenCol,  Len{\col}No = \MaxLenColNo \\
\foreach \row in {1,...,\MaxLenColNo}{%%
\pgfplotstablegetelem{\row}{\col}\of{\collatztable}
\ifx\empty\Exclude{} \xdef\Exclude{\pgfplotsretval}%
\else \xdef\Exclude{\Exclude, \pgfplotsretval}%
\fi
}}% %%
% Target List
\foreach \i in \Main{%%
\excludeelemtrue
\foreach \j in \Exclude{%
\ifx\i\j \global\excludeelemfalse\fi
}%
\ifexcludeelem  %Show: \i\par
% Target List
\ifx\empty\Target{} \xdef\Target{\i}%
\else \xdef\Target{\i, \Target}% reverse: \Target, \i
\fi
%  \else Show: {\i} is not in the list. \par
\fi}%%
Show: \pgfplotstabletypeset[columns/.expanded={No,\Target},]\collatztable

%\newpage
\noindent\textbf{Main List:} $M=\{ \Main \}$ \par
\noindent\textbf{Exclude List:}  $E=$\{\Exclude\} \par
\noindent\textbf{Target List: $\boldsymbol{T_1=M \setminus E =}$\{\Target\} }

% \begin{tikzpicture}
% axis}
</math>

Muss so aussehen:




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90 Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 18.03.2019, Mitteilungen: 494, aus: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.31, eingetragen 2020-11-02

Die erforderliche Anzahl an Pfaden $T_{(N)}$ welche alle Zahlen von $1 \dots N$ enthalten ergibt sich grob nach meinen Überlegungen mit: $$T_{(N)}= \left[ \frac{N-3}{6} + \frac{3,85}{100}N \right] $$ (Für $N\gtrsim 1000$)

Für $N=1000$ wäre damit schon ein Baum mit $206$ Pfaden nötig.
Ist das deiner Meinung nach dann noch überschaubar graphisch darstellbar, da Du ja eine Lösung für "beliebige $N$" suchst ?


-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 16.02.2013, Mitteilungen: 3685, aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.32, eingetragen 2020-11-02

Hallo Wario,

das Problem könnte jedenfalls sein, einen Algorithmus zu finden, der den Baum "übersichtlich" anordnet? Hast du da schon Ideen für - ich fände das eine ziemlich spannende Sache.

Grüße
Gonz



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.33, vom Themenstarter, eingetragen 2020-11-02

@ Beitrag No.31:

Die Abschätzung der Maximallänge ist m.E. nur dann wichtig, wenn man mit der Rückwärtsfolge arbeitet. Aber selbst dann könnte man damit vermutlich im Allgmeinen beliebig viele Folgenglieder zuviel berechnen.

@ Beitrag No.32:

Das frage ich ja gerade.
Ich mache erstmal folgendes: Ich schreibe alle Folgen C(N) von 1,...,N spaltenweise auf. Dann streiche ich alle Spalten, die bereits als Folgendglied irgendwo vorkamen (das ist mit Main List, Exclude List, Target List gemeint. Die erste Zeile muss man in der Exclude List natürlich auslassen, da man sonst alles streichen würde).

Bei N=20 bleiben dabei T1={19,18,15,12} übrig. Diese Folgen enthalten nun alle Zahlen 1,2,...,20 und müssen somit alle nötigen Glieder für den Collatzgraphen für 20 enthalten.

Jetzt müssen aber in den verbleibenden Spalten 19,18,15,12 noch Zellen gestrichen werden und diese müssen dann noch angeordnet werden.

Wenn ich da so weitermache wäre das eine aufwendige Sache:
Ich müsste quasi für jedes verbleibende Element alle anderen Spalten durchsuchen, ob es in ihnen enthalten ist (lediglich die erste Zeile kann man überspringen).

2020-11-01 20:11 - Wario in Beitrag No. 30 schreibt:
<math>
\pgfmathtruncatemacro\N{20}% Startnumber
%Tables
\pgfmathtruncatemacro\Np{\N-1}% Startnumber minus 1
\setlength{\tabcolsep}{3.33pt}
\pgfplotstableset{
every head row/.style={after row=\hline},
%every last row/.style={after row=\hline},
font=\footnotesize,
1000 sep={\,},
min exponent for 1000 sep=4,
%column type=l,
columns/No/.style={  string type,  column type/.add={}{|},    },
empty cells with={--},
}


% Collatz Sequence ==================
\def\gobblefour#1#2#3#4{}
\def\C#1{%
\number\numexpr#1\relax
\ifnum#1>1, \else\expandafter\gobblefour\fi
\expandafter\C\expandafter{\the\numexpr\ifodd\numexpr#1\relax3*(#1)+1\else #1/2\fi\relax}}
% =============================

\begin{document}
%\section{Collatz-Table for $\boldsymbol{N=\N}$}
\pgfmathtruncatemacro\MaxLen{0}% Startvalue for Length
\pgfplotsinvokeforeach{1,...,\N}{%#1
\pgfmathtruncatemacro\n{#1}
% Collatz
\xdef\CollatzCol{\C{\n}}
% Lengths =================
\pgfmathtruncatemacro\Len{dim({\CollatzCol})}
% Show: Sequence of\n  has the length \Len \\
\pgfmathtruncatemacro\MaxLen{\Len > \MaxLen ? \Len : \MaxLen}
% Maximum of Column
\pgfmathtruncatemacro\Max{max(\CollatzCol)}
\foreach[count=\Pos] \k in \CollatzCol {
\pgfmathsetmacro\test{\k==\Max ?  \Pos :  0}
\ifnum\test=0 \else \xdef\MaxPos{\test} \fi
}
\pgfmathtruncatemacro\MaxPosNo{\MaxPos-1}
% Save Values Len, Max, MaxPos, MaxPosNo
\edef\savevalues{
\noexpand\tikzset{  declare function={
{Len#1}= \Len;
{Max#1}= \Max;
{MaxPos#1}= \MaxPos;
{MaxPosNo#1}= \MaxPosNo;
}    }
}\savevalues
% Columns  =================
\edef\nextcol{\noexpand\pgfplotstableset{
create on use/#1/.style={  create col/set list={\CollatzCol}  }
}
\noexpand\pgfplotstablenew[columns={1,...,\n}]{\MaxLen}\noexpand\collatztable
}\nextcol
% Row counter - optional  =================
\pgfplotstableset{
create on use/No/.style={
create col/set list={1,...,\MaxLen, $L$, Max, at}  }
}
\pgfplotstablenew[columns={No}, ]{\n}\rowcount
}%%

\pgfplotstableset{
every row no \MaxLen/.style={after row=\hline, before row=\hline},
}

%Maximum Length: \MaxLen
% Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\collatztable}

% Add Length Row:
\let\LenRowList=\empty
\foreach \col in {1,...,\N}{
\pgfmathparse{Len\col}
\ifx\empty\LenRowList{} \xdef\LenRowList{\pgfmathresult}%
\else \xdef\LenRowList{\LenRowList, \pgfmathresult}%
\fi}
%Show LenRow:  \LenRowList \par
%
\edef\createLenRow{
\noexpand\pgfplotstableread[col sep=comma, row sep=crcr]{
0, \LenRowList  \noexpand\\
}\noexpand\LenRow}\createLenRow
% Concatenate
\pgfplotstablevertcat{\collatztable}{\LenRow}
%Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\LenRow} \par
%Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\collatztable}

% Add MaxRow:
\let\MaxRowList=\empty
\foreach \col in {1,...,\N}{
\pgfmathparse{Max\col}
\ifx\empty\MaxRowList{} \xdef\MaxRowList{\pgfmathresult}%
\else \xdef\MaxRowList{\MaxRowList, \pgfmathresult}%
\fi}
%Show MaxRow:  \MaxRowList \par
%
\edef\createMaxRow{
\noexpand\pgfplotstableread[col sep=comma, row sep=crcr]{
0, \MaxRowList  \noexpand\\
}\noexpand\MaxRow}\createMaxRow
% Concatenate
\pgfplotstablevertcat{\collatztable}{\MaxRow}
%Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\MaxRow} \par
%Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\collatztable}

% Add MaxPosRow:
\let\MaxPosList=\empty
\foreach \col in {1,...,\N}{
\pgfmathparse{MaxPos\col}
\ifx\empty\MaxPosList{} \xdef\MaxPosList{\pgfmathresult}%
\else \xdef\MaxPosList{\MaxPosList, \pgfmathresult}%
\fi}
%Show MaxPos:  \MaxPosList \par
%
\edef\createMaxPosRow{
\noexpand\pgfplotstableread[col sep=comma, row sep=crcr]{
0, \MaxPosList  \noexpand\\
}\noexpand\MaxPosRow}\createMaxPosRow
% Concatenate
\pgfplotstablevertcat{\collatztable}{\MaxPosRow}
%Show: \pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\MaxPosRow}
%Show:
%\pgfplotstabletypeset[columns={No, \N,\Np,...,1},]{\collatztable}


%\newpage
%\section{Column reduced Table}

% \def\Main{\N, \Np,..., 2, 1} % old
\def\Main{1,...,\N}

\let\Exclude=\empty % create list
\let\Target=\empty % create list
\newif\ifexcludeelem
\excludeelemfalse

% Exclude List
\foreach \col in {\N,...,1}{%% \Main reverse
\pgfmathtruncatemacro\MaxLenCol{Len\col}%
\pgfmathtruncatemacro\MaxLenColNo{\MaxLenCol-1}% Last temp-row No.
%Show: Len\col = \MaxLenCol,  Len{\col}No = \MaxLenColNo \\
\foreach \row in {1,...,\MaxLenColNo}{%%
\pgfplotstablegetelem{\row}{\col}\of{\collatztable}
\ifx\empty\Exclude{} \xdef\Exclude{\pgfplotsretval}%
\else \xdef\Exclude{\Exclude, \pgfplotsretval}%
\fi
}}% %%
% Target List
\foreach \i in \Main{%%
\excludeelemtrue
\foreach \j in \Exclude{%
\ifx\i\j \global\excludeelemfalse\fi
}%
\ifexcludeelem  %Show: \i\par
% Target List
\ifx\empty\Target{} \xdef\Target{\i}%
\else \xdef\Target{\i, \Target}% reverse: \Target, \i
\fi
%  \else Show: {\i} is not in the list. \par
\fi}%%
Show: \pgfplotstabletypeset[columns/.expanded={No,\Target},]\collatztable

%\newpage
%\noindent\textbf{Main List:} $M=\{ \Main \}$ \par
%\noindent\textbf{Exclude List:}  $E=$\{\Exclude\} \par
%\noindent\textbf{Target List: $\boldsymbol{T_1=M \setminus E =}$\{\Target\} }

% \begin{tikzpicture}
% axis}
</math>


Ich müsste schauen, ob die 58 irgenwo vorkommt und dann überall streichen.
Dann schauen, ob die 29 irgendwo vorkommt  und dann überall streichen.
... ... ...

Das gleiche muss man dann mit den Elementen der ersten Zeile, die übrig geblieben ist machen. Das ist zusammen extrem aufwendig.

Daher frage ich mich ob das einfacher geht.





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90 Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 18.03.2019, Mitteilungen: 494, aus: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.34, eingetragen 2020-11-02

2020-11-02 23:05 - Wario in Beitrag No. 33 schreibt:
@ Beitrag No.31:

Die Abschätzung der Maximallänge ist m.E. nur dann wichtig, wenn man mit der Rückwärtsfolge arbeitet. Aber selbst dann könnte man damit vermutlich im Allgmeinen beliebig viele Folgenglieder zuviel berechnen.

In #31 geht es doch gar nicht um eine "Abschätzung irgend einer Maximallänge".

2020-11-02 23:05 - Wario in Beitrag No. 33 schreibt:

Daher frage ich mich ob das einfacher geht.

Das kann man einfacher hinbekommen.
Die "Aussortierung" an sich ist weniger das Problem als die, wie in #31 bereits erwähnte, graphische Umsetzung.  


-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.35, vom Themenstarter, eingetragen 2020-11-03

2020-11-02 23:53 - haegar90 in Beitrag No. 34 schreibt:
2020-11-02 23:05 - Wario in Beitrag No. 33 schreibt:
@ Beitrag No.31:

Die Abschätzung der Maximallänge ist m.E. nur dann wichtig, wenn man mit der Rückwärtsfolge arbeitet. Aber selbst dann könnte man damit vermutlich im Allgmeinen beliebig viele Folgenglieder zuviel berechnen.

a) In #31 geht es doch gar nicht um eine "Abschätzung irgend einer Maximallänge".

2020-11-02 23:05 - Wario in Beitrag No. 33 schreibt:

Daher frage ich mich ob das einfacher geht.

b) Das kann man einfacher hinbekommen.
Die "Aussortierung" an sich ist weniger das Problem als die, wie in #31 bereits erwähnte, graphische Umsetzung.  


a) Ok, missverstanden. Ich glaube trotzdem, dass die Abschätzung der Pfadanzahl bei der "Tabellenmethode" hier nichts nützt. Da ich das im Grunde schon habe: die Anzahl der isolierten Spalten ist gleichzeitig die Anzahl der benötigten Pfade bzw. Äste.
Ich will jetzt keine neuen Ansätze versuchen, die davon wegführen (!).


b) Wenn man die Zellen der Tabelle richtig angeordnet hat, ist die graphische Ausgabe davon eine trivale Ergänzung.

Denke Dir das Bild Beitrag 30 als Tabelle (ohne Pfeile und dort, wo nichts steht einen Strich oder eine 0).






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90 Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 18.03.2019, Mitteilungen: 494, aus: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.36, eingetragen 2020-11-03

Wenn das so ist, wie Du es in #35 schreibst, dann hast Du das Problem ja quasi schon gelöst.


-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.37, vom Themenstarter, eingetragen 2020-11-03

2020-11-03 00:40 - haegar90 in Beitrag No. 36 schreibt:
Wenn das so ist, wie Du es in #35 schreibst, dann hast Du das Problem ja quasi schon gelöst.

Nein, die richtige Anordnung der Zellen fehlt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wario Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 01.05.2020, Mitteilungen: 191
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.38, vom Themenstarter, eingetragen 2020-11-03

Weiteres Zwischenergebnis

Man kann die Zeilenreduzierung so vornehmen:
Für eine der reduzierten Spalten bildet man die Differenzmenge zu allen übrigen Spalten. Dann bleiben genau die Zahlen übrig, die im Collatzgraphen stehen.

Z.B. N=28; für die Spalte 18:



(wer den Graphen für N=28 nicht kennt muss es jetzt einfach glauben.)


Und das müsste man jetzt für alle Spalten der spaltenreduzierten Tabelle machen.
Die richtige Anordnung hat man damit noch nicht. Entweder hat man die geschickt zugleich erledigt oder man muss jetzt die zeilenreduzierten Spalten alle nochmal nach den Anschlusselementen durchsuchen.

Das ist mir offengestanden gerade zu aufwendig zu programmieren. Da weiß ich gerade nicht, ob ich das machen werde.

So unfassbar und unvollstellbar es klingen mag: mich hat die Aufgabe der Tabellen- bzw. Listensortierung /-anordnung interessiert. Das sogen. Collatzproblem ist mir eigentlich relativ egal; das hat sich lediglich als gutes Testbeispiel angeboten.

Aber was dieses Collatz-Geschwobel angeht: Ich stelle fest, dieser Graph vom Typ Beitrag 0 etc. ist immer mal wieder zu sehen, man findet aber selten eine gescheite Umsetzung dafür.
Es würde mich extrem wundern, wenn jemand dieses Problem löst oder auch überhaupt nur einen vielversprechenden Ansatz ersinnt, wenn solche Grundwerkzeuge ungeklärt sind bzw. dafür keine konsistente Methode ausgearbeitet ist.  Naja.

Eigentlich will ich das Fass nicht aufmachen (weil die Gefahr besteht, dass ich das dann diskutieren muss), aber: mathematisch ist es relativ klar, was mit der Tabelle geschieht. An sich sind das alles Matrixoperationen (Streichung, Umordnung), die sich als Folge von Matrixprodukten darstellen lassen (leere Zellen, wie gesagt, am besten mit 0). Damit würde ich vermutlich am Collatzproblem rumforschen (wenn ich es täte, was ich nicht tue). Somit auch von mir einen schlauen Einwurf, der vermutlich inhaltlich stimmt, aber ansonsten nichtsagend bleibt, weil er nicht zu Ende geführt wurde.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 16.02.2013, Mitteilungen: 3685, aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.39, eingetragen 2020-11-03

Trotzdem bleibt das ein spannendes Thema (an dem "eigentlichen" Collatz-Problem haben wir uns hier auf dem MP natürlich auch schon ausgetobt). Ich habe mal aus den Altlasten auf der Festplatte das Programm herausgesucht, das den Baum erstellt, allerdings bisher nicht in Spalten geordnet, sondern als Baumstruktur mit einer Liste von Knoten und deren nachfolgern:

python
N   = 27
Baum = {}
Baum[1]=[]
 
print("Collatz Reverse 1.02/F by gonz@gmx.biz für N = ",N)
 
for myN in range(2,N+1):
    aktuell  = myN
    vorherig = 0
    while not aktuell in Baum:
        if vorherig>0: Baum[aktuell]=[vorherig]
        else: Baum[aktuell]=[]
        vorherig=aktuell
        if aktuell%2==0: aktuell=aktuell//2
        else: aktuell=aktuell*3+1
    if vorherig>0: Baum[aktuell].append(vorherig)
 
print(Baum)


Der Vorteil in python ist hier, dass man die Listenverarbeitung schon direkt bekommt und nicht programmieren muss. Sicher ginge das auch schöner und einfacher. Aktuell liefert es eine Datenstruktur der folgenden Art:


{1: [2], 2: [4], 3: [6], 10: [3, 20], 5: [10], 16: [5, 32], 8: [16], 4: [8], 6: [12], 7: [14], 22: [7, 44], 11: [22], 34: [11], 17: [34], 52: [17], 26: [52], 13: [26], 40: [13, 80], 20: [40], 9: [18], 28: [9], 14: [28], 12: [24], 15: [], 46: [15, 92], 23: [46], 70: [23], 35: [70], 106: [35], 53: [106], 160: [53], 80: [160], 18: [], 19: [38], 58: [19], 29: [58], 88: [29], 44: [88], 21: [], 64: [21], 32: [64], 24: [], 25: [], 76: [25], 38: [76], 27: [], 82: [27], 41: [82], 124: [41], 62: [124], 31: [62], 94: [31], 47: [94], 142: [47], 71: [142], 214: [71], 107: [214], 322: [107], 161: [322], 484: [161], 242: [484], 121: [242], 364: [121], 182: [364], 91: [182], 274: [91], 137: [274], 412: [137], 206: [412], 103: [206], 310: [103], 155: [310], 466: [155], 233: [466], 700: [233], 350: [700], 175: [350], 526: [175], 263: [526], 790: [263], 395: [790], 1186: [395], 593: [1186], 1780: [593], 890: [1780], 445: [890], 1336: [445], 668: [1336], 334: [668], 167: [334], 502: [167], 251: [502], 754: [251], 377: [754], 1132: [377], 566: [1132], 283: [566], 850: [283], 425: [850], 1276: [425], 638: [1276], 319: [638], 958: [319], 479: [958], 1438: [479], 719: [1438], 2158: [719], 1079: [2158], 3238: [1079], 1619: [3238], 4858: [1619], 2429: [4858], 7288: [2429], 3644: [7288], 1822: [3644], 911: [1822], 2734: [911], 1367: [2734], 4102: [1367], 2051: [4102], 6154: [2051], 3077: [6154], 9232: [3077], 4616: [9232], 2308: [4616], 1154: [2308], 577: [1154], 1732: [577], 866: [1732], 433: [866], 1300: [433], 650: [1300], 325: [650], 976: [325], 488: [976], 244: [488], 122: [244], 61: [122], 184: [61], 92: [184]}


Ich denke bei Gelegenheit versuche ich das mal in Richtung der graphischen Darstellung ausbauen...

Für größere N wächst die Breite des Baumes tatsächlich exponential, bevor sie dann durch die Begrenzung auf den max. Startwert wieder abnimmt. Vielleicht kann man die Ausgabe rekursiv machen und immer Zweige an dem jeweiligen Wurzelknoten "zusammenkleben"...

Einen schönen Tag wünscht
Gerhard/Gonz



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 1Gehe zur Seite: 1 | 2  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 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]