Nur wo Mathematik drauf steht ist auch Mathematik drinnen ... War: Algorithmus gesucht

29/03/2008 - 00:00 von Siegfried Neubert | Report spam
XPost und Fup2 de.sci.mathematik (oder so àhnlich!)





Hallo Ihr, moin moin!



Ich stelle diesen Text noch mal ein,

weil es mir sehr viel Spaß gemacht hat nach langer Zeit mal wieder
(darüber) nachzudenken

- ggf. geht's Euch beim Ansehen ja auch so. Und, Hero bitte nicht
aufregen,

die Zitate sind bitte eher chronologische Zusammenstellung, keine
"Treaddokumentation".



"Joachim Mohr" schrieb im Newsbeitrag
news:fsdku6$bdd$02$1@news.t-online.com...

...


"Jens Mander" schrieb im Newsbeitrag
news:fsdhnt$ggh$01$1@news.t-online.com...



...


Hallo!



Ich habe die Reihe der natürlichen Zahlen von 1 bis 101. Nun suche
ich

die beiden Reihen von links und von rechts, die summiert den gleichen

Wert ergeben. In diesem Beispiel wàren das die Reihen



1..24 von links und Summe k(k+1)/2

101..99 von rechts Summe n*(n+1)/2 - (i-1)*i/2



Beides ergibt 300.

Frage: Gibt es eine Möglichkeit, zu einer beliebigen Reihe 1..x

irgendeine solcher Lösungen (es kann ja mehrere geben) schneller zu

finden, als durch ausprobieren?





Du suchst also einen Algorithmus, um die Gleichung

k(k+1)/2 = n*(n+1)/2 - (i-1)*i/2 oder einfacher

k*(k+1) + (i-1)*i = n*(n+1) ganzzahlig zu lösen.

Für 1<=k<=n muss man dann eine quadratische Gleichung lösen:

Für n1 erhàlt man die Lösungen

(k, i) = (24, 99), (39, 94), (60, 82), (81, 61), (93, 40), (98, 25),
(101, 1)



Aufgabe: Löse für alle k,i e IN die Gleichungen

k*(k+1) + (i-1)*i = n*(n+1) also i^2-i + k^2 + k - n^2-n = 0

Lösung: i1,2=1/2 +- sqrt(1/4-k^2-k+n^2+n)

Die negative Lösung entfàllt schon mal.



Algorithmus bei festem n: Für k = 1 bis n löse:

i = 1/2+(sqrt(1/4-k(k+1)+n(n+1) . Wenn i e IN, dann Lösung (k,i)



MFG Joachim





Dann mein erster und zweiter Versuch:



2) "Siegfried Neubert" schrieb im Newsbeitrag
news:651scaF2eiti1U1@mid.dfncis.de...

.




Und nochmal moin, moin!



Wo Mathematik drauf steht, ist auch Mathematik drin! Siehe Ergànzung
unten!





1) "Siegfried Neubert" schrieb im Newsbeitrag
news:651a8bF2di6bdU1@mid.dfncis.de...



.





Hi und moin, moin Ihr!





[ geskippte Beitràge (siehe oben von Joachim Mohr und Jens Mander ]

.




Man braucht erst "von unten" mit [sqrt(2n)]. (Gaußklammer)
beginnen.

Hier also [sqrt(202)]. = 14, weil

1+2++13 = 13*14/2 = 13*7 = 91 < 101 aber

1+2+...+13+14 = 91+14 = 105 > 101



Und hat man eine Lösung (K,I) für ein

k= sqrt(202)].-1, sqrt(202)]., sqrt(202)].+1, ..., K, ... < n

gefunden, dann ist für (k=I-1,i=K+1)

wg. der "Symmetrie" auch eine Lösung

und es sollte I-1 >= K+1 gelten

(sonst hatte man diese Lösung schon und war fertig!)



Gezielt braucht man nur bis k= Kmax = [ n/Sqrt(2) ]. suchen.

Hier, Kmax= [ 101/1,4142... ]. = 71.

Insgesamt also für n= 101, k= 14, ..., 71 , d.h. für 58 k-Werte




Und die Lösung (n,1) trivial ist.



Aber ich bleibe dran,

ich habe Hoffnung es wird noch besser.





Es gibt da noch eine mathematische Erungenschaft,

die nennt sich Quadratische Reste:

http://de.wikipedia.org/wiki/Quadratischer_Rest



Zum Bleistift kann eine Zahl x, x e IN , nur dann ein Quadradt einer

