Collatz Folgen 3n+1

[wurzel]

Hallo zusammen,

meine Idee ist es, die Beweis-Collatz-Vermutung zu untersuchen.

Mir ist aufgefallen, dass die Folgen:

"Kind, Mama, Oma, Urgroßmütter" ,
"C:Program Files\CommonFilesSystem\ado\en-US" und
Collatz sequence (3n+1)

gleiche Datenstrukturen haben.

Beschreibung unter:
https://sourceforge.net/projects/trial-collatz-proof/

(collatz-proof_e.py 10 KB )

[__blackjack__]

@wurzel: Anmerkungen zum Quelltext:

Auf Modulebene sollte nur Code stehen der Konstanten, Funktionen, und Klassen definiert. Das Hauptprogramm steht üblicherweise in einer Funktion die `main()` heisst.

Namen werden in Python klein_mit_unterstrichen geschrieben. Ausnahmen sind Konstanten (KOMPLETT_GROSS) und Klassen (PascalCase).

Namen sollten keine kryptischen Abkürzungen enthalten oder gar nur daraus bestehen. Der Name soll dem Leser vermitteln was der Wert dahinter im Programm bedeutet, nicht zum rätseln zwingen.

Eingerückt wird per Konvention vier Leerzeichen pro Ebene.

Man definiert Namen erst wenn man sie braucht und nicht viele Zeilen vorher.

Funktionen bekommen alles was sie ausser Konstanten benötigen als Argument(e) übergeben. Das `sequence()` die Liste `exponenten` verwendet/füllt, ist beispielsweise sehr undurchsichtig. Funktionen sollten aber auch nicht übergebene leere Listen füllen sondern diese Liste(n) selbst erstellen und als Rückgabewert liefern.

`start_N` und `Start_N` sind als Namen viel zu ähnlich. Letztlich braucht man beide Namen nicht, weil der Wert kurz darauf jeweils an einen anderen Namen gebunden wird.

Es wird an mehreren Stellen `int()` mit einer ganzen Zahl aufgerufen. Das macht keinen Sinn.

Statt eine leere Liste zu erzeugen und gleich in der nächsten Zeile etwas mit `append()` anzuhängen, sollte man gleich die Liste mit dem/den Element(en) hinschreiben.

Man macht keine Vergleiche mit literalen Wahrheitswerten. Bei dem Vergleich kommt doch nur wieder ein Wahrheitswert bei heraus. Entweder der, den man sowieso schon hatte; dann kann man den auch gleich nehmen. Oder das Gegenteil davon; dafür gibt es ``not``. Also statt ``while stop == False:`` schreibt man ``while not stop:``.

Ein Flag wie `stop` für eine ``while``-Schleife ist unnötig wenn man stattdessen die Schleife an der entsprechenden Stelle mit ``break`` verlassen kann.

`check_2()` und `check_3()` sind im Grunde die gleiche Funktion, nur mit einem anderen Wert auf den getestet wird. Das sollte *eine* Funktion sein, die diesen Wert als Argument übergeben bekommt.

Wenn man abhängig von einem Test `True` oder `False` als Ergebnis hat, dann braucht man kein ``if``/``else``, denn der Test selbst ergibt bereits den Wahrheitswert den man sucht.

Wenn man eine Liste `odd_and_even_numbers` hat, braucht man die ungeraden Zahlen aus dieser Liste nicht zusätzlich in einer weiteren Liste speichern, denn diese Liste kann man ja jederzeit aus `odd_and_even_numbers` generieren wenn man sie braucht. Ähnliches gilt für `exponents` und `reverse_exponents`.

`i` in `sequence()` wird zwar hochgezählt, aber für nichts verwendet.

Das ``else`` zum ``while`` macht keinen Sinn wenn da kein ``break`` in der Schleife vorkommt.

Die ``while``-Schleife in `sequence()` wird zur Endlosschleife wenn `number` nicht ungerade ist. Das sollte man prüfen und entsprechend eine Ausnahme auslösen.

`index_names` wird definiert, aber nirgends verwendet. Genau wie `eltern` ist das auch nur eine Liste mit aufsteigenden ganzen Zahlen die von der Länge einer anderen Liste abhängen, also etwas das man so auch gar nicht hart in den Quelltext schreiben sollte, da man diese Sequenz mit `range()` erzeugen kann.

