001 – Addition der Vielfachen von 3 oder 5

 

Wenn wir alle natürlichen Zahlen unter 10, die durch 3 oder 5 teilbar sind, auflisten, erhalten wir:

3, 5, 6, 9

Die Summe daraus ist 23.

Finde die Summe aller Vielfachen von 3 oder 5 unter 1000!

Lösung

Möglichkeit 1

In einer Schleife wird eine Variable bis 999 hochgezählt. Bei jedem Durchlauf wird geprüft, ob der aktuelle Wert durch 3 oder durch 5 geteilt werden kann. Ist dies der Fall, wird der aktuelle Wert auf die Summe addiert:

summe = 0;

for i = 1:999
    if (mod(i, 3) == 0) || (mod(i,5) == 0)
        summe = summe + i;
    end
end

summe

Das Ergebnis ist 233168.

Hätten wir die Zahlen statt bis 1000 bis 100000000 aufaddieren sollen, hätte sich dies in der Rechenzeit bemerkbar gemacht.

Rechenzeit von Möglichkeit 1 für n = 100000000: 13.765252 Sekunden

Möglichkeit 2

Alle Vielfachen von 3 unter 1000 werden summiert. Alle Vielfachen von 5 unter 1000 werden summiert. Die beiden Summen werden addiert. Da die Zahlen, die durch 15 teilbar sind, doppelt gezählt wurden, werden diese wieder abgezogen:

summe = 0;

for i = 3:3:999
    summe = summe + i;
end

for i = 5:5:999
    summe = summe + i;
end

for i = 15:15:999
    summe = summe - i;
end

summe

Rechenzeit von Möglichkeit 2 für n = 100000000: 0.265250 Sekunden

Möglichkeit 3

Die dritte Möglichkeit besteht darin, erst einmal über das Problem nachzudenken, und dann mit dem Programmieren anzufangen. Wir schreiben den Ansatz von Möglichkeit 2 ein wenig um (Grenze 999 wurde zu g verallgemeinert):

x = \sum\limits_{i = 3,i+ = 3}^g i +\sum\limits_{i = 5,i+ = 5}^g i -\sum\limits_{i = 15,i+ = 15}^g i

Wir benutzen nun das Zeichen \div für die ganzzahlige Division:

x = \sum\limits_{i = 1}^{g \div 3} {3i} +\sum\limits_{i = 1}^{g \div 5} {5i} -\sum\limits_{i = 1}^{g \div 15} {15i}

Die Konstanten können wir vor die Summen ziehen:

x = 3\sum\limits_{i = 1}^{g \div 3} i +5\sum\limits_{i = 1}^{g \div 5} i -15\sum\limits_{i = 1}^{g \div 15} i

Nun benutzen wir die Summenformel von Gauß:

\sum\limits_{i = 1}^n i  = \frac{{n\left( {n+1} \right)}} {2}

\Rightarrow \quad x = 3\frac{{\left( {g \div 3} \right)\left( {\left[ {g \div 3} \right]+1} \right)}} {2}+5\frac{{\left( {g \div 5} \right)\left( {\left[ {g \div 5} \right]+1} \right)}} {2}-15\frac{{\left( {g \div 15} \right)\left( {\left[ {g \div 15} \right]+1} \right)}} {2}

Matlab-Code:

g = 999;

summe3 = 3 * 0.5 * floor(g/3) * (floor(g/3) + 1)
summe5 = 5 * 0.5 * floor(g/5) * (floor(g/5) + 1)
summe15 = 15 * 0.5 * floor(g/15) * (floor(g/15) + 1)

summe = summe3 + summe5 - summe15

Rechenzeit von Möglichkeit 3 für n = 100000000: 0.000448 Sekunden

Ähnliche Artikel

2 Kommentare zu “001 – Addition der Vielfachen von 3 oder 5”

Finde die Summe aller Vielfachen von 3 oder 5 unter 1000!

266333 ist die richtige Lösung!

Ich bin ziemlich sicher, dass mein Ergebnis stimmt… Zudem haben zehntausende Leute bei project euler das gleiche rausbekommen. Welchen Rechenweg hast du benutzt?

Kommentar verfassen