Ganzzahl sein, wenn

x mod 3 ungleich 2 ist oder

x mod 5 ungleich 2 oder 3 ist oder

x mod 7 ungleich 3 od. 5 od. 6 ist ...

...

Nun, ich behaupte der Ausdruck 4(n+k+1)(n-k)+1

korrespondiert zur Fragestellung oben,

und da n und k variabel sein sollen, verallgemeinert er die originàre

Fragestellung.





Entweder ich wollte Euch ràtseln lassen, ;o)

- Pardon -

oder ich vergaß in meiner Begeisterung mit aufzuschreiben:



k(k+1) = n(n+1) -i(i-1)

i(i-1) = n^2-k^2 +n-k = (n-k)(n+k+1)

4i(i-1) +1 = (2i-1)^2 = 4(n-k)(n+k+1)+1




Berechnet man nun für n variabel aber jetzt fest gewàhlt, z.B. n1

und k=1,2,3 (danach wiederholen sich die Ergebnisse periodisch)

(4(n+k+1)(n-k)+1) mod 3, erhàlt man der Reihe nach

2, 1, 1, ...

Die 2 ist aber kein sog. Quadratischer Rest (QR) mod 3, also kann

k= 1,4,7,10, ... keine Lösung sein.





Betrachtet man nun (4(n+k+1)(n-k)+1) mod 5

weiter für k= 2,3,5,6,8,9,...

erhàlt man (wieder Periodisch) für k=1,2,3,4,5, ...

(1), 0, 1, (4), 4, 1, (0), 1, 4, (4), 1, 0, (1), 4, 4, ...



Leider sind das alles QRs.

Aber mod 7 liefert für k=1,2,3,4,5,6,7, ...

(6),4,1,(4),6,0,(0),6,4,(1),4,6,(0),0,6,(4),1,4,(6),0,0, ...



Die eingeklammerten Werte für k=1,4,7,10, ...

fallen ja schon mod 3 heraus.

Und nun noch alle mit 4, da 4 kein QR mod 7 ist, also verbleiben

-,-,1,-,6,0,-,6,-,-,-,6,-,0,6,-,1,4,-,0,0, ...

und das wieder periodisch!



D.H. nur die Werte k=3,5,6,8,12,14,15,17,18,20,21, ...

bzw. allg. (mit dem Ergebnis oben für die Grenzen von k ) alle Werte

[sqrt(202)]. -1 < K= 21m+k < [ n/Sqrt(2) ].

mit m e IN und k e { 3,5,6,8,12,14,15,17,18,20,21 }

müßte man weiter betrachten.



Weitere Einschrànkungen erhàlt man (z.B.) mod 11, mod 13 etc.

Mit jedem mod p, p prim, etwa die hàlfte weniger

(aber Achtung, siehe hier mod 5).

So hat man jedoch schon "nur noch" für ca. 30 Werte die Wurzel zu
ziehen,

statt für 101, und kann das bel. weiter eingrenzen!



Nochmal Gruß



Siggi N. - Hamburg



.



P.S.: Noch einfacher - mit geringerem Aufwand - scheints mir (nun),

k von oben nach unten laufen zu lassen.

Soll heißen: k= n-1, n-2, ... , [ n/Sqrt(2) ].-1,

dann hàtte man mod 3 und mod 7 nur ca. 15 Wurzeln zu ziehen

(oder eben entsprechend/bel. weniger mit mod 11, mod 13, ... )..



Aber, mit einem kleinen Programm, dass ggf. schneller (sicher schneller
zu schreiben)

ist als alles oben gesagt, ganz sicher aber unkomplizierter - es lebe
der Praktiker -,

macht dann das Spielen mit N richtig Spaß, zur Nachahmung empfohlen!



n= < N >: sk= k= 1: si= i= n

While n > k Do

If sk < si Then k= k+1: sk= sk+k

ElseIf sk = si Then Print sk, k, i

k= k+1: sk= sk+k: i= i-1: si= si+i

Else i= i-1: si= si+i

Wend





Ich erbitte ggf. Kommentare/Anregungen/Kritik



Mit freundlichen Grüßen, tschüß



Siggi N. - Hamburg
 

Lesen sie die antworten

#1 Jens Mander
29/03/2008 - 22:57 | Warnen spam
Wow, das sieht ja wirklich alles sehr interessant aus! Ich freue mich, dass
meine Frage so viel Engagement ausgelöst hat. :-)

Viele Grüße
Jens

Ähnliche fragen