Euler's totient function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
{--

So! Good morning! (somewhere in the world, I'm sure. Midway-time, perhaps?)

We combine what we've experimented with in the last two days, coprimality and
prime factors so that we can work on these next set of exercises, which are
P34, P37, and P38 of the P-99 Prolog problem-set.

P34: Calculate Euler's totient function, phi m.

Euler's so-called totient function, phi m, is defined as the number of positive 
integers r (1 <= r < m) that are coprime to m.

Example: m = 10: r = 1,3,7,9; thus phi m = 4. Note the special case: phi 1 = 1.

Find out what the value of phi m is if m is a prime number. Euler's totient 
function plays an important role in one of the most widely used public key 
cryptography methods (RSA). In this exercise you should use the most primitive 
method to calculate this function (there are smarter ways that we shall discuss 
later). --}

phi :: Integer -> Int
phi m = undefined

{--

-- BONUS (or: 'now' is that 'later' mentioned just above) ---------------------

P37: Calculate Euler's totient function, phi m (improved).

See problem P34 for the definition of Euler's totient function. If the list of 
the prime factors of a number m is known in the form of problem P36 then the 
function phi m can be efficiently calculated as follows: 

Let [[p1,m1],[p2,m2],[p3,m3],...] be the list of prime factors (and their 
multiplicities) of a given number m. Then phi m can be calculated with the 
following formula:

phi m = (p1 - 1) * p1 ** (m1 - 1)
      * (p2 - 1) * p2 ** (m2 - 1)
      * (p3 - 1) * p3 ** (m3 - 1)
      * ...

[ed: added the bracketing of the multiplication to force exponentiation
over the entire multiple, as phi 10 does not work with the partial functions
x * (y ** z), but it does work with the partial function being (xy) ** z.

... No, that is not correct, either. Bonus-bonus, correct the prime-factors
phi-m formula. Ick.

hint: wikipedia may be your friend and mine. Maybe.] 

[edit: copy/paste error, corrected (+) to (*). Sry.]

--}

φ :: Integer -> Int
φ m = undefined

{--

P38: Compare the two methods of calculating Euler's totient function.

Use the solutions of problems P34 and P37 to compare the algorithms. Take the 
number of logical inferences [ed: or 'steps' or 'continuations' or 'function
applications'] as a measure for efficiency. Try to calculate phi 10090 as an 
example.

Let's try some numbers from random.org:

126953
236707
254727
787524
280556
53602
541784
356773
507242
349314

Run and time both phi and φ against the numbers above.

SWEET! (I added that, just by myself, because that's how I roll!)

A solution is available at http://lpaste.net/107972

 --}