Adventures in Prolog - Some more Primes

Again, we are going to tackle some problems mentioned in the list of 99-Prolog problems. Today's post builds upon the gcd predicate defined last time to attack problems:

• P31 = is_prime


• P35 = prime_factors


• P36 = prime_factors_mult


• P39 = prime_list

Now, building on the previously defined gcd predicate, on may define a prime inductively:

• a prime is a number which is only (divisible by one and itself)


• the smallest prime is 2


• any number greater than 2 is either composite or prime

Building on this definition we may translate the smallest prime into a Prolog predicate quite easily. To determine the primeness/composibility of any number greater than 2, one may use the gcd predicate. Recalling that a prime p is a number which cannot be divided by any number in ]1, p[, the following predicate may be given:

is_prime(2) :- !.
is_prime(3) :- !.
is_prime(X) :-
  X >= 2,
  UpperBound is round(sqrt(X)) + 1,
  is_prime_t(X, 2, UpperBound), !.

is_prime_t(_, UpperBound, UpperBound).
is_prime_t(X, CurrentFactor, UpperBound) :-
  gcd(X, CurrentFactor, GCD),
  GCD = 1, !,
  NewFactor is CurrentFactor + 1,
  is_prime_t(X, NewFactor, UpperBound).

As can be seen above, two elementary cases (2 and 3) are given and any number not 2 or 3 is checked for primeness. Instead of checking composibility of a prime p for any number in ]1, p[, one may use any number in ]1, square_root(p)]. The reason why I used the rounded value of the square root + 1 is the case of checking 4 which would be determined as a prime because of:

is_prime_t(4, 2, 2).

Instead of the + 1, we might also a check on whether some number is even. Since we know that 2 is not only the smallest prime but also the only even prime number, such a check might greatly enhance the solution search.

Using this definition of is_prime, we might define the prime_list predicate quite easily. A prime list is generated from any number within some interval [a, b], which is prime. We might differentiate three cases (where the last is for convenience) in the definition of prime_list:

1. the interval is [a,b] where a=b


2. the interval is [a,b] where a<b


3. the interval is [a,b] where b<a

Case one results in a list containing one prime if a is itself a prime number. Case 3 will be mapped to case 2 where a and b are switched. This results in a possible prime_predicate as follows:

prime_list(X, X, [X]) :-
  is_prime(X), !.

prime_list(X, X, []) :- !.

prime_list(X, Y, L) :-
  X > Y,
  prime_list_t(Y, X, [], L), !.
 
prime_list(X, Y, L) :-
  prime_list_t(X, Y, [], L), !.
 
prime_list_t(X, X, CurrentPrimes, OutPrimes) :-
  is_prime(X), !,
  append(CurrentPrimes, [X], OutPrimes);
  OutPrimes = CurrentPrimes.

prime_list_t(X, Y, CurrentPrimes, OutPrimes) :-
  is_prime(X), !,
  append(CurrentPrimes, [X], NewPrimes),
  Z is X + 1,
  prime_list_t(Z, Y, NewPrimes, OutPrimes).
 
prime_list_t(X, Y, CurrentPrimes, OutPrimes) :-
  Z is X + 1,
  prime_list_t(Z, Y, CurrentPrimes, OutPrimes).

The last problem to cover is the prime factorization of some given number. This problem is handled by the two predicates prime_factors and prime_factors_mult. Where the first contains each (possibly duplicate) prime factor and prime_factors_mult delivers a power representation of the prime factors of some given number. The approach taken is quite simple, again the factorization of a prime number contains itself (and one which is not included). Also, any composite number can be represented uniquely by a product of prime factors. For example, 4 = 2 * 2 or 12 = 2 * 2 * 3. Now, provided this property of a natural number we may define our two predicates like this:

prime_factors(0, []) :- !.
prime_factors(1, []) :- !.
prime_factors(X, [X]) :- is_prime(X), !.
prime_factors(X, Out) :-
  prime_factors_t(X, 2, [], Out), !.
  
prime_factors_t(1, _, Out, Out).

