From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 math/math.tex | 890 ++++++++++++++++++++++++++--------------------------------
 1 file changed, 398 insertions(+), 492 deletions(-)

(limited to 'math/math.tex')

diff --git a/math/math.tex b/math/math.tex
index 1f372e5..4545927 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -1,58 +1,187 @@
 \section{Mathe}
 
-\subsection{ggT, kgV, erweiterter euklidischer Algorithmus}
-\lstinputlisting{math/gcd-lcm.cpp}
-\lstinputlisting{math/extendedEuclid.cpp}
+\begin{algorithm}{Zykel Erkennung}
+	\begin{methods}
+		\method{cycleDetection}{findet Zyklus von $x_0$ und länge in $f$}{b+l}
+	\end{methods}
+	\sourcecode{math/cycleDetection.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Permutationen}
+	\begin{methods}
+		\method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)}
+	\end{methods}
+	\sourcecode{math/kthperm.cpp}
+	\begin{methods}
+		\method{permIndex}{bestimmt index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)}
+	\end{methods}
+	\sourcecode{math/permIndex.cpp}
+\end{algorithm}
 
 \paragraph{Lemma von \textsc{Bézout}}
-Sei $(x, y)$ eine Lösung für $ax + by = d$.
+Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$.
 Dann lassen sich wie folgt alle Lösungen berechnen:
 \[
-	\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right)
+\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right)
 \]
 
-\paragraph{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$}
-Sei $0 \leq x < n$. Definiere $d := \ggT(x, n)$.\newline
-\textbf{Falls $d = 1$:}
-\begin{itemize}[nosep]
-	\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit
-	$\alpha x + \beta n = 1$.
-	\item Nach Kongruenz gilt $\alpha x + \beta n \equiv \alpha x \equiv 1 \mod n$.
-	\item $x^{-1} :\equiv \alpha \mod n$
-	\end{itemize}
-\textbf{Falls $d \neq 1$:} Es existiert kein $x^{-1}$.
-\lstinputlisting{math/multInv.cpp}
+\paragraph{\textsc{Pell}-Gleichungen}
+Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert.
+Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen
+sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
+\begin{align*}
+	x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\
+	x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k
+\end{align*}
 
-\subsection{Mod-Exponent über $\mathbb{F}_p$}
-\lstinputlisting{math/modExp.cpp}
-Iterativ:
-\lstinputlisting{math/modPowIterativ.cpp}
+\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}
+	\runtime{\log(a) + \log(b)}
+	\sourcecode{math/gcd-lcm.cpp}
+	\sourcecode{math/extendedEuclid.cpp}
+\end{algorithm}
 
-\subsection{Chinesischer Restsatz}
+\subsection{Multiplikatives Inverses von $\boldsymbol{n}$ in $\boldsymbol{\mathbb{Z}/p\mathbb{Z}}$}
+\textbf{Falls $\boldsymbol{p}$ prim:}\quad $x^{-1} \equiv x^{p-2} \bmod p$
+
+\textbf{Falls $\boldsymbol{\ggT(n, p) = 1}$:}
 \begin{itemize}
-	\item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
-	\item Direkte Formel für zwei Kongruenzen $x \equiv a \mod n$, $x \equiv b \mod m$:
-	\[
-		x \equiv a - y * n * \frac{a - b}{d} \mod \frac{mn}{d}
-		\qquad \text{mit} \qquad
-		d := \ggT(n, m) = yn + zm
-	\]
-	Formel kann auch für nicht teilerfremde Moduli verwendet werden.
-	Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung,
-	wenn $a\equiv~b \mod \ggT(m, n)$.
-	In diesem Fall sind keine Faktoren
-	auf der linken Seite erlaubt.
+	\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit
+	$\alpha n + \beta p = 1$.
+	\item Nach Kongruenz gilt $\alpha n + \beta p \equiv \alpha n \equiv 1 \bmod p$.
+	\item $n^{-1} :\equiv \alpha \bmod p$
+	\end{itemize}
+\textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.
+\sourcecode{math/multInv.cpp}
+
+\begin{algorithm}{Lineare Kongruenz}
+	\begin{itemize}
+		\item Löst $ax\equiv b\pmod{m}$.
+		\item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt
+		also $g$ Lösungen modulo $m$.
+	\end{itemize}
+	\sourcecode{math/linearCongruence.cpp}
+\end{algorithm}
+
+\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
+%\vspace{-1.25em}
+%\begin{multicols}{2}
+	\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)}
+	\sourcecode{math/modMulIterativ.cpp}
+%	\vfill\null\columnbreak
+	\method{powMod}{berechnet $a^b \bmod n$}{\log(b)}
+	\sourcecode{math/modPowIterativ.cpp}
+%\end{multicols}
+%\vspace{-2.75em}
+\begin{itemize}
+	\item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! 
 \end{itemize}
-\lstinputlisting{math/chineseRemainder.cpp}
-
-\subsection{Primzahltest \& Faktorisierung}
-\lstinputlisting{math/primes.cpp}
 
