\documentclass[10pt]{scrartcl}

\usepackage{fancyvrb}

\usepackage{umlaut}
\usepackage{a4}

%%%%%%%% math symbols
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

% code typesetting in text
\newcommand{\cd}[1]{{{\small \tt{#1}}}}

% code parsed by GHC, completely verbatim (fancyvrb):
\DefineVerbatimEnvironment{code}{Verbatim}{fontsize=\small, frame=lines,
                                           label=\textit{compiled code}}
% ignored code (fancyvrb):
\DefineVerbatimEnvironment{icode}{Verbatim}{fontsize=\small, frame=lines,
                                            label=\textit{ignored code}}

\author{Jost Berthold}
\date{}

\title{Parallelit\"at in fkt.$^{\mbox{alen}}$ Spr., SS
  06\footnote{Dieses Programm ist in ``literate-Haskell'' geschrieben,
    daher die Dateiendung \cd{lhs}.  Der Quelltext lässt sich sowohl
    mit \LaTeX ~setzen, als auch mit ghc compilieren.  } }

\begin{document}

\maketitle

\section*{Aufgabe 2.2}

Es ist ein Hauptprogramm zu schreiben, das als Parameter eine Zahl
akzeptiert und etwas damit berechnet. Parameter bekommt man mit
\cd{getArgs :: IO [String]}, die Funktion \cd{read :: String -> a}
konvertiert in den passenden Typ, hier \cd{Int}.
Fehlt: Fehlerbehandlung, falls kein Parameter vorhanden.

\begin{code}
import System
import List 

main = do args <- getArgs
          let 
            n = read (args!!0)
	  putStrLn ("Sequenzielle Summe: " ++ (show (summePhi n)))
	  putStrLn ("Mit Primzahlen:" ++ (show (summePhiO n)))
\end{code}

\subsection*{Berechnung}
Zu berechnen: Summe der Werte $\varphi (k)$ für $k \in \{1..n\}$.
\begin{code}
summePhi :: Int -> Int
summePhi n = sum ( map phi [1..n])

phi :: Int -> Int
phi n = length (filter (relprime n) [1..(n-1)])

hcf     :: Int -> Int -> Int
hcf x 0 = x
hcf x y = hcf y (rem x y)

relprime     :: Int -> Int -> Bool
relprime x y = hcf x y == 1

\end{code}
\newpage

\subsection*{\ldots oder mit etwas Mathematik \ldots}
{\footnotesize Quelle: \verb!de.wikipedia.org/wiki/Eulersche_%CF%86-Funktion!}

Falls $ p $ Primzahl ist, gilt $ \varphi(p) = p - 1 $.

Falls $p$ und $q$ teilerfremd sind, ist $\varphi$ multiplikativ: 
$$\varphi (p\cdot q) = \varphi (p) \cdot \varphi (q) \mbox{, falls } ggt(p,q) = 1$$

Ferner: $p^k$ ist teilerfremd zu allen kleineren Zahlen, die 
nicht Vielfache von $p$ sind. Vielfache von $p$ kleiner als $p^k$
sind gerade $\{ 1\cdot p,2\cdot p,3\cdot p, \ldots ,(p^{k-1}-1)\cdot p \}$.
Folglich gilt $$\varphi(p^k) = (p-1)p^{k-1}$$

Sei $n \in \mathbb{N}$ beliebig, und die Primfaktorzerlegung für 
$n$ sei $p_1^{k_1} \cdot ... \cdot p_m^{k_m} $.

Dann ist $\varphi(n) =  \sum_{j=1}^m ((p_j - 1) \cdot p_k^{k_j-1} )$

\begin{code}
summePhiO n = sum (map phiOpt [1..n])

phiOpt :: Int -> Int
phiOpt n = foldl (*) 1  [ (p-1)*p^(k-1) 
			  | (p,k) <- primefactors n ]

primefactors :: Int -> [(Int,Int)]
primefactors n | n <= 1    = []
	       | otherwise = primeList (primesIn primes n)

primeList :: [Int] -> [(Int,Int)]
primeList ps = [ (x, length (filter (==x) ps))
		 | x <- nub ps ] -- List::nub: Duplikate aus Liste entfernen 

primesIn :: [Int] -> Int -> [Int]
primesIn [] _ = error "no primes left!"
primesIn ps@(p:rest) n | p > n          = []
		       | n `mod` p == 0 = p:primesIn ps (n `div` p)
		       | otherwise      = primesIn rest n

-- Primzahlen, siehe Vorlesung:
primes :: [Int]
primes = sieve [2..]
sieve :: [Int] -> [Int]
sieve [] = []
sieve (x:xs) = x: (sieve (filter (not . multiple) xs))
    where multiple y = rem y x == 0
\end{code}


\end{document}