Collatz-Vermutung

[wurzel]

'''
Dieses Skript kann auch online ausgeführt werden.
'''
def sequence(K,start_n):
child=[start_n]
c=start_n
double_c=0
stop=False
while stop==False:
p=K*c
p=int(p)
if not p % 2==0:
p=p+1
m=0
while p % 2==0:
m=m+1
p=p/2
p=int(p)

c=int(p)
if (c in child):
double_c=c
stop=True
else:
child.append(c)
return child,double_c

# Ausführung

K=3.65
for i in range(1,100):
if not i % 2==0:
child,double_c = sequence(K,i)
print(i,len(child),double_c)

'''
Alle Folgen ungerader Zahlen sind fallend und enden mit 1.
Warum ?
https://sourceforge.net/projects/trial-collatz-proof/
'''

[grubenfox]

von 2024: viewtopic.php?t=57929

[Sirius3]

@wurzel: eingerückt wird immer mit 4 Leerzeichen pro Ebene, nicht 8, 5, 3 oder 6.
Variablennamen sollten immer komplett klein geschrieben werden und aussagekräftiger sein, als nur ein Buchstabe.
Statt `not p % 2 == 0` benutzt man `p % 2 != 0`.
Wie while-Schleife sollte eine while-True sein, dann kann man sich das Flag `stop` sparen.
`double_c = 0` wird nie benutzt.
Ich vermute mal, die Zeile `p = int(p)` sollte in der inneren while-Schleife sein, und nicht danach. Statt dessen benutzt man aber Ganzzahldivision `p //= 2`.
`m` wird gar nicht benutzt.
Insgesamt kommt man dann bei sowas raus:

Code: Alles auswählen

K = 3.65

def sequence(k, start_n):
    children = [start_n]
    c = start_n
    while True:
        c = int(k * c)
        if c % 2 != 0:
            c += 1
        while c % 2 == 0:
            c //= 2

        if c in children:
            break
        children.append(c)
    return children, c

def main():
    for i in range(1, 100, 2):
        children, double_c = sequence(K, i)
        print(i, len(children), double_c)

if __name__ == "__main__":
    main()

Was ist an der Folge 3, 5, 9, 1 fallend?

[__blackjack__]

@wurzel: Wenn man das nicht in einen Code-Block setzt, kann man damit nichts anfangen, weil die Einrückung dann nicht sichtbar ist.

Ob wirklich alle Folgen in einer 1 enden ist ja gerade nicht geklärt. Das ist ja nur eine Vermutung. Aber das hattest Du ja auch letztes Jahr nicht so wirklich verstanden wenn ich mich recht erinnere. Das man das nicht _beweisen_ kann, in dem man das für eine endliche Anzahl von Beispielen durchrechnet, und daraus schliesst, das wird dann wohl für alle Zahlen so sein.

Neben der fehlenden Einrückung könnte die Formatierung des Quelltextes besser sein um das leichter lesbar und verständlich zu machen. Beispielsweise eine durchgehend konsistente Einrückung mit vier Leerzeichen pro Ebene. Selbst eine andere Anzahl von Leerzeichen wäre noch besser als verschiedene Blöcke die logisch auf der gleichen Ebene stehen, optisch aber unterschiedlich weit einzurücken.

Leerzeichen um das ``=`` bei Zuweisungen und binäre Operatoren, und nach Kommas erhöhen die Lesbarkeit auch.

Das Hauptprogramm sollte in einer Funktion stehen, damit es keine globalen Variablen die man absichtlich oder aus versehen in Funktionen verwenden kann.

Um Bedingungen von ``if`` gehören keine unnötigen Klammern. Das ist Python, nicht C oder Java oder eine andere Sprache wo das aus syntaktischen Gründen immer geklammert sein muss.

Falls `K` keine Konstante ist, sollte das nicht gross geschrieben werden. Auch wenn der Wert nicht verändert wird, scheint das nicht als Konstante gemeint zu sein, weil es als Argument übergeben wird, und das macht bei Konstanten keinen Sinn.

