Week 2: Exercises

1. Greatest Common Denominator

Write a predicate gcd(A, B, C) that is true if C is the greatest common denominator of A and B.

2. Smallest Prime Factor

Write a predicate smallest_factor(N, P) that is true if P is the smallest prime factor of N.

3. Number of Prime Factors

Write a predicate num_factors(A, N) that is true if A has exactly N prime factors, where repeated factors are counted separately. For example, num_factors(12, 3) is true since 12 = 2 x 2 x 3.

4. Between

Write a predicate between(+Low, +High, ?N) that is true if N is an integer between Low and High, inclusive.

5. s(s(s(X)))

(Bratko, ex. 2.6)

Consider this program:

f( 1, one).
f( s(1), two).
f( s(s(1)), three).
f( s(s(s(X))), N) :- f(X, N).

What answer(s) will these queries produce?

```
f( s(1), A).
```
```
f( s(s(1))), two).
```
```
f( s(s(s(s(s(s(1))))))), C).
```
```
f( D, three).
```

6. Member

Write a predicate member(X, L) that is true if X is an element of the list L.

7. Last

Write a predicate last(X, L) that is true if X is the last element of list L.

8. Append

Write a predicate append(L, M, N) that is true if N is the concatenation of lists L and M.

9. Delete

Write a predicate del(X, L, L1) that is true if L1 is the list L with item X removed (at any position).

Homework Exercise 1: Distinct Factors

Write a Prolog predicate distinct_factors(+N, ?F) which is true if the integer N has exactly F distinct prime factors.

For example, distinct_factors(252, 3) is true because 252 = 2 x 2 x 3 x 3 x 7, so it has 3 distinct prime factors (i.e. 2, 3, 7).

Homework Exercise 2: Disjoint Split

Write a Prolog predicate split(?L, ?M, ?N) which is true if L can be split into two disjoint subsequences M and N. A subsequence must contain elements in the same order as in the original list L.

For example,

split([a, b, c, d, e, f], [a, c, d, f], [b, e])

is true, since [a, c, d, f] and [b, e] are subsequences of L = [a, b, c, d, e, f], and together they contain all the elements of L.

To keep things simple, you may assume that all elements of L are distinct.

Homework Exercise 3: Merge Without Duplicates

Write a Prolog predicate merge(+L1, +L2, ?M) that merges two sorted lists of numbers L1 and L2 into a sorted list M, combining duplicates into a single element.

For example,

merge([2, 5, 8, 8, 10], [3, 5, 6, 7, 8, 11, 15], L)

will yield L = [2, 3, 5, 6, 7, 8, 10, 11, 15].