014 – Collatz-Problem und Zahlenfolgen

 

Das Collatz-Problem, auch als (3n + 1)-Vermutung oder Syracuse-Algorithmus bezeichnet, ist ein ungelöstes mathematisches Problem, das 1937 von Lothar Collatz entdeckt wurde. Bei dem Problem geht es um Zahlenfolgen, die nach einem einfachen Bildungsgesetz konstruiert werden:

Beginne mit einer natürlichen Zahl n. Ist n gerade, so nimm als nächstes n / 2. Ist n ungerade, so nimm als nächstes 3n + 1.

Erstaunlicherweise endete die Folge bisher immer mit …, 4, 2, 1 – egal welche Startzahl man probiert hat. Die Collatz-Vermutung lautet: Jede so konstruierte Zahlenfolge endet im Zykel 4,2,1 egal, mit welcher natürlichen Zahl man beginnt.

Beispiel: n = 13

Es resultiert die Folge: 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Wenn wir mit 13 anfangen, erhalten wir eine Folge mit 10 Gliedern. Aus welcher Startzahl n unter einer Millionen folgt die längste Collatz-Kette?

Lösung

Es werden alle Zahlen von 1 bis 1000000 auf die Länge ihrer Collatz-Kette geprüft:

max = [1 1];

for it = 1 : 1000000
    coll = it;
    count = 1;
    while coll ~= 1
        if mod(coll, 2) == 0
            coll = coll / 2;
        else
            coll = coll * 3 + 1;
        end
        count = count + 1;
    end
    if count > max(1)
        max(1) = count;
        max(2) = it;
    end
end

max

Ergebnis: Länge 525 für n = 837799
Rechenzeit: 11.141164 Sekunden

Verbesserungen

Wir müssen die Zahlen u von 1 bis 500000 nicht testen, da es jeweils ein n=2u gibt, das zu der gleichen Kette führt, nur mit einem zusätzlichen Glied vorweg.

Verbesserter Algorithmus:

max = [1 1];

for it = 500001 : 1000000
    coll = it;
    count = 1;
    while coll ~= 1
        if mod(coll, 2) == 0
            coll = coll / 2;
        else
            coll = coll * 3 + 1;
        end
        count = count + 1;
    end
    if count > max(1)
        max(1) = count;
        max(2) = it;
    end
end

max

Rechenzeit: 5.048625 Sekunden

Ähnliche Artikel

2 Kommentare zu “014 – Collatz-Problem und Zahlenfolgen”

Christian Bachmann

Hallo,
meiner Meinung nach kann nicht auf die Suche in den geraden Zahlen in der oberen Hälfte verzichtet werden, da eventuell eine ungerade Zahl in der unteren Hälfte eine längere Folge verursacht. Deshalb ist der zweie Absatz in den Verbesserungen irreführend.
Christian

Stimmt, es werden nicht alle geraden Zahlen der oberen Hälfte in einem Schritt von einer Zahl aus der unteren Hälfte erreicht. Vielleicht kann man irgendwie zeigen, dass sie über mehr Schritte erreicht werden, aber ich habe den Satz mal lieber rausgenommen.

Kommentar verfassen