-\subsection{Primzahlsieb von \textsc{Eratosthenes}}
-\lstinputlisting{math/primeSieve.cpp}
+\begin{algorithm}{Matrix-Exponent}
+	\begin{methods}
+		\method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
+		\method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2}
+	\end{methods}
+	\sourcecode{math/matrixPower.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Berlekamp-Massey}
+	\begin{methods}
+		\method{BerlekampMassey}{Berechnet ein lineare Recurenz $n$-ter Ordnung}{n^2}
+		\method{}{aus den ersten $2n$ Werte}{}
+	\end{methods}
+	\sourcecode{math/berlekampMassey.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Lineare-Recurenz}
+	Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine Lineare Recurenz. Dann kann das \mbox{$k$-te} folgenglid in \runtime{n^3\log(k)} brechnet werden.
+	$$\renewcommand\arraystretch{1.5}
+	\setlength\arraycolsep{3pt}
+	\begin{pmatrix} 
+		c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\
+		1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\
+		0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\
+		0 & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\
+		0 & \smash{\cdots} & 0 & 1 & 0 \\
+	\end{pmatrix}^k
+	\times~~
+	\begin{pmatrix} 
+		f(n-1) \\
+		f(n-2) \\
+		\smash{\vdots} \\
+		\smash{\vdots} \\
+		f(0) \\
+	\end{pmatrix}
+	~~=~~
+	\begin{pmatrix} 
+	f(n-1+k) \\
+	f(n-2+k) \\
+	\smash{\vdots} \\
+	\smash{\vdots} \\
+	f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
+	\end{pmatrix}
+	$$
+\end{algorithm}
+
+\begin{algorithm}{Chinesischer Restsatz}
+	\begin{itemize}
+		\item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
+		\item Direkte Formel für zwei Kongruenzen $x \equiv a \bmod n$, $x \equiv b \bmod m$:
+		\[
+			x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \frac{mn}{d}
+			\qquad \text{mit} \qquad
+			d := \ggT(n, m) = yn + zm
+		\]
+		Formel kann auch für nicht teilerfremde Moduli verwendet werden.
+		Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung,
+		wenn $a\equiv~b \bmod \ggT(m, n)$.
+		In diesem Fall sind keine Faktoren
+		auf der linken Seite erlaubt.
+	\end{itemize}
+	\sourcecode{math/chineseRemainder.cpp}
+\end{algorithm}
 
-\subsection{\textsc{Euler}sche $\varphi$-Funktion}
-\begin{itemize}[nosep]
+\begin{algorithm}{Primzahltest \& Faktorisierung}
+	\begin{itemize}
+		\item für $n > 10^9$ \texttt{BigInteger} benutzten order \texttt{modMul}! 
+	\end{itemize}
+	\method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
+	\sourcecode{math/millerRabin.cpp}
+	\method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}3]{n}}
+	\sourcecode{math/rho.cpp}
+	\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
+	\sourcecode{math/squfof.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
+	\begin{itemize}
+		\item Kann erweitert werden: Für jede Zahl den \{kleinsten, größten\} Primfaktor speichern, Liste von Primzahlen berechnen
+		\item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
+	\end{itemize}
+	\begin{methods}
+		\method{primeSieve}{berechnet Primzahlen und Anzahl}{n\*\log(\log(n))}
+		\method{isPrime}{prüft ob Zahl prim ist}{1}
+	\end{methods}
+	\sourcecode{math/primeSieve.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Teiler}
+	\begin{methods}
+		\method{countDivisors}{Zählt teiler von $n$}{n^\frac{1}{3}}
+		\method{isPrime}{prüft ob Zahl prim ist}{1}
+	\end{methods}
+	\sourcecode{math/divisors.cpp}
+\end{algorithm}
+
+\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
+\begin{methods}
+	\method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
+	\method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???}
+	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}
+\end{methods}
+\sourcecode{math/piLehmer.cpp}
+
+\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
+\begin{itemize}
 	\item Zählt die relativ primen Zahlen $\leq n$.
 
 	\item Multiplikativ:
@@ -61,67 +190,136 @@ Iterativ:
 	\item $p$ prim, $k \in \mathbb{N}$:
 	$~\varphi(p^k) = p^k - p^{k - 1}$
 