Falls man die ungeraden Zahlen von 1 bis 99 betrachten will, generiert man eher nicht alle Zahlen von 1 bis 99 und prüft ob die jeweilige Zahl ungerade ist, sondern generiert gezielt nur die ungeraden Zahlen. `range()` kennt dafür ja auch eine Schrittweite.

`child` ist kein sinnvoller Name für eine Liste. Das ist ja kein Kind, das ist eine Liste von Werten. Eventuell welche die ”Kinder” sind, aber da das hier ja kein Baum ist, macht das nicht wirklich Sinn. Das ist die Folge von Zahlen, die nach dieser Rechenvorschrift entsteht. Also eigentlich müsste das `sequence` heissen. Was ein Problem ist weil die Funktion schon so heisst. Was sie aber nicht sollte, weil eine Sequenz ein ”Ding” ist (im weitesten Sinne), und keine Tätigkeit. Funktionen benennt man aber üblicherweise nach Tätigkeiten. Genau aus diesem Grund, das man sie leichter von eher passiven Werten unterscheiden kann.

`double_c` wird am Anfang eine 0 zugewiesen die niemals irgendwo verwendet wird. Ansonsten wird dem Namen an einer einzigen Stelle der Wert von `c` zugewiesen und gleich danach wird das dann einmal Rückgabewert verwendet. Damit ist der Name überflüssig, weil man da auch einfach `c` verwenden kann.

Man vergleicht nicht mit literalen Wahrheitswerten. Da kommt doch wieder ein Wahrheitswert heraus. Entweder der, den man sowieso schon hatte, dann kann man den auch gleich verwenden. Oder dessen Gegenteil. Dafür gibt es ``not``. Also nicht ``while stop == False:`` sondern ``while not stop:``.

`stop` ist aber sowieso überflüssig. Einfach eine ``while True:``-Schleife und die Schleife an der Stelle wo man `stop` den Wert `False` zuweist, die Schleife mit ``break`` verlassen. Da hier nach der Schleife nur eine ``return``-Anweisung steht, kann man das auch gleich an Stelle vom ``break`` schreiben. Beziehungsweise kann man den Code auch leicht umstellen, mit einer leeren Sequenz anfangen und ``while c not in sequence:`` als Bedingung verwenden. Dann braucht man weder ein extra Flag noch einen Abbruch im Schleifenkörper.

Der Wert von `m` wird nirgends verwendet, das kann also weg. `p` wird eigentlich auch nicht verwendet, das wird dann wieder `c` zugewiesen, mit `c` wird aber nichts gemacht, während mit `p` operiert wird, das hätte man also auch gleich alles mit `c` berechnen können.

Wenn man die Ganzzahldivision verwenden würde, braucht man am Ende keine Gleitkommazahl mit `int()` wieder in eine ganze Zahl umwandeln. Hier können nicht einmal Abweichungen durch Gleitkommaarithmetik entstehen, weil ja immer nur ganze Zahlen durch zwei geteilt werden.

Code: Alles auswählen

#!/usr/bin/env python3


def calculate_sequence(k, start_n):
    c = start_n
    sequence = []
    while c not in sequence:
        sequence.append(c)
        c = int(k * c)
        c += c % 2
        while c % 2 == 0:
            c //= 2

    return sequence, c


def main():
    k = 3.65
    for i in range(1, 100, 2):
        sequence, c = calculate_sequence(k, i)
        print(f"{i:2} {len(sequence):2} {c}")


if __name__ == "__main__":
    main()

[Pedroski55]

Es scheint mir, sobald man auf eine Zahl wie 160, 80, 40 usw, ist die Lösung in Sicht. Auch Primzahlen leiten zur Lösung.

Um den Satz zu beweisen, muss man nur beweisen, dass man immer auf eine solche Zahl kommt.

Das Ganze hängt auch irgendwie mit den Primzahlen zusammen, die schon immer mysteriös waren!

Start = 53, Resultat = [53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1], Sequencelänge = 12

Code: Alles auswählen

def rauf(num):
    next_num = 3 * num + 1
    return next_num

