Summe berechnen ggT. ausrechnen

Question

Ich wollt wissen, wie man hier die Summe berechnet.

Answer 1

Hallo BI, 

die Primfaktorzerlegung von  75  ist  3 * 5²

Wegen ggT(i,75)=1 dürfen die PFZ der Summanden i also keine 3 und keine 5 enthalten.

i darf also weder durch 3 noch durch 5 teilbar sein:

Summe  = 1+2+4+7+8+11+13+14+16+17+19+22+23+26+28+29+31+32+34+37+38+41+43+44+

                         +46+47+49+52+53+56+58+59+61+62+64+67+68+71+73+74  = 1500 

vielleicht fällt ja jemandem noch etwas Eleganteres ein :-)

-------------

Nachtrag (vgl. Kommentare):   [ für n >> 75  unverzichtbar :-) ] 

Es gilt die Summenformel:  \(\sum\limits_{i=1}^{n} i\) = n/2 * (n+1)

Die gesuchte Summe kann man schreiben als 

\(\sum\limits_{i=1}^{75} i\)  -  3 * \(\sum\limits_{i=1}^{25} i\)  -  5 * \(\sum\limits_{k=1}^{15} i\) + 15 * \(\sum\limits_{i=1}^{5} i\)  und dann jeweils die Summenformel anwenden.

Summe der Zahlen von 1 - 75 

Summe der 25 durch 3 teilbaren Zahlen von 1 - 75        [ 75/3 = 25 ]

Summe der 15 durch 5 teilbaren Zahlen von 1 - 75        [ 75/5 = 15 ] 

Summe der 5 durch 3 und 5 (und damit durch 15)  teilbaren Zahlen von 1 - 75  [ 75/15 = 5 ] 

Letztere muss addiert werden, weil man sie zuvor zweimal subtrahiert hat. 

Ich hoffe, diese Kurzfassung der Erklärung genügt zum Verständnis

Gruß Wolfgang

Comments

Wie wäre es mit

( (75+1)*75 - 3*(25+1)*25 - 5*(15+1)*15 + 15*(5+1)*5 ) / 2

?

---

Diese Anwendung der Summenformel \(\sum\limits_{i=1}^{n} i\) = n/2 *(n+1) habe ich natürlich auch überlegt :-)

Hatte dann aber Zweifel, ob das (Zerlegung und Bestimmung der oberen Grenzen für die Einzelsummen) leichter verständlich erklärbar ist.

Immerhin hast du das ja auch nicht versucht :-)

---

Also ich bin aufgrund deiner Bemerkung

"Wegen ggT(i,75)=1 dürfen die PFZ der Summanden i also keine 3 und keine 5 enthalten. i darf also weder durch 3 noch durch 5 teilbar sein:"

draufgekommen.

---

Habe das mit Kurzfassung der Erklärung nachgetragen.

Meine hier im Forum oft geschmähten Farben könnten beim Verständnis viele Worte ersparen.

---

"vielleicht fällt ja jemandem noch etwas Eleganteres ein :-)"

Nun, an weiteren Einfällen soll es nicht mangeln:

Summe = ( (1+74) + (2+73) + (4+71) + (7+68) + ... + (68+7) + (71+4) + (73+2) + (74+1) ) / 2 = 75 * 40 / 2 = 1500.

(Das ist "der kleine Gauß", diesmal nicht auf eine erithmetische Reihe angewendet, sondern auf die zu 75 teilerfremden Zahlen von 1 bis 75.)

Answer 2

(1+2+4+7+8+11+13+14)*(1+3+5+7+9)
= 60*25
= 1500

ist eigentlich auch ein schöner Ansatz.

Comments

So, wie gesehen gibt es also viele Möglichkeiten, das vorgelegte Problem mit erträglichem Aufwand in Handarbeit zu lösen. Allgemein gilt die Beziehung:

$$ \mathop{\sum i}_{\substack{1 \le i \le n \\ \text{ggT}(i,n)=1}\:\:} = \dfrac {n\cdot \varphi(n) } 2 $$Diese Formel lässt sich vermutlich leicht begründen und zur Bestimmung der Werte der Funktion \(\varphi\) gibt es Rechenregeln. Für das Beispiel ergibt sich:

$$ \mathop{\sum i}_{\substack{1 \le i \le 75 \\ \text{ggT}(i,75)=1}\:\:} = \dfrac {75\cdot 40 } 2 = 1500.$$