Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Rest einer Summe
Autor
Schule Rest einer Summe
sebast2004
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 06.07.2022
Mitteilungen: 4
  Themenstart: 2022-07-06

Hallo, ich habe zu folgender Aufgabe eine FRage: Auf einer Tafel stehen die Zahlen 1, 2, ..., 2012. Jede Minute geht ein Schüler zur Tafel, wählt zwei Zahlen x und y, löscht sie und schreibt die Zahl 2x + 2y an die Tafel. Dies wird fortgesetzt, bis nur noch eine Zahl N übrig bleibt. Finden Sie den Rest, wenn der maximal mögliche Wert von N durch 1000 geteilt wird (OMU2012). Ich habe als Beispiel mal die FOlge 1, 2, 3,4, 5 betrachtet. Man muss immer die zwei größten Zahlen streichen, damit N möglichst groß wird. 1 2 3 4 5 -> 1 2 3 18 1 2 3 18 -> 1 2 42 1 2 42 -> 1 88 1 88 -> 178 Für die SUmmen habe ich gerechnet: (5+4)*2 = 18 (18+3)*2 = ((5+4)*2+3)*2)=42 (42+2)*2 = (((5+4)*2+3)*2)+2)*2)=88 (88+1)*2= ((((5+4)*2+3)*2)+2)*2)+1)*2=178 Dann hätte ich für N die SUmme: 5*2^(5-1)+4*2^(5-1)+3*2^(5-2)+2*2^(5-3)+1*2^(5-4)=178 Ist meine überlegugn für die FOlge 1, 2, ..., 2012 dann so richtig: N=2012*2^(2012-1)+2011*2^(2012-1)+2010*2^(2012-2)+...+1*2^(2012-2011) ?? Wie kann man zeigen, dass diese Formel dann für die Zahlen bis 2012 richtig wäre (falls meine Gedanken richtig waren)? Wie kann ich die Summe dann berechnen? Die gauß-Formel kenne ich. Und die Summe hätte ich so mit dem Summenzeichen geschrieben: N=2012*2^2011+sum(i*2^i,i=1,2011)=?? Im Summensymbol kommt i in beiden Faktoren vor. Hier kenne ich noch keine Formel. Würde mich sehr über eine Hilfe freuen. DAnke!!!


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2532
  Beitrag No.1, eingetragen 2022-07-06

Es bietet sich häufig an, OEIS zu benutzen, wenn man etwas über Zahlenfolgen wissen will. Hier liefert diese Suche eine Formel a(n) für die Summen, bei denen der Index bis n läuft. (Und die Summe hier ist a(2011).)


   Profil
sebast2004
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 06.07.2022
Mitteilungen: 4
  Beitrag No.2, vom Themenstarter, eingetragen 2022-07-07

Dass es so eine Suche nach Folgen gibt, wusste ich bis jetzt noch nicht. Wie kann man die Summenformel beweisen? Und ist mein Term für N richtig? Von N muss ich dann nur noch den rest bei der Division durch 1000 feststellen.


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2532
  Beitrag No.3, eingetragen 2022-07-07

\quoteon(2022-07-07 07:10 - sebast2004 in Beitrag No. 2) Dass es so eine Suche nach Folgen gibt, wusste ich bis jetzt noch nicht. Wie kann man die Summenformel beweisen? \quoteoff Das naheliegendste ist Induktion. \quoteon Und ist mein Term für N richtig? \quoteoff Scheint so. \quoteon Von N muss ich dann nur noch den rest bei der Division durch 1000 feststellen. \quoteoff Jop.


   Profil
sebast2004
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 06.07.2022
Mitteilungen: 4
  Beitrag No.4, vom Themenstarter, eingetragen 2022-07-07

