libzahl

commit 87e84a9167666022bba7c73b5447791bf9f6797b
parent 18a0e23b2f2e37c56c4f0f9a3dd56c1c619a4468
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(-)
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.