Problems on the Prolog 99 Problems: P34 and P37

[YauHsienHuang]

I took the famous Prolog exercises 99 Problems (
https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ ) and found some
problems. The 34th problem indicates that the Euler's totient function
phi(10) = 4, because smaller coprimes of 10 are 1, 3, 7, 9. The 37th
problem says that phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2
** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ..., where p_i is distinct
prime factor of m, and m_i is the times that p_i occurs in the list of
prime factors, and thus prime factors of 10 is [[2, 1], [5, 1]] and phi
(10) = (2-1) * 2 ** (1-1) + (5-1) * 5 ** (1-1) = 5. Why are these two
problem not concurrent?

My programs:

% range(2, 7, [2,3,4,5,6,7]).
range(M, N, []) :- M > N, !.
range(N, N, [N]) :- !.
range(M, N, [M|Z]) :- M1 is M + 1, range(M1, N, Z).

% is_prime(37): yes
factor(_, 0).
factor(1, _).
factor(N, M) :- M > 0, M1 is M - N, factor(N, M1).
factors(_, [], []) :- !.
factors(N, [X|Y], [X|Z]) :- factor(X, N), !, factors(N, Y, Z).
factors(N, [_|Y], Z) :- factors(N, Y, Z), !.
is_prime(N) :- range(1, N, X), factors(N, X, Z), Z == [1,N].

% coprime(2, 3): yes
coprime(M, N) :- 1 =:= gcd(M, N).

% coprimes(10, [1,2,3,4,5,6,7,8,9], [1,3,7,9]).
coprimes(_, [], []).
coprimes(N, [X|Y], [X|Z]) :- coprime(N, X), !, coprimes(N, Y, Z).
coprimes(N, [_|Y], Z) :- coprimes(N, Y, Z).

% totient_phi/2 indicated in P34
totient_phi(1, 1) :- !.
totient_phi(N, Z) :- N1 is N - 1, range(1, N1, X), coprimes(N, X, Y),
length(Y, Z).

% prime_factors_multi/2 indicated in P36
prime_factors_mult(N, [[N,1]]) :- is_prime(N), !.
prime_factors_mult(N, Z) :- N1 is N - 1, range(2, N1, X),
element_at(X, _, X1), is_prime(X1), N rem X1 =:= 0, N2 is N / X1,
prime_factors_mult(N2, [[Y,N3]|Z1]),
( X1 =:= Y, N4 is N3 + 1, Z = [[Y,N4]|Z1], !;
Z = [[X1,1],[Y,N3]|Z1]), !.

% prime_factors_mult/2 indicated in P37
phi(1, 1) :- !.
phi(N, Z) :- is_prime(N), !, Z is N - 1.
phi(N, Z) :- prime_factors_mult(N, [[P, M]|_]), X is (P-1)*P^(M-1),
N1 is N / (P * M), phi(N1, Y), Z is X + Y.

[Chip Eastham]

On Nov 11, 3:09 am, YauHsienHuang <g9414002.pccu.edu...@gmail.com>
wrote:

> I took the famous Prolog exercises 99 Problems
> (https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/)
> and found some problems. The 34th problem indicates
> that the Euler's totient function phi(10) = 4,
> because smaller coprimes of 10 are 1, 3, 7, 9.
> The 37th problem says that
> phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2
> ** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ...,
> where p_i is distinct prime factor of m, and m_i
> is the times that p_i occurs in the list of
> prime factors, and thus prime factors of 10 is
> [[2, 1], [5, 1]] and

> phi(10) = (2-1) * 2 ** (1-1) + (5-1) * 5 ** (1-1) = 5.

> Why are these two problem not concurrent?

I think you misunderstood the 37th problem.
There are no "+" signs involved in the
formula. Euler's phi function is called a
multiplicative function because phi(ab) is
equal to phi(a)*phi(b) when GCD(a,b) = 1.

regards, chip

[YauHsienHuang]

Ah, that is. Sorry for my misunderstanding.

Thank you.