-	\item $n = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k}$:
-	$~\varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_k}\right)$
-	Evtl. ist es sinnvoll obgien Code zum Faktorisieren zu benutzen und dann diese Formel anzuwenden.
-
 	\item \textbf{\textsc{Euler}'s Theorem:}
-	Seien $a$ und $m$ teilerfremd. Dann:
-	$a^{\varphi(m)} \equiv 1 \mod m$\newline
+		Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
 	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
-	$a^{m} \equiv a \mod m$
+	$a^{m} \equiv a \pmod{m}$
 \end{itemize}
-\lstinputlisting{math/phi.cpp}
-
-\subsection{Primitivwurzeln}
-\begin{itemize}[nosep]
-	\item Primitivwurzel modulo $n$ existiert genau dann wenn:
-	\begin{itemize}[nosep]
-		\item $n$ ist $1$, $2$ oder $4$, oder
-		\item $n$ ist Potenz einer ungeraden Primzahl, oder
-		\item $n$ ist das Doppelte einer Potenz einer ungeraden Primzahl.
+\sourcecode{math/phi.cpp}
+
+\begin{algorithm}{\textsc{Möbius}-Funktion und \textsc{Möbius}-Inversion}
+	\begin{itemize}
+		\item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und  $g(n) := \sum_{d \vert n}f(d)$.
+		Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$.
+		\item $\sum\limits_{d \vert n}\mu(d) =
+		\begin{cases*}
+		1 & falls $n = 1$\\
+		0 & sonst
+		\end{cases*}$
 	\end{itemize}
-
-	\item Sei $g$ Primitivwurzel modulo $n$.
-	Dann gilt:\newline
-	Das kleinste $k$, sodass $g^k \equiv 1 \mod n$, ist $k = \varphi(n)$.
-\end{itemize}
-\lstinputlisting{math/primitiveRoot.cpp}
-
-\subsection{Diskreter Logarithmus}
-\lstinputlisting{math/discreteLogarithm.cpp}
-
-\subsection{Binomialkoeffizienten}
-\lstinputlisting{math/binomial.cpp}
-
-\subsection{LGS über $\mathbb{F}_p$}
-\lstinputlisting{math/lgsFp.cpp}
-
-\subsection{LGS über $\mathbb{R}$}
-\lstinputlisting{math/gauss.cpp}
-
-\subsection{Polynome \& FFT}
+	\textbf{Beispiel Inklusion/Exklusion:}
+	Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline
+	\textbf{Lösung}:
+	Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$.
+	Es gibt $2^{cnt[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten.
+	Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$.
+	\sourcecode{math/mobius.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Primitivwurzeln}
+	\begin{itemize}
+		\item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$
+		\item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln
+		\item Sei $g$ Primitivwurzel modulo $n$.
+		Dann gilt:\newline
+		Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$.
+	\end{itemize}
+	\begin{methods}
+		\method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)}
+		\method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)}
+	\end{methods}
+	\sourcecode{math/primitiveRoot.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Diskreter Logarithmus}
+	\begin{methods}
+		\method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)}
+	\end{methods}
+	\sourcecode{math/discreteLogarithm.cpp}
+\end{algorithm}
+%TODO
+\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel}
+	\begin{methods}
+		\method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)}
+	\end{methods}
+	Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$
+	\sourcecode{math/discreteNthRoot.cpp}
+\end{algorithm}
+
+\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/lgsFp.cpp}
+
+\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
+\sourcecode{math/gauss.cpp}
+
+\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
 Multipliziert Polynome $A$ und $B$.
-\begin{itemize}[nosep]
-	\item $\deg(A * B) = \deg(A) + \deg(B)$
-	\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe
-	$\deg(A * B) + 1$ haben.
-	Größe muss eine Zweierpotenz sein.
-	\item Für ganzzahlige Koeffizienten: \lstinline{(int)round(real(a[i]))}
-\end{itemize}
-\lstinputlisting{math/fft.cpp}
-
-\subsection{Numerisch Integrieren, Simpsonregel}
-\lstinputlisting{math/simpson.cpp}
-
-\subsection{3D-Kugeln}
-\lstinputlisting{math/spheres.cpp}
-
-\subsection{Longest Increasing Subsequence}
-\lstinputlisting{math/longestIncreasingSubsequence.cpp}
-
-\subsection{Inversionszahl und Mergesort}
-\lstinputlisting{math/inversions.cpp}
+	\begin{itemize}
+		\item $\deg(A \cdot B) = \deg(A) + \deg(B)$
+		\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe
+		$\deg(A \cdot B) + 1$ haben.
+		Größe muss eine Zweierpotenz sein.
+		\item Für ganzzahlige Koeffizienten: \lstinline{(int)round(real(a[i]))}
+		\item xor, or und and Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$
+	\end{itemize}
+	%\lstinputlisting{math/fft.cpp}
+	%\lstinputlisting{math/ntt.cpp}
+	%\textcolor{safeOrange}{$\blacksquare$} NTT code, %\textcolor{safeGreen}{$\blacksquare$} FFT code
+	\sourcecode{math/transforms/all.cpp}
+	\columnbreak
+	Für sehr viele transforms kann die Vertauschung vorberechnet werden:
+	\sourcecode{math/transforms/fftPerm.cpp}
+	Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)
+	\sourcecode{math/transforms/fftMul.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
+	\sourcecode{math/simpson.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Numerisch Extremstelle bestimmen}
+	\sourcecode{math/goldenSectionSearch.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Longest Increasing Subsequence}
+	\begin{itemize}
+		\item \code{lower\_bound} $\Rightarrow$ streng monoton
+		\item \code{upper\_bound} $\Rightarrow$ monoton
+	\end{itemize}
+	\sourcecode{math/longestIncreasingSubsequence.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Inversionszahl}
+	\sourcecode{math/inversions.cpp}
+\end{algorithm}
+
+\begin{algorithm}{\textsc{Legendre}-Symbol}
+	Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
+	\begin{align*}
+		\legendre{a}{p} &=
+		\begin{cases*}
+		\hphantom{-}0 & falls $p~\vert~a$ \\[-1ex]
+		\hphantom{-}1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \bmod p$ \\[-1ex]
+		-1 & sonst
+		\end{cases*} \\
+		\legendre{-1}{p} = (-1)^{\frac{p - 1}{2}} &=
+		\begin{cases*}
+		\hphantom{-}1 & falls $p \equiv 1 \bmod 4$ \\[-1ex]
+		-1 & falls $p \equiv 3 \bmod 4$
+		\end{cases*} \\
+		\legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} &=
+		\begin{cases*}
+		\hphantom{-}1 & falls $p \equiv \pm 1 \bmod 8$ \\[-1ex]
+		-1 & falls $p \equiv \pm 3 \bmod 8$
+		\end{cases*}
+	\end{align*}
+	\begin{align*}
+		\legendre{p}{q} \cdot \legendre{q}{p} = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} &&
+		\legendre{a}{p} \equiv a^{\frac{p-1}{2}}\bmod p
+	\end{align*}
+	\sourcecode{math/legendre.cpp}
+\end{algorithm}
 
 \subsection{Satz von \textsc{Sprague-Grundy}}
 Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
