libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | LICENSE

commit 555b57b3190c2ed6f73970c0515ac77dc4087220
parent 67ebaf88644f0bf47103af79fee76d015d43ce00
Author: Mattias Andrée <maandree@kth.se>
Date:   Sat, 23 Jul 2016 20:07:26 +0200

Add exercise: [M20] Reverse factorisation of factorials

Signed-off-by: Mattias Andrée <maandree@kth.se>

Diffstat:
doc/exercises.tex | 49++++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 48 insertions(+), 1 deletion(-)

diff --git a/doc/exercises.tex b/doc/exercises.tex @@ -52,6 +52,27 @@ The function shall be efficient for all $n$ where all primes $p \le n$ can be found efficiently. You can assume that $n \ge 2$. You should not evaluate $n!$. +\item {[\textit{M20}]} \textbf{Reverse factorisation of factorials} + +You should already have solved ``Factorisation of factorials'' +before you solve this problem. + +Implement the function + +\vspace{-1em} +\begin{alltt} + void unfactor_fact(z_t x, z_t *P, + unsigned long long int *K, size_t n); +\end{alltt} +\vspace{-1em} + +\noindent +which given the factorsation of $x!$ determines $x$. +The factorisation of $x!$ is +$\displaystyle{\prod_{i = 1}^{n} P_i^{K_i}}$, where +$P_i$ is \texttt{P[i - 1]} and $K_i$ is \texttt{K[i - 1]}. + + \end{enumerate} @@ -77,7 +98,7 @@ $$ 1 + \frac{L_{n - 2}}{L_{n - 1}} = \frac{L_{n - 1}}{L_{n - 2}} $$ $$ 1 + \varphi = \frac{1}{\varphi} $$ -So the ratio tends toward the golden ration. +So the ratio tends toward the golden ratio. \item \textbf{Factorisation of factorials} @@ -93,4 +114,30 @@ There is no need to calculate $\lfloor \log_p n \rfloor$, you will see when $p^a > n$. +\item \textbf{Reverse factorisation of factorials} + +$\displaystyle{x = \max_{p ~\in~ P} ~ p \cdot f(p, k_p)}$, +where $k_p$ is the power of $p$ in the factorisation +of $x!$. $f(p, k)$ is defined as: + +\vspace{1em} +\hspace{-2.8ex} +\begin{minipage}{\linewidth} +\begin{algorithmic} + \STATE $k^\prime \gets 0$ + \WHILE{$k > 0$} + \STATE $a \gets 0$ + \WHILE{$p^a \le k$} + \STATE $k \gets k - p^a$ + \STATE $a \gets a + 1$ + \ENDWHILE + \STATE $k^\prime \gets k^\prime + p^{a - 1}$ + \ENDWHILE + \RETURN $k^\prime$ +\end{algorithmic} +\end{minipage} +\vspace{1em} + + + \end{enumerate}