E-99: 31-40

Source

Right on the heals of 21-30 comes 31-40. These problems began to delve into mathematics, with a great emphasis on prime numbers and their generation. Quite interesting to work with, since prime numbers are the basis behind encryption of any non-trivial strength. Enjoy:

%% Determine whether a given integer number is prime. %% Example: (is-prime 7) -> T p31(2) -> true; p31(N) when N rem 2 : 0 -> false; p31(N) -> p31is\prime(N, 3, N div 2 ). p31is\prime(\N, K, Limit) when K > Limit -> true; p31is\prime(N, K, Limit) -> case N rem K of 0 -> false; \Else -> p31is\prime(N, K+2, Limit) end. %% Determine the greatest common divisor of two positive integer numbers. %% Use Euclid's algorithm. %% Example: (gcd 36 63) -> 9 p32(A, 0) -> A; p32(A, B) when B > A -> p32(B, A); p32(A, B) -> p32(B, A rem B). %% Determine whether two positive integer numbers are coprime. %% Two numbers are coprime if their greatest common divisor equals 1. %% Example: (coprime 35 64) -> T p33(A, B) -> p32(A, B) : 1. %% 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. %% (totient-phi 10) -> 4 %% Find out what the value of phi(m) is if m is a prime number. %% psuedo-code if is\prime(m), phi(m) = m-1, else compute phi(m). %% 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). p34(1) -> 1; p34(M) -> p34totient\phi(M, 1, []). p34totient\phi(M, M, L) -> length(L); p34totient\phi(M, R, L) -> case p33(M, R) of true -> p34totient\phi(M, R+1, [R | L]); false -> p34totient\phi(M, R+1, L) end. %% Determine the prime factors of a given positive integer. %% Construct a flat list containing the prime factors in ascending order. %% Example: (prime-factors 315) -> (3 3 5 7) p35(N) -> p35prime\factors(N, 2, []). p35prime\factors(1, \C, PF) -> lists:reverse(PF); p35prime\factors(N, 2, PF) -> case (N rem 2) : 0 of true -> p35prime\factors(N div 2, 2, [2 | PF]); false -> p35prime\factors(N, 3, PF) end; p35prime\factors(N, C, PF) -> case (N rem C) : 0 of true -> p35prime\factors(N div C, C, [C | PF]); false -> p35prime\factors(N, C+2, PF) end. %% Determine the prime factors of a given positive integer (2). %% Construct a list containing the prime factors and their multiplicity. %% Example: (prime-factors-mult 315) -> ((3 2) (5 1) (7 1)) %% Hint: The problem is similar to problem P13. p36(N) -> p10(p35(N)). %% 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)] + … %% Note that a * b stands for the b'th power of a. p37(M) -> p37phi(p36(M), 1). p37phi([], Phi) -> Phi; p37phi([[M, P] | L], Phi) -> p37phi(L, Phi * (P - 1) * round(math:pow( P, M-1 )) ). %% 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 as a measure for efficiency. Try to calculate phi(10090) as an example. p38(M) -> {T34, V34} = timer:tc(lp, p34, [M]), {T37, V37} = timer:tc(lp, p37, [M]), io:fwrite("p34 took ~p micro seconds and returned ~p.~n", [T34, V34]), io:fwrite("p37 took ~p micro seconds and returned ~p.~n", [T37, V37]). %% A list of prime numbers. %% Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range. p39(High) -> p39(1, High). p39(Low, High) when Low > High -> p39(High, Low); p39(Low, High) -> [X || X < - p39primes(lists:seq(2, High) , [1]), X >= Low, X =< High]. p39primes([], Primes) -> lists:reverse(Primes); p39primes([1 | Sieve], Primes) ->      p39primes(Sieve, [1 | Primes]); % pops 1 off the sieve p39primes([2 | Sieve], Primes) ->      p39primes([X || X < - Sieve, (X rem 2) > 0], [2 | Primes]); % pops 2 off the sieve and removes all multiples of 2 p39primes([Curr | Sieve], Primes) -> p39primes([X || X < - Sieve, (X rem Curr) > 0], [Curr | Primes]). % pops the next value off the sieve and removes all multiples %% Goldbach's conjecture. %% Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. %% Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. %% It has been numerically confirmed up to very large numbers (much larger than we can go with our Prolog system). %% Write a predicate to find the two prime numbers that sum up to a given even integer. %% Example: (goldbach 28) -> (5 23) p40(N) -> p40goldbach(N, p39(N), []). p40goldbach(0, \Primes, Result) when length(Result) : 2 -> lists:reverse(Result); p40goldbach(N, \Primes, Result) when length(Result) : 2, N / 0 -> false; p40goldbach(\N, [], \Result) -> false; p40goldbach(N, [P | Primes], Result) -> Sol = p40goldbach(N-P, Primes, [P | Result]), case is\list(Sol) of true -> Sol; \else -> p40goldbach(N, Primes, Result) end.