``for i in range(len(sequence)):`` nur um `i` dann als Index in die Sequenz zu verwenden ist in Python ein „anti-pattern“. Man kann direkt über die Elemente iterieren, ohne den Umweg über einen Laufindex. Falls man zusätzlich eine laufende Zahl benötigt, gibt es die `enumerate()`-Funktion. Und falls man über mehr als eine Sequenz ”parallel” iterieren möchte, gibt es die `zip()`-Funktion.

Die Definition von `S_eltern` *in* der Schleife macht keinen Sinn, weil hier in jedem Schleifendurchlauf immer wieder der gleiche Wert an diesen Namen gebunden wird.

Bei `S_kinder` werden wiederholt in einer Schleife Zeichenketten “addiert“. Das ist potentiell ineffizient, da Zeichenketten unveränderbar sind, und so in jedem Schleifendurchlauf mehr und mehr Daten im Speicher kopiert werden müssen. Der idiomatische Weg ist die `join()`-Methode auf Zeichenketten.

Um Bedingungen bei ``if`` & Co braucht man keine Klammern.

Die ``while``-Schleife zum suchen der Wurzel ist eigentlich eine ``for``-Schleife.

Das erste ``stack_row.insert(0,index)`` ist ein bisschen sinnfrei weil die Liste zu dem Zeitpunkt garantiert leer ist. Das würde sofort ins Auge fallen wenn die leere Liste nicht viele Zeilen davor schon angelegt wird, obwohl sie dort noch gar nicht benötigt wird.

Es ist ineffizient eine Liste als Stack zu verwenden in dem man mit `insert()` und `remove()` immer das erste Element hinzufügt/entfernt. `remove()` ist zudem noch verwirrend, weil man dafür erst einmal durchschauen muss, dass der Wert der da entfernt wird, grundsätzlich der erste Wert ist. Listen kann man prima und effizient als Stack benutzen wenn man `append()` und `pop()` verwendet um das *letzte* Element als oberstes Element im Stack zu behandeln.

`sp()` ist kein guter Name und im Grunde ist es ein bisschen fraglich ob sich dafür eine Funktion lohnt, denn das ist eigentlich nur eine ”Multiplikation” einer Zeichenkette mit einer Zahl:

Code: Alles auswählen

In [29]: "*" * 42
Out[29]: '******************************************'

Das da immer wieder zwischen einer leeren und einer nicht-leeren Namensliste unterschieden wird, ist unnötig. Wenn man statt Namen lieber die Indizes ausgeben möchte, dann übergibt man halt einfach eine Namensliste die Indizes statt Namen enthält, und schon kann man sich diese ganzen Unterscheidungen sparen.

`tree()` gibt den Baum aus, zerstört dabei aber die Datenstruktur die ausgegeben wird, weil Elemente aus `kinder` gelöscht werden. Das sollte nicht passieren, denn das ist sehr überraschend für den Leser das eine Ausgabefunktion die Daten verändert.

In `numbers_previous_table()` werden am Anfang vier leere Listen erzeugt, die nirgends verwendet werden.

``int()`` ist etwas umständlich für ``0``.

Die ``while``-Schleife in der Funktion sollte eigentlich eine ``for``for-Schleife sein.

Mit `N_r` wird etwas berechnet was aber nirgends verwendet wird.

``sequence[len(sequence)-1]`` ist umständlich für ``sequence[-1]``.

Statt ``not a == b`` würde man einfach ``a != b`` schreiben.

Die ganze `S.append()`-Aufrufe machen keinen Sinn. Statt immer wieder eine Liste mit Zeilen zu füllen um die dann in einer Schleife auszugeben, könnte man da gleich `print()` verwenden.

Die `frm()`-Funktion wird nirgends verwendet, und auch hier stellt sich die Frage ob das eine Funktion sein muss, denn das ist eigentlich auch ein ziemlich simpler Ausdruck:

Code: Alles auswählen

In [34]: def frm(n,a):
    ...:     L=len(str(n))
    ...:     S=''
    ...:     while a>L :
    ...:         S=S+' '
    ...:         a=a-1
    ...:     S=S+str(n)
    ...:     return S
    ...: 

In [35]: frm(42, 5)
Out[35]: '   42'

In [36]: def frm(n,a):
    ...:     return f"{n:{a}}"
    ...: 

In [37]: frm(42, 5)
Out[37]: '   42'

