And for a very small phi ...

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
import Control.Arrow
import Control.Monad

import Data.Time.Clock

import Analytics.Theory.Number         -- http://lpaste.net/107480

{--

A set of solutions to the Haskell exercise at http://lpaste.net/107955

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

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

 --}

phi :: Integer -> Int
phi = length . coprimesOf

coprimesOf :: Integer -> [Integer]
coprimesOf m = 1 : [2..pred m] >>= \x -> 
               guard (isCoprime x m) >> return x

{--

so:

*Main> coprimesOf 10
[1,3,7,9]

so, phi 10 ~> 4

*Main> coprimesOf 36
[1,5,7,11,13,17,19,23,25,29,31,35]

so, phi 36 ~> 12 as per wikipedia

 --}

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

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

{-- so, note: if the ms are always 1, then this reduces to

product (map pred (primeFactors m)), amirite? I'm so right!

φ :: Integer -> Integer
φ = product . coOf'

coOf' :: Integer -> [Prime]
coOf' = map pred . primeFactors

Nope. I'm wrong! :(

So, back to the above formula.

 --}

φ :: Integer -> Int
φ = fromInteger . product . coOf'

coOf' :: Integer -> [Prime]
coOf' = map phish . groupedPrimeFactors

phish :: (Prime, Int) -> Integer -- pronounced 'phi-ish' (liek: phi-like)

-- ... I intentionally misspelt leik, leik, ya know: leik.

phish (prime, exponent) =
   (prime `pow` (toInteger $ pred exponent)) * pred prime

-- so, should I have spelt 'phish' 'phiish' if I meant to to be pronounced
-- 'phi-ish' or is 'phish' just okay and ambiguous enough?

{--

so:

*Main> φ 10
4
*Main> φ 36
12

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

Discussion:

So, my primeFactors boils down to an (now) incremental linear over a
doubly-exponential function cost, then on top of that, we have a doubly-
linear scan (map and product), so this is the cost of φ m.

For phi m, this is singly exponential over m then singly exponential over
2 .. pred m (which is linear over singly exponential), THEN we do the
coprimality test (linear).

UGH! BOTH SO EXPENSIVE, but φ, of course, is less expensive, otherwise I
wouldn't have forced you through that exercise, right? Right? Amirite?

SO! phi and φ for 10090 .. both return instantly, so there's that.

('Damn! I'm good!' here or ... idk)

Let's try some numbers from random.org:

126953
236707
254727
787524
280556
53602
541784
356773
507242
349314

 --}

runFor :: FilePath -> (Integer -> Int) -> IO NominalDiffTime 
runFor file fn = 
   readFile file >>= return . map read . lines >>= \nums ->
   getCurrentTime >>= \start -> 
   mapM_ (print . (id &&& fn)) nums >> getCurrentTime >>= \stop ->
   return (diffUTCTime stop start)

{--

*Main> runFor "10.rnd" phi ~>
(126953,125268)
(236707,236706)
(254727,147600)
(787524,241920)
(280556,140276)
(53602,26800)
(541784,270888)
(356773,350668)
(507242,242572)
(349314,99792)
6.092052s

*Main> runFor "10.rnd" φ ~>
(126953,125268)
(236707,236706)
(254727,147600)
(787524,241920)
(280556,140276)
(53602,26800)
(541784,270888)
(356773,350668)
(507242,242572)
(349314,99792)
0.159344s

So, φ is 0.15 sec and phi is 6.1 sec.

WOOT! for φ

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

Okay, cool story for you, dear readers. I saw the vanity plate of a car some
time ago:

XIPSI

So I looked at the letters and said to the driver: "χξ? [khee-see]"

And he looked at me, utterly confused: "Huh?" he said, "That's my fraternity:
'tchai-puh-sigh'!"

"Ah," I said politely.

 --}
72:5: Warning: Redundant $
Found:
prime `pow` (toInteger $ pred exponent)
Why not:
prime `pow` toInteger (pred exponent)
122:4: Warning: Use liftM
Found:
readFile file >>= return . map read . lines
Why not:
liftM (map read . lines) (readFile file)