(wrong string) ée

From: <git_AT_suckless.org>
Date: Sat, 23 Jul 2016 20:10:40 +0200 (CEST)

commit 555b57b3190c2ed6f73970c0515ac77dc4087220
Author: Mattias Andrée <maandree_AT_kth.se>
AuthorDate: Sat Jul 23 20:07:26 2016 +0200
Commit: Mattias Andrée <maandree_AT_kth.se>
CommitDate: Sat Jul 23 20:07:26 2016 +0200

    Add exercise: [M20] Reverse factorisation of factorials
    
    Signed-off-by: Mattias Andrée <maandree_AT_kth.se>

diff --git a/doc/exercises.tex b/doc/exercises.tex
index 7f9cd8c..2d68130 100644
--- a/doc/exercises.tex
+++ b/doc/exercises.tex
_AT_@ -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}
 
 
_AT_@ -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}
_AT_@ -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}
Received on Sat Jul 23 2016 - 20:10:40 CEST