Zwischenstand:

Code: Alles auswählen

#!/usr/bin/env python3
# Trial Collatz Proof
# Author: Aleh Kavalenka, Datum: 13. December 2023
#         email: kavalenka@web.de
#         90473  Nuremberg
from itertools import chain


def pause():
    input("\ncontinue - Enter")
    print()


def is_divisible(number, divisor):
    return number % divisor == 0


def sequence(number, odd_numbers_count):
    if is_divisible(number, 2):
        raise ValueError(f"number ({number!r}) must be odd")

    odd_numbers = []
    exponents = []
    while True:
        if not is_divisible(number, 2):
            odd_numbers.append(number)
            if len(odd_numbers) == odd_numbers_count:
                break
            number = 3 * number + 1
            exponent = 0
            while is_divisible(number, 2):
                exponent += 1
                number //= 2
            exponents.append(exponent)

    return odd_numbers, exponents


def reverse_sequence(odd_numbers, exponents):
    reverse_odd_numbers = []
    odd_number = odd_numbers[len(exponents)]
    for exponent in reversed(exponents):
        reverse_odd_numbers.append(odd_number)
        odd_number = int((pow(2, exponent) * odd_number - 1) / 3)
    reverse_odd_numbers.append(odd_number)
    return reverse_odd_numbers


def print_tree(kinder, eltern, names):
    kinder_all = list(chain.from_iterable(kinder))
    rechts = [-1] * len(eltern)

    # suchen Eltern-Name, der in Kinder-Namens fehlt — Wurzel
    # find root
    for index in range(len(kinder)):
        if eltern[index] not in kinder_all:
            rechts[index] = 0
            break
    else:
        print("Wurzel fehlt")
        input()
        return

    row_stack = [index]
    rechts[index] = 0

    #   wurzel
    print("    " * rechts[index], names[eltern[index]])

    cell = kinder[index][0]
    print("    " * rechts[index], "└──", names[cell])

    kinder = [kinder_indizes.copy() for kinder_indizes in kinder]
    j = 0
    while True:
        if cell in eltern:
            index = eltern.index(cell)
            if rechts[index] < 0:
                j = j + 1
                rechts[index] = j
                row_stack.append(index)
            if kinder[index]:
                cell = kinder[index][0]
                print("    " * rechts[index], "└──", names[cell])
                kinder[index].remove(cell)

        else:
            index = row_stack[-1]
            if kinder[index]:
                j = rechts[index]
                cell = kinder[index][0]
                print("    " * rechts[index], "└──", names[cell])
                kinder[index].remove(cell)
            else:
                row_stack.pop()
                index = row_stack[-1]
                if len(row_stack) == 1:
                    break


def numbers_previous_table(
    odd_numbers_start, odd_numbers_count, exponents_count
):
    a = 1  # a=5, a=7 test negativ
    print()
    print("Table Numbers-Previous .")
    print("Each number N has many previous V ")
    print("   N      V = (2^m *N-", a, ")/3  (m)")
    kinder = []
    eltern = []
    number_o = 0
    for i in range(odd_numbers_start, odd_numbers_count):
        if not (is_divisible(i, 2) or is_divisible(i, 3)):
            number_os = []
            output = [str(i), "       "]
            if not is_divisible(i, 3):
                eltern.append(i)
            exponent = 0
            while exponent < exponents_count:
                exponent += 1
                number_o = pow(2, exponent) * i - a

                if is_divisible(number_o, 3):
                    number_o = number_o // 3

                    if number_o != eltern[-1]:  # It's impossible.
                        output.append(f"{number_o}({exponent})   ")
                        number_os.append(number_o)

            print("  ", "".join(output))
            if number_os:
                kinder.append(number_os)

    return kinder, eltern