prime_factors_t(X, TestFactor, CurrentFactors, Out) :-
  gcd(X, TestFactor, GCD),
  GCD \== 1, !,
  append(CurrentFactors, [GCD], NewFactors),
  Z is X / TestFactor,
  prime_factors_t(Z, TestFactor, NewFactors, Out).
  
prime_factors_t(X, TestFactor, CurrentFactors, Out) :-
  NewTestFactor is TestFactor + 1,
  prime_factors_t(X, NewTestFactor, CurrentFactors, Out).
  
prime_factors_mult(0, []) :- !.
prime_factors_mult(1, []) :- !.
prime_factors_mult(X, [X]) :- is_prime(X), !.
prime_factors_mult(X, Out) :-
  prime_factors_mult_t(X, 2, 0, [], Out), !.

prime_factors_mult_t(1, _, _, Out, Out).
prime_factors_mult_t(X, X, CurrentPower, CurrentFactors, Out) :-
  Power is CurrentPower + 1,
  append(CurrentFactors, [[X, Power]], Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  gcd(X, TestFactor, GCD),
  GCD \== 1, !,
  NewPower is Power + 1,
  Z is X / TestFactor,
  prime_factors_mult_t(Z, TestFactor, NewPower, CurrentFactors, Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  Power >= 1,
  append(CurrentFactors, [[TestFactor, Power]], NewFactors),
  NewTestFactor is TestFactor + 1,
  prime_factors_mult_t(X, NewTestFactor, 0, NewFactors, Out).

prime_factors_mult_t(X, TestFactor, Power, CurrentFactors, Out) :-
  Power = 0,
  NewTestFactor is TestFactor + 1,
  prime_factors_mult_t(X, NewTestFactor, 0, CurrentFactors, Out).

Essentially, prime_factors_mult performs the same steps as prime_factors. However, instead of creating a list for some prime factor right from the beginning, the power of that prime factor is accumulated and stored at last.

Happy, Prolog-ing and if you find any errors/typos please report them.

Adventures in Prolog - GCD and Coprime

Today's post follows the tradition of the my last post, i.e. it continues with another problem stated in the list of 99 Prolog problems. Today, we are going to have a look at problem 32 and 33.

Problem 32 concerns the implementation of a greatest common divisor predicate (gcd). In an earlier post, I implemented a gcd routine in Python. We are going to reuse this definition of gcd here, using a ternary predicate/relation.

The Prolog definition of gcd makes use of gcd's recursive definition, which are:

1. the gcd of two numbers x and y is equal to the gcd of x - y and y for y <>
2. the gcd of some number and 0 is the number
3. the gcd of some number and 1 is 1

Now, given the above properties (and some more) a possible gcd predicate might look like this:

gcd(A, 0, A) :- !. %includes gcd(0,0)
gcd(1, _, 1) :- !.
gcd(A, A, A) :- !.

gcd(A, B, GCD) :-
  A < B, !,
  X is B - A,
  gcd(X, A, GCD).

gcd(A, B, GCD) :-
  X is A - B,
  gcd(X, B, GCD).

Provided the above definition of gcd, the solution to problem P33 is given within the problem statement. For this, a predicate to determine coprimality may be defined as is:

coprime(X, X) :- fail.
coprime(X, Y) :- gcd(X, Y, 1).

Clearly, we could add more clause to avoid a computation of gcd when it is obviously not necessary. However this was omitted here.

Adventures In Prolog - Duplicate List Members

Today's post is about problem 14 from the list of 99 Prolog problems (see here):

(*) Duplicate the elements of a list.
Example:
?- dupli([a,b,c,c,d],X).
X = [a,a,b,b,c,c,c,c,d,d]

Since the problem is marked with one star, a solution should be within reach. Now, to duplicate each element of the list, we do the following:

1. We traverse the list element by element until we reach the last element, i.e. the empty list.


2. For each element (excluding the empty list), the element is added twice to a newly built output list.

Given the above solution statement, a possible translation to Prolog code might look like this:

dupli([], []).
dupli(L, O) :-  dupli_t(L, [], O).

dupli_t([], Current, Current).
dupli_t([H|T], CList, OutList) :-  
  append(CList, [H, H], IntermediateList),  
  dupli_t(T, IntermediateList, OutList).