# (wrong string) ée

From: <git_AT_suckless.org>
Date: Sat, 23 Jul 2016 17:55:41 +0200 (CEST)

commit 67ebaf88644f0bf47103af79fee76d015d43ce00
Author: Mattias Andrée <maandree_AT_kth.se>
AuthorDate: Sat Jul 23 17:49:40 2016 +0200
Commit: Mattias Andrée <maandree_AT_kth.se>
CommitDate: Sat Jul 23 17:49:40 2016 +0200

Add two exercises to the manual

[M10] Convergence of the Lucas Number ratios
[M12+] Factorisation of factorials

diff --git a/Makefile b/Makefile
index e7a86e8..4087d3e 100644
--- a/Makefile
+++ b/Makefile
_AT_@ -82,7 +82,8 @@ TEXSRC =\
doc/bit-operations.tex\
doc/number-theory.tex\
doc/random-numbers.tex\
- doc/not-implemented.tex
+ doc/not-implemented.tex\
+ doc/exercises.tex

HDR_PUBLIC = zahl.h $(HDR_SEMIPUBLIC) HDR =$(HDR_PUBLIC) $(HDR_PRIVATE) diff --git a/doc/exercises.tex b/doc/exercises.tex new file mode 100644 index 0000000..7f9cd8c --- /dev/null +++ b/doc/exercises.tex _AT_@ -0,0 +1,96 @@ +\chapter{Exercises} +\label{chap:Exercises} + +% TODO +% +% All exercises should be group with a chapter +% +% ▶ Recommended +% M Matematically oriented +% HM Higher matematical education required +% +% 00 Immediate +% 10 Simple +% 20 Medium +% 30 Moderately hard +% 40 Term project +% 50 Research project +% +% ⁺ High risk of undershoot difficulty + + +\begin{enumerate}[label=\textbf{\arabic*}.] + + +\item {[\textit{M10}]} \textbf{Convergence of the Lucas Number ratios} + +Find an approximation for$\displaystyle{ \lim_{n \to \infty} \frac{L_{n + 1}}{L_n}}$, +where$L_n$is the$n^{\text{th}}$Lucas Number \psecref{sec:Lucas numbers}. + +$$\displaystyle{ + L_n \stackrel{\text{\tiny{def}}}{\text{=}} \left \{ \begin{array}{ll} + 2 & \text{if} ~ n = 0 \\ + 1 & \text{if} ~ n = 1 \\ + L_{n - 1} + L_{n + 1} & \text{otherwise} + \end{array} \right . +}$$ + + +\item {[\textit{M12${}^+$}]} \textbf{Factorisation of factorials} + +Implement the function + +\vspace{-1em} +\begin{alltt} + void factor_fact(z_t n); +\end{alltt} +\vspace{-1em} + +\noindent +which prints the prime factorisation of$n!$(the$n^{\text{th}}$factorial). +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!$. + + +\end{enumerate} + + + +\chapter{Solutions} +\label{chap:Solutions} + + +\begin{enumerate}[label=\textbf{\arabic*}.] + +\item \textbf{Convergence of the Lucas Number ratios} + +It would be a mistake to use bignum, and bigint in particular, +to solve this problem. Good old mathematics is a much better solution. + +$$\lim_{n \to \infty} \frac{L_{n + 1}}{L_n} = \lim_{n \to \infty} \frac{L_{n}}{L_{n - 1}} = \lim_{n \to \infty} \frac{L_{n - 1}}{L_{n - 2}}$$ + +$$\frac{L_{n}}{L_{n - 1}} = \frac{L_{n - 1}}{L_{n - 2}}$$ + +$$\frac{L_{n - 1} + L_{n - 2}}{L_{n - 1}} = \frac{L_{n - 1}}{L_{n - 2}}$$ + +$$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. + + +\item \textbf{Factorisation of factorials} + +Base your implementation on + +$$\displaystyle{ + n! = \prod_{p~\in~\textbf{P}}^{n} p^{k_p}, ~\text{where}~ + k_p = \sum_{a = 1}^{\lfloor \log_p n \rfloor} \lfloor np^{-a} \rfloor. +}$$ + +There is no need to calculate$\lfloor \log_p n \rfloor$, +you will see when$p^a > n\$.
+
+
+\end{enumerate}
diff --git a/doc/libzahl.tex b/doc/libzahl.tex
index c07a5e0..dc1835b 100644
--- a/doc/libzahl.tex
+++ b/doc/libzahl.tex
_AT_@ -6,6 +6,7 @@
\usepackage{amsmath, amssymb, mathtools, MnSymbol, mathrsfs, esvect}
\usepackage{tipa, color, graphicx}
\usepackage{shorttoc, minitoc}
+\usepackage{enumitem}
\usepackage[english]{babel}
\selectlanguage{english}