def main():
    print("Collatz-sequence  (Example)")
    number = 133
    print("start_N =", number)
    m = 0
    loops = 0
    numbers = [number]
    while True:
        if not is_divisible(number, 2):
            m = 0
            next_number = 3 * number + 1
            print("if odd  : N=3*", number, "+1=", next_number)
            number = next_number
        else:
            m += 1
            number //= 2
            print("if even : N=N/2=", number, "   m = ", m)

        numbers.append(number)
        if number == 1:
            loops += 1
            if loops == 3:
                break
    print()
    print("odd and even numbers: ", numbers)
    print()
    print("Further, only odd numbers are used.")
    print(
        "odd numbers: ",
        [number for number in numbers if not is_divisible(number, 2)],
    )
    pause()

    print("Formulas for forward and backward sequences.")
    print("Forward-sequence   (3 *N+1)/2^m ")
    odd_numbers_count = 43
    odd_numbers, exponents = sequence(27, odd_numbers_count)
    assert len(odd_numbers) == odd_numbers_count
    print("odd_numbers N ", odd_numbers)
    print("odd_numbers_count=", len(odd_numbers))
    print("exponents m ", exponents)
    print()
    print("Backward_sequence (2^m *N-1)/3 ")
    reverse_odd_numbers = reverse_sequence(odd_numbers, exponents)
    print("reverse_odd_numbers N ", reverse_odd_numbers)
    print("reverse_exponents m ", list(reversed(exponents)))
    pause()

    print()
    print("A tree (Example) ")
    names = [
        "Paul   ",
        "Eva    ",
        "Leonie ",
        "Sabrina",
        "Stefan ",
        "Alice  ",
        "Daniel ",
        "Lea    ",
        "Elina  ",
    ]
    assert all(len(name) == len(names[0]) for name in names)

    kinder = [[2, 3], [0], [4, 5], [5, 7, 8]]

    print("Table Parent-Children.")
    print("Every parent has children.")
    for eltern_name, kinder_indizes in zip(names, kinder):
        print(eltern_name, " : ", "  ".join(names[i] for i in kinder_indizes))
    print()
    print("Note C.")
    print("The tables data has the next properties:")
    print()
    print("1.Every parent has children.")
    print("2.No repetitions among parents and ")
    print("  no repetitions among children")
    print("3.One of parents is not a child.")
    print()
    print("These 3.Properties are necessary and sufficient to build a tree.")

    print()
    print("A tree")
    print_tree(kinder, range(len(kinder)), names)
    pause()

    kinder, eltern = numbers_previous_table(1, 50, 10)
    print()
    print("The table can be infinitely long and wide.")
    pause()

    print()
    print("Note A.")
    print(
        "Table Numbers-Previous does not have two identical Previous numbers."
    )
    print("Proof by contradiction.")
    print(" Let it be for two odd unequal Current numbers A and B ")
    print("    (2^m *A -1)/3 = (2^n *B -1)/3 ,")
    print("     2^m *A -2^n *B = 0")
    print("at m>n")
    print("    2^n *(2^(m-n) *A - B) = 0, which is false,")
    print("    because 2^(m-n)*A is an even natural number,")
    print("    and B is an odd natural number,")
    print("at m<n")
    print("    2^m *(A - 2^(n-m) * B) = 0, which is false")
    print("    because 2^(n-m) * B is an even natural number,")
    print("    and A is an odd natural number,")
    print("at m=n")
    print("    A = B, which is wrong")
    print("    because A and B are unequal numbers")
    print()
    print("So the assumption (2^m *A -1)/3 = (2^n *B -1)/3 is False.")

    print()
    print("Note B.")
    print("N=(2^m *A -1)/3")
    print(" If A is divisible by 3,")
    print("    A=B*3 ,")
    print(" then N=(2^m *B*3-1)/3 = 2^m* B - 1/3 ,")
    print(" this is unacceptable because N is a natural number.")
    print(" The numbers 3,6,9 ... is missing in Current column.")
    pause()

    print()
    print("The table Numbers-Previous has the same properties as")
    print("the Parents-Children table (Note C):")
    print("1.Every Number has Previous.")
    print("2.No repetitions among Numbers and ")
    print("  no repetitions among Previous  (Note A)")
    print("3.One of Numbers is not a Previous.")
    print()
    print("These 3.Properties are necessary and sufficient to build a tree.")
    pause()

    print("A tree")
    print_tree(
        kinder,
        eltern,
        list(map(str, range(max(chain.from_iterable(kinder)) + 1))),
    )
    pause()

    print("A tree can be infinitely long and wide.")
    print()
    print()
    print("A tree is a collection of nodes that are connected by edges and")
    print("has a hierarchical relationship between the nodes.")
    print("The topmost node of the tree is called the root.")
    print("The edges form a single path from each node to the root (node 1).")
    print("Each path is a Collatz sequence ")
    print("After 1 comes:")
    print("    3*1+1=4")
    print("    4/2  =2 ")
    print("    4/2  =1 ")
    print()
    print("    3*1+1=4")
    print("    4/2  =2 ")
    print("    4/2  =1 ")
    print(" and no other loops. ")
    print()
    print(" Thank you.")


