Add exercise: [M13] The totient from factorisation - libzahl - big integer library
HTML git clone git://git.suckless.org/libzahl
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
DIR commit 87e84a9167666022bba7c73b5447791bf9f6797b
DIR parent 18a0e23b2f2e37c56c4f0f9a3dd56c1c619a4468
HTML Author: Mattias Andrée <maandree@kth.se>
Date: Fri, 21 Oct 2016 05:20:55 +0200
Add exercise: [M13] The totient from factorisation
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
M doc/exercises.tex | 57 +++++++++++++++++++++++++++++++
1 file changed, 57 insertions(+), 0 deletions(-)
---
DIR diff --git a/doc/exercises.tex b/doc/exercises.tex
@@ -271,6 +271,38 @@ and $\varphi(1) = 1$.
+\item {[\textit{M13}]} \textbf{The totient from factorisation}
+
+Implement the function
+
+\vspace{-1em}
+\begin{alltt}
+ void totient_fact(z_t t, z_t *P,
+ unsigned long long int *K, size_t n);
+\end{alltt}
+\vspace{-1em}
+
+\noindent
+which calculates the totient $t = \varphi(n)$, where
+$n = \displaystyle{\prod_{i = 1}^n P_i^{K_i}} > 0$,
+and $P_i = \texttt{P[i - 1]} \in \textbf{P}$,
+$K_i = \texttt{K[i - 1]} \ge 1$. All values \texttt{P}.
+\texttt{P} and \texttt{K} make up the prime factorisation
+of $n$.
+
+You can use the following rules:
+
+\( \displaystyle{
+ \begin{array}{ll}
+ \varphi(1) = 1 & \\
+ \varphi(p) = p - 1 & \text{if } p \in \textbf{P} \\
+ \varphi(nm) = \varphi(n)\varphi(m) & \text{if } \gcd(n, m) = 1 \\
+ n^a\varphi(n) = \varphi(n^{a + 1}) &
+ \end{array}
+}\)
+
+
+
\item {[\textit{HMP32}]} \textbf{Modular tetration}
Implement the function
@@ -711,6 +743,31 @@ then, $\varphi(n) = \varphi|n|$.
+\item \textbf{The totient from factorisation}
+
+\vspace{-1em}
+\begin{alltt}
+void
+totient_fact(z_t t, z_t *P,
+ unsigned long long *K, size_t n)
+\{
+ z_t a, one;
+ zinit(a), zinit(one);
+ zseti(t, 1);
+ zseti(one, 1);
+ while (n--) \{
+ zpowu(a, P[n], K[n] - 1);
+ zmul(t, t, a);
+ zsub(a, P[n], one);
+ zmul(t, t, a);
+ \}
+ zfree(a), zfree(one);
+\}
+\end{alltt}
+\vspace{-1em}
+
+
+
\item \textbf{Modular tetration}
Let \texttt{totient} be Euler's totient function.