016 – Quersumme von 2^1000

 

Es ist 215 = 32768 und die Quersumme ist 3+2+7+6+8 = 26.

Was ist die Quersumme von 21000?

Lösung

Da Matlab nicht von sich aus ausreichend genau mit so großen Zahlen zurechtkommt, müssen wir uns selber eine “Zahl” programmieren.

Idee:

Statt einer Zahl benutzen wir einen Vektor vec, dessen Elemente vec(i) für die Ziffern stehen. Wir brauchen 302 Ziffern (Länge des Vektors). Im ersten Schritt setzen wir die erste Stelle von vec auf 1. Dann beginnen wir eine Schleife, in der in jedem Schritt der gesamte Vektor mit 2 multipliziert wird. Wird dabei eine der “Ziffern” größer als 10, muss eine 1 übertragen werden zur nächsten Ziffer.

Beispiel mit kürzerem Vektor:

Start:

vec = 1, 0, 0, 0

Multiplikation mit 2:

vec = 2, 0, 0, 0

keine Ziffer ist größer als 10. Multiplikation mit 2:

vec = 4, 0, 0, 0

keine Ziffer ist größer als 10. Multiplikation mit 2:

vec = 8, 0, 0, 0

keine Ziffer ist größer als 10. Multiplikation mit 2:

vec = 16, 0, 0, 0

erste Ziffer ist größer als 10, daher Übertrag:

vec = 6, 1, 0, 0

Multiplikation mit 2:

vec = 12, 2, 0, 0

erste Ziffer ist größer als 10, daher Übertrag:

vec = 2, 3, 0, 0

Der aktuelle Vektor stellt also die Zahl 32 dar. Die Multiplikation mit 2 führen wir 1000 mal durch. Anschließend summieren wir die Vektorelemente auf.

Matlab-Code:

vec = zeros(1,302);
vec(1) = 1;

for i = 1 : 1000
    vec = vec .* 2;
    for j = 1 : 301
        if vec(j) >= 10
            vec(j) = vec(j) - 10;
            vec(j + 1) = vec(j + 1) + 1;
        end
    end
end

summe = 0;
for j = 1 : 302
    summe = summe + vec(j);
end

summe

Ergebnis: 1366
Rechenzeit: 0.004519 Sekunden