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 von 1 bis 500000 nicht testen, da es jeweils ein 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