def runter(num):
    next_num = int(num / 2)
    return next_num

def coller(num):
    seq = []
    seq.append(num)
    while num !=1:
        if num % 2 == 1:
            num = rauf(num)
            seq.append(num)
        elif num % 2 == 0:
            num = runter(num)
            seq.append(num)    
    return seq

P = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
         37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
         79, 83, 89, 97, 103, 107,
         109, 113, 127, 131, 137, 139,
         149, 151, 157, 163, 167, 173, 179, 181,
         191, 193, 197, 199]

for prim in P:
    res = coller(prim)
    print(f'Start = {prim}, Resultat = {res}, Sequencelänge = {len(res)}')

Ist es nicht so, dass alle ganze Zahlen als Resultat der Multiplication zweier Primzahlen entstehen können?

[noisefloor]

Hallo,

Ist es nicht so, dass alle ganze Zahlen als Resultat der Multiplication zweier Primzahlen entstehen können?

Nein, das ist mathematisch doppelt falsch. Primzahlen lassen sich nicht als Produkt aus zwei ganzen Zahlen herstellen, weil die Primzahlen keine Teiler haben außer 1 und sich selber. D.h. eine Primzahl kann man nur als Produkt aus eins mal sich selber darstellen. 1 ist aber keine Primzahl, weil 1 nur einen Teiler hat (nämlich 1, also sich selber), Primzahlen haben aber zwei Teiler, nämlich 1 und sich selber. Zweiter Punkt: die ganzen Zahlen umfassen negativ Zahlen. Da es keine negativen Primzahlen gibt, weil Primzahlen per Definition größer 1 sind, kann man auf keinen Fall eine negative Zahl als Produkt aus zwei Primzahlen darstellen.

Gruß, noisefloor

[Sirius3]

@noisefloor: Pedroski55 schrieb, dass jede Zahl als Produkt zweier Primzahlen geschrieben werden kann, nicht dass jede Primzahl als Produkt zweier Zahlen.
Die richtige Antwort ist, dass die Primfaktorzerlegung einer natürlichen Zahl eindeutig ist.

@Pedroski55: wie schon geschrieben, benutzt man am besten Ganzzahl-Division. Wenn die elif-Bedingung exakt das Gegenteil der if-Bedingung ist, dann benutzt man else. Und wenn in beiden Blöcken der selbe Code steht, kann man ihn auch einmal außerhalb schreiben.

Code: Alles auswählen

def rauf(num):
    return 3 * num + 1

def runter(num):
    return num // 2

def coller(num):
    seq = [num]
    while num != 1:
        if num % 2 == 1:
            num = rauf(num)
        else:
            num = runter(num)
        seq.append(num)
    return seq

[__blackjack__]

@Sirius3: noisefloor hat da schon recht, denn wenn Pedroski55 schreibt, dass sich jede ganze Zahl als Multiplikation von zwei Primzahlen schreiben lässt, dann muss das ja auch für Primzahlen selbst gelten, denn das sind ja auch ganze Zahlen. Es reicht also zu zeigen, dass es für Primzahlen nicht gilt. Dann kann es nicht für alle ganzen Zahlen gelten.

Der Inhalt der ``while``-Schleife ist immer noch so lang…

Code: Alles auswählen

def collatz(num):
    seq = [num]
    while num != 1:
        seq.append(num := (rauf if num % 2 == 1 else runter)(num))
    return seq

[noisefloor]

@Sirius3: richtig, jede _natürliche_ Zahl außer 1 und Primzahlen lässt sich eindeutig als Produkt aus Primzahlen ("Primfaktorzerlegung") darstellen. Das ändert aber nichts daran, dass die Aussage von Pedroski55 "Ist es nicht so, dass alle ganze Zahlen als Resultat der Multiplication zweier Primzahlen entstehen können?" doppelt falsch ist.

Gruß, noisefloor

[Sirius3]

@noisefloor: ja, aber aus anderen Gründen. Primzahlen lassen sich aus dem Produkt einer Primzahl darstellen. Die 1 läßt sich als Produkt aus 0 Primzahlen darstellen.