021 – Befreundete Zahlen unter 10000

 

Sei d\left(n\right) definiert als die Summe der echten Teiler von n (Zahlen kleiner als n, durch die n ohne Rest teilbar ist).

Wenn d\left(a\right)=b und d\left(b\right)=a gilt mit a \ne b, dann sind a und b ein Paar befreundeter Zahlen und a und b werden befreundete Zahlen genannt.

Beispiel:

Die echten Teiler von 220 sind 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 und 110.

Es ist also d\left(220\right)=284

Die echten Teiler von 284 sind 1, 2, 4, 71 und 142.

Es ist also d\left(284\right)=220

Finde die Summe aller befreundeten Zahlen unter 10000!

Lösung

In einer Schleife werden alle Zahlen von 1 bis 10000 mit der Summe der Teiler der Summe der Teiler von sich selbst verglichen. Wenn diese gleich sind, muss noch ausgeschlossen werden, dass es sich um eine vollkommene Zahl handelt. Eine natürliche Zahl wird vollkommene Zahl (auch perfekte Zahl) genannt, wenn sie genauso groß ist wie die Summe ihrer positiven echten Teiler.

Um die Teiler herauszufinden, implementieren wir eine eigene kleine Funktion.

Matlab-Code:

function  euler021

    clear;
    tic

    amicable = 0;
    for i = 1 : 10000
        if i == divSum(divSum(i)) && i ~= divSum(i)
            amicable = [amicable i];
        end
    end

    sum(amicable)
    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: 31626
Rechenzeit: 4.948899 Sekunden