@@ -131,98 +329,22 @@ Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu
 		\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}
 	\right\} 
 \]
-$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\\\
+$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\
 Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.
 
-\subsection{\textsc{Legendre}-Symbol}
-Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
-\begin{align*}
-	\legendre{a}{p} &=
-	\begin{cases*}
-		 0 & falls $p~\vert~a$ \\[-1ex]
-		 1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \mod p$ \\[-1ex]
-		-1 & sonst
-	\end{cases*} \\
-	\legendre{-1}{p} &= (-1)^{\frac{p - 1}{2}} =
-	\begin{cases*}
-		 1 & falls $p \equiv 1 \mod 4$ \\[-1ex]
-		-1 & falls $p \equiv 3 \mod 4$
-	\end{cases*} \\
-	\legendre{2}{p} &= (-1)^{\frac{p^2 - 1}{8}} =
-	\begin{cases*}
-		 1 & falls $p \equiv \pm 1 \mod 8$ \\[-1ex]
-		-1 & falls $p \equiv \pm 3 \mod 8$
-	\end{cases*} \\
-	\legendre{p}{q} \cdot \legendre{q}{p} &=
-	(-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}
-\end{align*}
-\lstinputlisting{math/legendre.cpp}
-
-\subsection{\textsc{Möbius}-Funktion und \textsc{Möbius}-Inversion}
-\begin{itemize}
-	\item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und  $g(n) := \sum_{d \vert n}f(d)$.
-	Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$.
-	\item $\sum_{d \vert n}\mu(d) =
-			\begin{cases*}
-				1 & falls $n = 1$\\
-				0 & sonst
-			\end{cases*}$
-\end{itemize}
-\textbf{Beispiel Inklusion/Exklusion:}
-Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline
-\textbf{Lösung}:
-Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$.
-Es gibt $2^{cnt[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten.
-Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$.
-\lstinputlisting{math/mobius.cpp}
-
 \subsection{Kombinatorik}
 
-\begin{flushleft}
-	\begin{tabular}{ll}
-		\toprule
-		\multicolumn{2}{c}{Berühmte Zahlen} \\
-		\midrule 
-		\textsc{Fibonacci}	&
-		$f(0) = 0 \quad
-		f(1) = 1 \quad
-		f(n+2) = f(n+1) + f(n)$ \\
-
-		\textsc{Catalan}	&
-		$C_0 = 1 \qquad
-		C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =
-		\frac{1}{n + 1}\binom{2n}{n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$ \\
-
-		\textsc{Euler} I &
-		$\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \qquad
-		\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1} $ \\
-
-		\textsc{Euler} II &
-		$\eulerII{n}{0} = 1 \quad
-		\eulerII{n}{n} = 0 \quad
-		\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}$ \\
-
-		\textsc{Stirling} I &
-		$\stirlingI{0}{0} = 1 \qquad
-		\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad
-		\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}$ \\
-
-		\textsc{Stirling} II &
-		$\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
-		\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1}$ \\
-
-		\textsc{Bell} &
-		$B_1 = 1 \qquad
-		B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k}
-		= \sum\limits_{k = 0}^{n}\stirlingII{n}{k}$\\
-
-		\textsc{Partitions} &
-		$f(0,0) = 1 \quad
-		f(n,k) = 0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0$ \\
-		& $f(n,k) = f(n-k,k) + f(n-1,k-1)$ \\
-		\bottomrule
-	\end{tabular}
-\end{flushleft}
+\paragraph{Wilsons Theorem}
+A number $n$ is prime if and only if 
+$(n-1)!\equiv -1\bmod{n}$.\\
+($n$ is prime if and only if $(m-1)!\cdot(n-m)!\equiv(-1)^m\bmod{n}$ for all $m$ in $\{1,\dots,n\}$)
+\begin{align*}
+	(n-1)!\equiv\begin{cases}
+		-1\bmod{n},&\mathrm{falls}~n \in \mathbb{P}\\
+		\hphantom{-}2\bmod{n},&\mathrm{falls}~n = 4\\
+		\hphantom{-}0\bmod{n},&\mathrm{sonst}
+	\end{cases}
+\end{align*}
 
 \paragraph{\textsc{Zeckendorfs} Theorem}
 Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer
@@ -231,340 +353,124 @@ aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.\\
 \emph{Lösung:} Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch
 hineinpasst.
 
+\paragraph{\textsc{Lucas}-Theorem}
+Ist $p$ prim, $m=\sum_{i=0}^km_ip^i$, $n=\sum_{i=0}^kn_ip^i$ ($p$-adische Darstellung),
+so gilt
+\vspace{-0.75\baselineskip}
+\[
+	\binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i} \bmod{p}.
+\]
+
+\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
+\input{math/tables/twelvefold}
+
 \paragraph{\textsc{Catalan}-Zahlen}
-\begin{itemize}[nosep]
-	\item Die erste und dritte angegebene Formel sind relativ sicher gegen Overflows.
-	\item Die erste Formel kann auch zur Berechnung der \textsc{Catalan}-Zahlen
-	bezüglich eines Moduls genutzt werden.
-	\item Die \textsc{Catalan}-Zahlen geben an: $C_n =$
-	\begin{itemize}[nosep]
+\begin{itemize}
+	\item Die \textsc{Catalan}-Zahl $C_n$ gibt an:
+	\begin{itemize}
 		\item Anzahl der Binärbäume mit $n$ nicht unterscheidbaren Knoten.
 		\item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren.
 		\item Anzahl der korrekten Klammerungen von $n+1$ Faktoren.
-		\item Anzahl der Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken in
-		Dreiecke zu zerlegen.
+		\item Anzahl der Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken in Dreiecke zu zerlegen.
 		\item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in
 		einem $n \times n$-Gitter, die nicht die Diagonale kreuzen.
 	\end{itemize}
 \end{itemize}
+\[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =
+\frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} \cdot C_{n-1}\]
+\begin{itemize}
+	\item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2}
+	\item Formel $2$ und $3$ erlauben berechnung in \runtime{n}
+\end{itemize}
 
 \paragraph{\textsc{Euler}-Zahlen 1. Ordnung}
 Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
 Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen.
 Dabei wird entweder ein Ansteig in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
+\[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad
+\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}=
+\sum_{i=0}^{k} (-1)^i\binom{n+1}{i}(k+1-i)^n\]
+\begin{itemize}
+	\item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2}
+	\item Formel $2$ erlaubt berechnung in \runtime{n\log(n)}
+\end{itemize}
 
 \paragraph{\textsc{Euler}-Zahlen 2. Ordnung}
 Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
+\[\eulerII{n}{0} = 1 \qquad\eulerII{n}{n} = 0 \qquad\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}\]
+\begin{itemize}
+	\item Formel erlaubt berechnung ohne Division in \runtime{n^2}
+\end{itemize}
 
 \paragraph{\textsc{Stirling}-Zahlen 1. Ordnung}
 Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.
 Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigene Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden.
+\[\stirlingI{0}{0} = 1 \qquad
+\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad
+\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\]
+\begin{itemize}
+	\item Formel erlaubt berechnung ohne Division in \runtime{n^2}
+\end{itemize}
 
 \paragraph{\textsc{Stirling}-Zahlen 2. Ordnung}
 Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.
 Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition einzuordnen.
 Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.
+\[\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
+\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} =
+\frac{1}{k!} \sum\limits_{i=0}^{k} (-1)^{k-i}\binom{k}{i}i^n\]
+\begin{itemize}
+	\item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2}
+	\item Formel $2$ erlaubt berechnung in \runtime{n\log(n)}
+\end{itemize}
 
 \paragraph{\textsc{Bell}-Zahlen}
 Anzahl der Partitionen von $\{1, \ldots, n\}$.
 Wie \textsc{Striling}-Zahlen 2. Ordnung ohne Limit durch $k$.
+\[B_1 = 1 \qquad
+B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k}
+= \sum\limits_{k = 0}^{n}\stirlingII{n}{k}\qquad\qquad B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\]
+
+\paragraph{Partitions}
+Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.
+Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
+\begin{align*}
+	p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\
+	p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt]
+	p(n)&=\sum_{k=1}^{n} p_k(n)=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}p\bigg(n - \frac{k(3k-1)}{2}\bigg)
+\end{align*}
+\begin{itemize}
+	\item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.
+	\item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$.
+\end{itemize}
 
