uebung4

Aus ProgrammingWiki

Herleitung der Funktionen für $x$ und $y$ aus $z = (x; y)$

$z =\left(\frac{(x+y)(x+y+1)}{2} \right) +y = t + y; w = x + y; x,y,z \in \N, w,t \in \R_{0}^{+}$

$t = z - y = \frac{w(w+1)}{2} = \frac{w^{2}+w}{2} $

Die Lösung von $w^{2} + w + 2t = 0$

für positives $w$ ist $w = \frac{\sqrt{8t+1}-1}{2}$ Außerdem gilt $t \leq z = t + w - x \leq t + w \leq t + w + 1 = \frac{w^{2}+w}{2} + w + 1 = \frac{(w+1)^{2} + (w+1)}{2}$

Unter verwendung von $z \leq \frac{(w+1)^{2} + (w+1)}{2}$ können wir $w$ nach oben abschätzen.

$w = \frac{\sqrt{8t+1}-1}{2} < \frac{\sqrt{8z+1}-1}{2}< w+1 $

Um die beiden natürlichen Zahlen x und y aus z zu gewinnen, ist als erstes $w = \lfloor \frac{\sqrt{8z+1}-1}{2} \rfloor $ zu berechnen. Dann ergeben sich

$t = \frac{w(w+1}{2}$ und $y = z -t$ sowie $x = w - y$