Week 3: Exercises

1. Reverse

Write a predicate reverse(L, M) that is true if M is the reverse of the list L.

2. Addition

Suppose that we represent natural numbers using structures: 0 = z, 1 = s(z), 2 = s(s(z)) and so on.

Write a predicate sum(I, J, K) that is true if I + J = K, where I, J, and K have this numeric representation. Your predicate should work in all directions.

3. Multiplication

Extending the previous exercise, write a predicate mul(I, J, K) that is true if I · J = K, where I, J, and K have this numeric representation. Your predicate should work in all directions.

4. Integer Sum

Write a predicate sum(L, N) that is true if N is the sum of the integers in the list L.

5. Real Sum

Write a predicate sum(L, R) that is true if R is the sum of the floating-point numbers in the list L.

6. Ordered List

Write a predicate ordered(L) that is true if the floating-point numbers in L are in non-decreasing order.

7. Time Difference

Let the structure time(H, M, S) represent the 24-hour time H:M:S, where H, M, and S are integers. Write a predicate plus(T, N, Q) that is true if time T plus N seconds equals time Q. Your predicate should work in all directions.

8. Factorial

Write a predicate factorial(N, F) that is true if F = N! . Your predicate should work in all directions and should terminate when the solution set is finite.

9. Sum of First N Elements

Write a predicate sum_n(N, L, S) that is true if S is the sum of the first N elements of L. If L has fewer than N elements, the predicate should fail.

10. Slice

Write a predicate slice(L, I, J, M) that is true if M contains elements I .. J of L, where elements are indexed starting from 1. For example, slice([r, i, v, e, r], 2, 4, [i, v, e]) is true.

11. Day Count

Write a predicate total_days(Y, Z, N) that is true if N is the total number of days in the years Y .. Z. Assume that 1900 < Y, Z < 2100 (which makes leap year calculations easier).

12. Day Count, Extended

Extend the previous exercise so that it correctly computes the count for any years in the Gregorian calendar.

13. Greatest Common Divisor

Write a predicate gcd(I, J, K) that is true if the greatest common divisor of I and J is K.

14. Prime

Write a predicate is_prime(N) that is true if N is prime.

15. All Primes

Write a predicate all_primes(I, J) that returns a list of all prime numbers between I and J, inclusive.

16. Smallest Prime Factor

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

17. Drop Every Nth

Write a predicate drop(L, N, M) that is true if we can remove every Nth element from L to make M. For example, drop([a, b, c, d, e, f, g], 3, [a, b, d, e, g]) is true.

18. 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.