-\paragraph{Integer Partitions}
-Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximalem Elment $\leq k$.\\
-
-\begin{tabular}{lcr}
-	\toprule
-	\multicolumn{3}{c}{Binomialkoeffizienten} \\
-	\midrule
-	$\binom{n}{k} = \frac{n!}{k!(n - k)!}$ &
-	$\binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1}$ &
-	$\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$ \\
-
-	$\sum\limits_{k = 0}^n \binom{n}{k} = 2^n$ &
-	$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}$ &
-	$\binom{n}{k} = (-1)^k \binom{k - n - 1}{k}$ \\
-
-	$\binom{n}{k} = \binom{n}{n - k}$ &
-	$\sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}$ &
-	$\sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}$ \\
-
-	$\binom{n}{k} = \frac{n}{k}\binom{n - 1}{k - 1}$ &
-	$\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}$ &
-	$\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$ \\
-	\bottomrule
-\end{tabular}
-\vspace{1mm}
-
-\begin{tabular}{l|l|l}
-	\toprule
-	\multicolumn{3}{c}{Reihen} \\
-	\midrule
-	$\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ &
-	$\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(n + 2)}{6}$ & 
-	$\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ \\
-
-	$\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \quad c \neq 1$ &
-	$\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \quad \vert c \vert < 1$ &
-	$\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \quad \vert c \vert < 1$ \\
-
-	\multicolumn{2}{l|}{
-		$\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$
-	} &
-	$\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\
-
-	$H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ &
-	\multicolumn{2}{l}{
-		$\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$
-	} \\
-
-	$\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ &
-	\multicolumn{2}{l}{
-		$\sum\limits_{i = 1}^n \binom{i}{m}H_i =
-		\binom{n + 1}{m + 1} \left(H_{n + 1} - \frac{1}{m  + 1}\right)$
-	} \\
-	\bottomrule
-\end{tabular}
-\vspace{1mm}
-
-\begin{tabular}{l|r}
-	\toprule
-	\multicolumn{2}{c}{
-		Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen)
-	} \\
-	\midrule
-	$\E(X + Y) = \E(X) + \E(Y)$ &
-	$\E(\alpha X) = \alpha \E(X)$ \\
-
-	$X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ &
-	$\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\
-
-	$\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ &
-	$\Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ \\
-	\bottomrule
-\end{tabular}
-\vspace{1mm}
-
-\begin{tabular}{lr|lr}
-	\toprule
-	\multicolumn{4}{c}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\
-	\midrule
-	$\#A > k\#B$ & $Pr = \frac{a - kb}{a + b}$ &
-	$\#B - \#A \leq k$ & $Pr = 1 - \frac{a!b!}{(a + k + 1)!(b - k - 1)!}$ \\
-
-	$\#A \geq k\#B$ & $Pr = \frac{a + 1 - kb}{a + 1}$ &
-	$\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ \\
-	\bottomrule
-\end{tabular}
-\vspace{5mm}
-
-\begin{tabular}{c|cccc}
-	\toprule
-	\multicolumn{5}{c}{The Twelvefold Way (verteile $n$ Bälle auf $k$ Boxen)} \\
-	\midrule
-	Bälle & identisch & unterscheidbar & identisch      & unterscheidbar \\
-	Boxen & identisch & identisch      & unterscheidbar & unterscheidbar \\
-	\midrule
-	- &
-	$p_k(n)$ &
-	$\sum\limits_{i = 0}^k \stirlingII{n}{i}$ &
-	$\binom{n + k - 1}{k - 1}$ &
-	$k^n$ \\
-
-	size $\geq 1$ &
-	$p(n, k)$ &
-	$\stirlingII{n}{k}$ &
-	$\binom{n - 1}{k - 1}$ &
-	$k! \stirlingII{n}{k}$ \\
-
-	size $\leq 1$ &
-	$[n \leq k]$ &
-	$[n \leq k]$ &
-	$\binom{k}{n}$ &
-	$n! \binom{k}{n}$ \\
-	\midrule
-	\multicolumn{5}{l}{
-		$p_k(n)$: \#Anzahl der Partitionen von $n$ in $\leq k$ positive Summanden.
-	} \\
-	\multicolumn{5}{l}{
-		$p(n, k)$: \#Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.
-	} \\
-	\multicolumn{5}{l}{
-		$[\text{Bedingung}]$: \lstinline{return Bedingung ? 1 : 0;}
-	} \\
-	\bottomrule
-\end{tabular}
-\vspace{1mm}
-
-\begin{flushleft}
-	\begin{tabular}{l|cccl}
-		\toprule
-		\multicolumn{5}{c}{Platonische Körper} \\
-		\midrule
-		Übersicht       & Seiten & Ecken & Kanten & dual zu \\
-		\midrule
-		Tetraeder       & 4      & 4     & 6      & Tetraeder \\
-		Würfel/Hexaeder & 6      & 8     & 12     & Oktaeder \\
-		Oktaeder        & 8      & 6     & 12     & Würfel/Hexaeder\\
-		Dodekaeder      & 12     & 20    & 30     & Ikosaeder \\
-		Ikosaeder       & 20     & 12    & 30     & Dodekaeder \\
-		\midrule
-		\multicolumn{5}{c}{Färbungen mit maximal $n$ Farben (bis auf Isomorphie)} \\
-		\midrule
-		\multicolumn{3}{l}{Ecken vom Oktaeder/Seiten vom Würfel} &
-		\multicolumn{2}{l}{$(n^6 + 3n^4 + 12n^3 + 8n^2)/24$} \\
-
-		\multicolumn{3}{l}{Ecken vom Würfel/Seiten vom Oktaeder} &
-		\multicolumn{2}{l}{$(n^8 + 17n^4 + 6n^2)/24$} \\
-
-		\multicolumn{3}{l}{Kanten vom Würfel/Oktaeder} &
-		\multicolumn{2}{l}{$(n^{12} + 6n^7 + 3n^6 + 8n^4 + 6n^3)/24$} \\
-
-		\multicolumn{3}{l}{Ecken/Seiten vom Tetraeder} &
-		\multicolumn{2}{l}{$(n^4 + 11n^2)/12$} \\
-
-		\multicolumn{3}{l}{Kanten vom Tetraeder} &
-		\multicolumn{2}{l}{$(n^6 + 3n^4 + 8n^2)/12$} \\
-
-		\multicolumn{3}{l}{Ecken vom Ikosaeder/Seiten vom Dodekaeder} &
-		\multicolumn{2}{l}{$(n^{12} + 15n^6 + 44n^4)/60$} \\
-
-		\multicolumn{3}{l}{Ecken vom Dodekaeder/Seiten vom Ikosaeder} &
-		\multicolumn{2}{l}{$(n^{20} + 15n^{10} + 20n^8 + 24n^4)/60$} \\
-
-		\multicolumn{3}{l}{Kanten vom Dodekaeder/Ikosaeder (evtl. falsch)} &
-		\multicolumn{2}{l}{$(n^{30} + 15n^{16} + 20n^{10} + 24n^6)/60$} \\
-		\bottomrule
-	\end{tabular}
-\end{flushleft}
-\vspace{1mm}
-
-\begin{tabular}{p{4.3cm}|p{7cm}}
-	\toprule
-	\multicolumn{2}{c}{Nim-Spiele (\ding{182} letzter gewinnt (normal), \ding{183} letzter verliert)} \\
-	\midrule
-	Beschreibung &
-	Strategie \\
-	\midrule
-
-	$M = [\mathit{pile}_i]$\newline
-	$[x] := \{1, \ldots, x\}$&
-	$\mathit{SG} = \oplus_{i = 1}^n \mathit{pile}_i$\newline
-	\ding{182} Nimm von einem Stapel, sodass $\mathit{SG}$ $0$ wird.\newline
-	\ding{183} Genauso.
-	Außer: Bleiben nur noch Stapel der Größe $1$, erzeuge ungerade Anzahl solcher Stapel.\\
-	\midrule
-
-	$M = \{a^m \mid m \geq 0\}$ &
-	$a$ ungerade: $\mathit{SG}_n = n \% 2$\newline
-	$a$ gerade:\newline
-	$\mathit{SG}_n = 2$, falls $n \equiv a \mod (a + 1) $\newline
-	$\mathit{SG}_n = n \% (a + 1) \% 2$, sonst.\\
-	\midrule
-
-	$M_{\text{\ding{172}}} = \left[\frac{\mathit{pile}_i}{2}\right]$\newline
-	$M_{\text{\ding{173}}} =
-	\left\{\left\lceil\frac{\mathit{pile}_i}{2}\right\rceil,
-	\mathit{pile}_i\right\}$ &
-	\ding{172}
-	$\mathit{SG}_{2n} = n$,
-	$\mathit{SG}_{2n+1} = \mathit{SG}_n$\newline
-	\ding{173}
-	$\mathit{SG}_0 = 0$,
-	$\mathit{SG}_n = [\log_2 n] + 1$ \\
-	\midrule
-
-	$M_{\text{\ding{172}}} = \text{Teiler von $\mathit{pile}_i$}$\newline
-	$M_{\text{\ding{173}}} = \text{echte Teiler von $\mathit{pile}_i$}$ &
-	\ding{172}
-	$\mathit{SG}_0 = 0$,
-	$\mathit{SG}_n = \mathit{SG}_{\text{\ding{173},n}} + 1$\newline
-	\ding{173}
-	$\mathit{ST}_1 = 0$,
-	$\mathit{SG}_n = \text{\#Nullen am Ende von $n_{bin}$}$\\
-	\midrule
-
-	$M_{\text{\ding{172}}} = [k]$\newline
-	$M_{\text{\ding{173}}} = S$, ($S$ endlich)\newline
-	$M_{\text{\ding{174}}} = S \cup \{\mathit{pile}_i\}$ &
-	$\mathit{SG}_{\text{\ding{172}}, n} = n \mod (k + 1)$\newline
-	\ding{182} Niederlage bei $\mathit{SG} = 0$\newline
-	\ding{183} Niederlage bei $\mathit{SG} = 1$\newline
-	$\mathit{SG}_{\text{\ding{174}}, n} = \mathit{SG}_{\text{\ding{173}}, n} + 1$\\
-	\midrule
-
-	\multicolumn{2}{l}{
-		Für jedes endliche $M$ ist $\mathit{SG}$ eines Stapels irgendwann periodisch.
-	} \\
-	\midrule
-
-	\textsc{Moore}'s Nim:\newline
-	Beliebige Zahl von maximal $k$ Stapeln. &
-	\ding{182}
-	Schreibe $\mathit{pile}_i$ binär.
-	Addiere ohne Übertrag zur Basis $k + 1$.
-	Niederlage, falls Ergebnis gleich 0.\newline
-	\ding{183}
-	Wenn alle Stapel $1$ sind:
-	Niederlage, wenn $n \equiv 1 \mod (k + 1)$.
-	Sonst wie in \ding{182}.\\
-	\midrule
-
-	Staircase Nim:\newline
-	$n$ Stapel in einer Reihe.
-	Beliebige Zahl von Stapel $i$ nach Stapel $i-1$. &
-	Niederlage, wenn Nim der ungeraden Spiele verloren ist:\newline
-	$\oplus_{i = 0}^{(n - 1) / 2} \mathit{pile}_{2i + 1} = 0$\\
-	\midrule
-
-	\textsc{Lasker}'s Nim:\newline
-	Zwei mögliche Züge:\newline
-	1) Nehme beliebige Zahl.\newline
-	2) Teile Stapel in zwei Stapel (ohne Entnahme).&
-	$\mathit{SG}_n = n$, falls $n \equiv 1,2 \mod 4$\newline
-	$\mathit{SG}_n = n + 1$, falls $n \equiv 3 \mod 4$\newline
-	$\mathit{SG}_n = n - 1$, falls $n \equiv 0 \mod 4$\\
-	\midrule
-
-	\textsc{Kayles}' Nim:\newline
-	Zwei mögliche Züge:\newline
-	1) Nehme beliebige Zahl.\newline
-	2) Teile Stapel in zwei Stapel (mit Entnahme).&
-	Berechne $\mathit{SG}_n$ für kleine $n$ rekursiv.\newline
-	$n \in [72,83]: \quad 4, 1, 2, 8, 1, 4, 7, 2, 1, 8, 2, 7$\newline
-	Periode ab $n = 72$ der Länge $12$.\\
-	\bottomrule
-\end{tabular}
-
-\begin{tabular}{ll}
-	\toprule
-	\multicolumn{2}{c}{Verschiedenes} \\
-	\midrule
-	Türme von Hanoi, minimale Schirttzahl: &
-	$T_n = 2^n - 1$ \\
-
-	\#Regionen zwischen $n$ Gearden	&
-	$\frac{n\left(n + 1\right)}{2} + 1$ \\
-
-	\#geschlossene Regionen zwischen $n$ Geraden &
-	$\frac{n^2 - 3n + 2}{2}$ \\
-
-	\#markierte, gewurzelte Bäume	&
-	$n^{n-1}$ \\
-
-	\#markierte, nicht gewurzelte Bäume	&
-	$n^{n-2}$ \\
-
-	\#Wälder mit $k$ gewurzelten Bäumen	&
-	$\frac{k}{n}\binom{n}{k}n^{n-k}$ \\
-
-	Derangements &
-	$!n = (n - 1)(!(n - 1) + !(n - 2))$ \\
-	&
-	$!n = \left\lfloor\frac{n!}{e} + \frac{1}{2}\right\rfloor$ \\
-	&
-	$\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\
-	\bottomrule
-\end{tabular}
-
-% \subsection{Big Integers}
-% \lstinputlisting{math/bigint.cpp}
+\paragraph{Binomialkoeffizienten}
+Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.
+
+\textbf{WICHTIG:} Binomialkoeffizient in \runtime{1} berechnen indem man $x!$ vorberechnet.
+
+%\begin{algorithm}{Binomialkoeffizienten}
+	\begin{methods}
+		\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
+	\end{methods}
+	\sourcecode{math/binomial.cpp}
+
+\columnbreak
+	\begin{methods}
+		\method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
+	\end{methods}
+	\textbf{Wichtig:} $p > n$
+	\sourcecode{math/binomial3.cpp}
+	
+	\begin{methods}
+		\method{calc\_binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n}
+	\end{methods}
+	\textbf{WICHTIG:} braucht alle Primzahlen $\leq n$
+	\sourcecode{math/binomial2.cpp}
+%\end{algorithm}
+
+%\input{math/tables/numbers}
+
+\begin{algorithm}[optional]{Big Integers}
+	\sourcecode{math/bigint.cpp}
+\end{algorithm}
-- 
cgit v1.2.3

