**Paste:**#107955**Author(s):**1HaskellADay and geophf**Language:**Haskell**Channel:**-**Created:**2014-07-23 13:01:23 UTC**Revisions:**- 2014-07-23 19:39:43 UTC #107976 (diff): No title (1HaskellADay)
- 2014-07-23 16:21:47 UTC #107969 (diff): No title (geophf)
- 2014-07-23 13:40:38 UTC #107958 (diff): No title (geophf)
- 2014-07-23 13:29:27 UTC #107957 (diff): No title (geophf)
- 2014-07-23 13:19:01 UTC #107956 (diff): No title (geophf)
- 2014-07-23 13:01:23 UTC #107955: Euler's totient function (1HaskellADay)

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 --} |