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.

[narpfel]

@__blackjack__: Die `while`-Schleife ist mir immer noch ein bisschen zu lang; so wird’s besser:

Code: Alles auswählen

Λ=lambda n:3*n+1
V=lambda n:n//2
def collatz(n):
 l=[n]
 while n!=1:l+=[n:=[V,Λ][n%2](n)]
 return l

[Pedroski55]

Beweis von Collatz:

Code: Alles auswählen

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

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

g_nums = [str(i) for i in range(0, 10, 2)] # ['0', '2', '4', '6', '8']
u_nums = [str(i) for i in range(1, 10, 2)] # ['1', '3', '5', '7', '9']

def coller2(num):
    seq = []
    seq.append(num)
    if num == 1:
        num = rauf(num)
        seq.append(num)
    while num !=1:
        wort = str(num)
        if wort[-1] in u_nums:
            num = rauf(num)
            seq.append(num)
        else:
            num = runter(num)
            seq.append(num)    
    return seq

def gerade_ungerade(num):
    gerade = 0
    ungerade = 0
    seq = coller2(num)
    print(f'Sequenzlänge = {len(seq)}')    
    for s in seq:
        wort = str(s)
        if wort[-1] in g_nums:
            gerade +=1
        else: ungerade +=1
    return (num, gerade, ungerade, seq)

Grosse Zahlen machen doch keine unangenehm langen Sequenzen:

Code: Alles auswählen

res  = gerade_ungerade(43272534769)

Sequenzlänge = 246

Code: Alles auswählen

res  = gerade_ungerade(43272534769123)

Sequenzlänge = 212

Keine Ahnung wie man hier eine Tabelle einführt, kann mir jemand behilflich sein?

Satz von Collatz Beweis:

Wenn eine Zahl Z ungerade ist, wird die nächste Zahl Z so berechnet:

Z = 3 x Z + 1

Z 1 3 5 7 9
nächste Z 4 10 16 22 28

Man sieht dass die zwischen Z und folgender Z ist immer 2, und zwischen nächste Z und folgender nächste Z ist immer 6. Das ist aber unwichtig. Wichtig ist, dass jede nächste Z gerade ist.

Wenn eine Z in 10, 14, oder 18 endet, Z / 2 ergibt eine ungerade Z, aber daraus entstehen 3 neue gerade Z.

Z 10 14 18
nächste Z 5 7 9
nächste Z 16 22 28

Alle gerade Z werden durch 2 geteilt. Dies kann zur Verkettung von gerade Z führen:

Z 3 x Z + 1 Z / 2 Z / 2 Z / 2
4325 12976 6488 3244 1622 811

Eine Verkettung von ungeraden Zahlen kommt nie vor.

Egal mit welcher Z man anfängt, die gerade Z überwiegen, etwa im Verhältnis 2:1. Weil gerade Z überwiegen, und gerade Z eine Verkettung bilden können, wird eine Sequenz immer ein Ende haben.

Der Anfang vom Ende ist 16, oder eine gerade Zahl, die ein Produkt von 16 und eine gerade Zahl ist:

21: [21, 64, 32, 16, 8, 4, 2, 1]
22: [22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Ruhe in Frieden, Herr Collatz!

[snafu]

Man könnte die Berechnung natürlich auch als Generator umsetzen. Dann benötigt man nicht zwingend die komplette Folge als Liste, wenn man nur einen Teil davon untersuchen möchte. Zum Beispiel so:

Code: Alles auswählen

from collections import deque
from itertools import chain, islice

def generate_collatz_numbers(n):
    if n < 1:
        raise ValueError(f"n must be >= 1, got: {n}")
    while n > 1:
        if n % 2:
            yield (n := 3 * n + 1)
        yield (n := n // 2)

def count_collatz_steps(start):
    return sum(1 for _ in generate_collatz_numbers(start))

def get_collatz_sequence(start, window_size=None):
    numbers = chain([start], generate_collatz_numbers(start))
    if window_size is None:
        seq = numbers
    elif window_size >= 0:
        seq = islice(numbers, window_size)
    else:
        seq = deque(numbers, -window_size)
    return list(seq)

def main():
    start = 42
    print(count_collatz_steps(start))
    print(get_collatz_sequence(start))
    print(get_collatz_sequence(start, 5))
    print(get_collatz_sequence(start, -5))

if __name__ == "__main__":
    main()

[snafu]

Ich habe beim Generator ein ``else`` nicht gesetzt, komme aber trotzdem auf die richtigen Zahlenfolgen. Stimmt das denn wirklich, dass jede ungerade Zahl >= 1 immer nach einem 3n + 1 zu einer geraden Zahl und damit zu einer oder mehreren n/2 führt? Man müsste ja dann "nur" zeigen, dass KEINE ungerade Zahl existiert, für die das nicht funktioniert. Aber welche sollte das sein? Eine ungerade Zahl ergibt verdoppelt immer eine gerade Zahl. Und eine gerade Zahl + die ungerade Zahl (somit n*3) ergibt immer eine ungerade. Und diese + 1 ist immer gerade, womit die andere Regel in Kraft tritt. Mit Sicherheit bin ich mathematisch zu unbegabt, denn nach meinem Verständnis ist genau das doch der Beweis, dass die Collatz-Folge für jede natürliche Zahl irgendwann gegen Eins konvergieren muss, oder etwa nicht? Geht es vielleicht darum, dass noch andere Schleifen vor [4, 2, 1] existieren könnten und man dies nicht sicher ausschließen kann?

[snafu]

Hier ist ein ganz gutes Video dazu:
https://www.youtube.com/watch?v=oF40neXSkAg

Geht im Kern wohl tatsächlich darum, dass mögliche vorherige Zyklen nicht sicher ausgeschlossen werden können.

[Sirius3]

@snafu: eine gerade Zahl hat mindestens einen Primfaktor 2. Wenn man zwei Zahlen miteinander multipliziert, werden die Potenzen der Primfaktoren addiert. Wenn es also den Primfaktor 2 nicht gibt, ist der auch nicht im Produkt. Oder einfach gesagt, das Produkt zweier ungerader Zahlen ist wieder ungerade. Dagegen ist die Summe zweier ungerader Zahlen gerade. Wenn also a ungerade ist, ist a * 3 + 1 gerade.
Wenn man dann diesen Collatz-Schritt mit dem nächsten Zusammennimmt erhält man (a * 3 + 1) / 2 oder a + (a+1) / 2. Ob dieses Ergebnis nun gerade oder ungerade ist, ist nicht so einfach zu bestimmen. Nach diesem Doppelschritt wird die Folge also größer. Die Frage ist, ob es a gibt, so dass die Folge immer größer wird, oder zumindest irgendwann mal wieder bei a landet.

@Pedroski55: es ist kein mathematischer Beweis, aus der Aussage, dass eine typische Folge ein Verhältnis von gerade zu ungerade von 2:1 hat, daraus abzuleiten, dass das für jede Folge gilt.

[snafu]

Interessant bei den kleineren Zahlen ist die 27, die 111(!) Schritte braucht. Das wird auch im verlinken Video erwähnt. Daran zeigt sich, dass es immer wieder komische Ausreißer dazwischen gibt und man somit eben nicht einfach mit Abschätzungen arbeiten kann.

[snafu]

Auch interessant wie sich der hintere Teil von großen Zahlen teilweise selbst in einem Zyklus befindet:

Code: Alles auswählen

Start: 10485760000000001
Steps: 343
First 20:
  10_485_760_000_000_001 <-- 
  31_457_280_000_000_004
  15_728_640_000_000_002
   7_864_320_000_000_001
  23_592_960_000_000_004
  11_796_480_000_000_002
   5_898_240_000_000_001
  17_694_720_000_000_004
   8_847_360_000_000_002
   4_423_680_000_000_001
  13_271_040_000_000_004
   6_635_520_000_000_002
   3_317_760_000_000_001 <--
   9_953_280_000_000_004
   4_976_640_000_000_002
   2_488_320_000_000_001
   7_464_960_000_000_004
   3_732_480_000_000_002
   1_866_240_000_000_001
   5_598_720_000_000_004

Code: Alles auswählen

from collections import deque
from itertools import chain, islice

def generate_collatz_numbers(n):
    if n < 1:
        raise ValueError(f"n must be >= 1, got: {n}")
    while n > 1:
        if n % 2:
            yield (n := 3 * n + 1)
        yield (n := n // 2)

def count_collatz_steps(start):
    return sum(1 for _ in generate_collatz_numbers(start))

def get_collatz_sequence(start, window_size=None):
    numbers = chain([start], generate_collatz_numbers(start))
    if window_size is None:
        return numbers
    elif window_size >= 0:
        return islice(numbers, window_size)
    else:
        return deque(numbers, -window_size)

def get_formatted_sequence(start, window_size=None):
    seq = get_collatz_sequence(start, window_size)
    length = len(format(start, "_")) + 2
    return map(f"{{:{length}_}}".format, seq)

def main():
    start = 40**10 + 1
    print("Start:", start)
    print("Steps:", count_collatz_steps(start))
    print("First 20:")
    print(*get_formatted_sequence(start, 20), sep="\n")

if __name__ == "__main__":
    main()

[snafu]

Das ist wirklich witzig, dass innerhalb der markieren Zyklen nochmals innere Zyklen sind:
- 4x Zyklus der letzten Ziffer (1, 4, 2, 1, 4, 2, ...) <-- das schon bekannte Muster 4, 2, 1
- 3x Zyklus von 60, 80, 40, 20 <-- Verhältnis: 4:2:1:3

Also wenn man sich für Zahlentheorie interessiert, ist das schon interessant mit gewissen Startwerten. Das hat etwas rhythmisches an sich. Auf dem 12ten Takt treffen sich die Zyklen wieder.