E-99: 31-40
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.