if __name__ == "__main__":
    main()

Die Hauptfunktion ist ein bisschen zu lang für meinen Geschmack. Und die Ausgabe des Baums zu umständlich, mit zu viel wiederholtem Code. Da würde man besser eine rekursive Datenstruktur für den Baum wählen und eine rekursive Funktion zur Ausgabe, oder zumindest eine rekursive Funktion in eine iterative umwandeln die näher an einer rekursiven Funktion ist, also wo der gesamte Zustand auf einem Stack abgelegt wird.

[wurzel]

Ich möchte mich bei __blackjack__ für die Programmierstunde
und die praktische Anwendung von Python bedanken.
Meisterkurs. Hut ab.

So wie ich es verstehe, akzeptieren Sie meine Version des Beweises.
Oder?

[__deets__]

Zum Beweis ist nichts gesagt worden. Und aus einer nicht-Besprechung Zustimmung zu folgern ist schon eine bemerkenswerte Volte.

[Qubit]

So wie ich es verstehe, akzeptieren Sie meine Version des Beweises.
Oder?

Die Ansätze mit "reversen Bäumen" sind zumindestens nicht neu und haben bisher keine anerkannten Beweise der Collatz-Vermutung geliefert.

Dazu müsstest du mind. beweisen, dass der reverse Baum

1. zusammenhängend ist und alle Zahlen umfasst
2. keine Teilbäume mit (beliebigen) Zyklen beinhaltet

Insbesondere reicht es nicht, nur Zusammenhänge für Vorgänger- oder Nachfolger-Zahlen zu zeigen.
(zB. könnte bei einem Zyklus so etwas sein wie ..-> aaa1234567 -> XXX1234567 -> bbb1234567-> .. -> ccc1234567 -> XXX1234567 -> ..)

[wurzel]

Note C.
1.Every parent has children.
2.No repetitions among parents and
no repetitions among children
3.One of parents is not a child.

The table Numbers-Previous has the same properties as
the Parents-Children table (Note C):
1.Every Number has Previous.
2.No repetitions among Numbers and
no repetitions among Previous (Note A)
3.One of Numbers is not a Previous. (root 1)

These 3.Properties are necessary and sufficient to build a tree.

Aus Sicht der Datenstruktur sind diese beiden Tabellen gleich.
Auch die entsprechenden Bäume sind gleich.
Die Kanten bilden einen einzelnen Pfad von jede Knote zur Wurzel (Knote 1).
Jeder Pfad ist Collatz-Folge.

[__blackjack__]

@wurzel: Jeder Pfad ist Collatz-Folge gilt doch aber nur wenn wirklich von *jeder* Zahl eine Collatz-Folge ausgeht. Genau *das* musst Du ja beweisen. Das geht nicht mit einem kleinen Programm das einen kleinen/endlichen Baum aufbaut das für *alle* *unendlich* vielen ganzen Zahlen zu zeigen.

[wurzel]

Convert the parent-child table
into a hierarchical tree step by step

please read the file build_a_tree.txt at
https://sourceforge.net/projects/trial-collatz-proof/

[__deets__]

Das hat immer noch nichts mit einem Beweis zu tun. Das ist eine algorithmische Vorschrift, die fuer konkrete Eltern-Kind-Tabellen einen Baum erzeugt. Wenn die Collatz-Vermutung durch Angabe weniger positiver Beispiele zu beweisen waere, waere sie schon seit 100 Jahren bewiesen. Ist sie aber nicht. Nichts in dieser Anweisung bezieht sich auf die zu beweisende Konvergenz des Verfahrens.

[DeaD_EyE]

Bewiesen ist das erst, wenn der Computer alle Folgen durchrechnen kann. Es würde unendlich lange dauern, da für n jede natürliche Zahl eingesetzt werden kann. Man kann einen Computer nutzen, um Beweise für etwas zu erbringen, dass endlich ist. Sobald unendlich viele Zahlen ins Spiel kommen, kann ein Computer die Aufgabe niemals lösen.

Für das Collatz-Problem gibt es noch keinen mathematischen Beweis.