023 – Summe von zwei abundanten Zahlen

 

Eine natürliche Zahl wird vollkommene Zahl genannt, wenn sie genauso groß ist wie die Summe ihrer positiven echten Teiler (also aller Teiler außer sich selbst). Zum Beispiel ist die Summe der echten Teiler von 28: 1+2+4+7+14=28, also ist 28 eine vollkommene Zahl.

Ist diese Summe der Teiler kleiner als die Zahl selbst, heißt die Zahl defizient. Ist die Teilersumme dagegen größer, so spricht man von einer abundanten Zahl.

Da 12 die kleinste abundante Zahl ist, ist die kleinste Zahl, die als Summe von zwei abundanten Zahlen geschrieben werden kann, 24. Mit mathematischer Analysis kann gezeigt werden, dass alle natürlichen Zahlen, die größer als 28123 sind, als Summe von zwei abundanten Zahlen geschrieben werden können. Dieses obere Limit kann nicht weiter gedrückt werden, obwohl bekannt ist, dass die größte Zahl, die nicht als Summe von zwei abundanten Zahlen ausgedrückt werden kann, sehr viel kleiner ist (kleiner als 21000).

Finde die Summe aller positiven natürlichen Zahlen, die nicht als Summe zweier abundanten Zahlen ausgedrückt werden können.

Lösung

Hier könnte man zu einem Brute-Force Ansatz greifen, indem man alle abundanten Zahlen von 1 bis 21000 bestimmt, alle Kombinationen aus diesen bildet, die doppelten Kombinationen löscht, den Vektor sortiert und prüft, welche Zahlen nicht darin enthalten sind. Dies sind die Zahlen, die nicht als Summe von zwei abundanten Zahlen geschrieben werden können.

Da aber ungefähr jede dritte Zahl abundant ist, gibt es zwischen 1 und 21000 ca. 7000 abundante Zahlen, also 49000000 Kombinationen. Diese zu berechnen dauert relativ lange.

Statt dessen können wir von jeder betrachteten Zahl in einer Schleife die abundanten Zahlen abziehen und prüfen, ob bei der Subtraktion wieder eine abundante Zahl herauskommt. In diesem Fall kann die Zahl als Summe von zwei abundanten Zahlen ausgedrückt werden und wir können mit der nächsten Zahl weitermachen. So sparen wir sehr viel Rechenzeit, da die Schleifen vorzeitig mit break verlassen werden können.

Matlab-Code:

function  euler023

    clear
    tic

    target = 21000;

    abundant = 0;
    for i = 1 : target
        if i < divSum(i)
            abundant = [abundant i];
        end
    end
    abundant = abundant(2 : length(abundant));
    toc

    tic
    notPossible = 0;
    for i = 1 : target
        possible = 0;
        for a = 1 : length(abundant)
            comp = i - abundant(a);
            if comp <= 0
                break
            end
            if find(abundant == comp) ~= 0
                possible = 1;
                break
            end
        end
        if possible == 0
            notPossible = [notPossible i];
        end
    end
    sum(notPossible)
    toc
end

function d = divisors(z)

    d = 1;
    for i = 2 : z / 2
        if mod(z, i) == 0
            d = [d i];
        end
    end
end

function s = divSum(z)

    s = sum(divisors(z));
end

Ergebnis: 4179871
Rechenzeit: 49.913802 Sekunden

Es gibt elegantere Lösungen für diese Aufgabe!

Ähnliche Artikel

Kommentar verfassen