Danke. Induktion habe ich: n=1: … n nach n+1: sum(i*2^i,i=1,n+1)= sum(i*2^i, i=1, n) + (n+1)*2^(n+1)= 2+2^(n-1)+(n+1)*2^(n+1)= usw. =2+2^(n+2)*n Ich komme dann für meinen obigen Term auf N=2^2016. Wegen dem Rest komme ich nur mit vielen Zwischenschritten aufbringen Ergebnis. Ist das richtig und gibt es einen „schnelleren“ Weg? 2^2016 == (2^30)^60 *2^216 == (824)^60*(2^20)^10*2^16 ==( (824)^3)^20*(576)^10*576==(224)^20*(576^2)^5*536==(224^2)^10*(776)^5*536==(176)^10*(776)^2*(776)^2*776*536==(176)^4*(176)^4*(176)^2*176*176*776*536==(176)^4*(176)^4*(176)^4*776*536==576*576*576*776*536==(576)^2*576*776*536==776*576*776*536==(776)^2*576*536==176*576*536== 536 Modulo 1000 Vielen Dank


   Profil
Wauzi
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.06.2004
Mitteilungen: 11536
Wohnort: Bayern
  Beitrag No.5, eingetragen 2022-07-07

Hallo, S(N)=sum(i*2^i,i=0,N)=sum((i-1)*2^(i-1),i=1,N+1) | | Indexverschiebung =sum(i*2^(i-1),i=1,N+1)-sum(2^(i-1),i=1,N+1)= =1/2*sum(i*2^i,i=1,N+1)-sum(2^i,i=0,N)= =1/2*sum(i*2^i,i=0,N+1)-sum(2^i,i=0,N)= \ Summand mit i=0 dazu, ändert nichts =1/2*sum(i*2^i,i=0,N)+1/2*(N+1)*2^(N+1)-sum(2^i,i=0,N)= =1/2*S(N)+1/2*(N+1)*2^(N+1)-sum(2^i,i=0,N) Die rechte Summe ist die bekannte geometrische Summe. Auflösen der Gleichung nach S(N) bringt die gesuchte Formel Dies geht mit anderen Methoden einfacher, aber nicht so elementar. Gruß Wauzi


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2427
  Beitrag No.6, eingetragen 2022-07-07

Huhu sebast2004, \quoteon(2022-07-07 11:52 - sebast2004 in Beitrag No. 4) Ist das richtig und gibt es einen „schnelleren“ Weg? \quoteoff das liegt ja auch etwas an deinem Kenntnisstand. Kennst du z. B. den chinesischen Restsatz und die Eulersche Phi-Funktion? Es ist offensichtlich \(2^{2016}\equiv 0 \pmod{8}\) und mit \(\phi(125)=\phi(5^3)=5^2(5-1)=100\) folgt dann \(2^{100}\equiv 1\pmod{125}\) und somit \(2^{2016}\equiv 2^{16}=2^7\cdot 2^7\cdot 2^2 \equiv 3\cdot 3\cdot 4 \equiv 36\pmod{125}\). Es gilt dann also ein \(x\) zu finden, für das \(36+125x\equiv 0\pmod{8}\) ist. Nun ist \(36+125x\equiv 4+5x\) und somit tut es \(x=4\). Setzen wir es ein erhalten wir \(36+125\cdot 4=536\). Dein Ergebnis scheint also zu stimmen. Gruß, Küstenkind


   Profil
sebast2004
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 06.07.2022
Mitteilungen: 4
  Beitrag No.7, vom Themenstarter, eingetragen 2022-07-07

Hallo Wautzi, deine Herleitung für die Formel zur Berechnung der SUmme habe ich nicht verstanden. Auch die geometrische Summe sehe ich nicht. Ich kenne nur: sum(q^k,k=0,\inf)=1/(1-q) und die Formel von Gauß sowie für Quadrat- und Kubikzahlen.


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
Wauzi
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.06.2004
Mitteilungen: 11536
Wohnort: Bayern
  Beitrag No.8, eingetragen 2022-07-07

Hallo, die endliche Summe ergibt sich so: sum(q^k,k=0,N)=sum(q^k,k=0,\inf )-sum(q^k,k=N+1,\inf )= =1/(1-q)-q^(N+1)*sum(q^k,k=0,\inf )= =1/(1-q)-q^(N+1)*1/(1-q)=(1-q^(N+1))/(1-q) Die anderen Probleme müßtest Du konkretisieren. Gruß Wauzi


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]