Problem Set 1– Abstractions and Paradigms

Tutorial Problem Set 1
Abstractions and Paradigms in Programming

1. Write a function (has-solution a b c) which returns #t if the diophantine equation
ax + by = c has integer solutions for x and y.
2. Write a function (sub x y) which subtracts y from x. You can assume that x is larger than
y. Define sub in terms of an appropriate function (sub-single x y z) with constraints
on the values of x, y, and z. The function should check these constraints. You can also
use the function convert to left-shift and add.
3. Write a function (ak-mult x y) to multiply two numbers using the Al-Khwarizmi method.
The function should never run out of memory, however large x and y may be. Look at
section 1.2.1 of SICP for inspiration.
4. Define a function (div x y), y 6= 0, which will return a pair of numbers (q, r) such that
x = yq + r and 0 ≤ r < y. Like Al-kharizmi’s method, this should also work by repeated
halvings of x. For this problem and some of the later ones, use the magic function cons
to pack a pair of numbers and the functions car and cdr to extract the first and second
component of the pair.
5. Given two numbers a and b, write a function (coeffs a b) which will return a pair of
integers x and y such that ax + by = gcd(a, b).
6. Given two integers x and n and an integer exponent y, write a function (modexp x y n)
which will output: x
y mod n.
7. A Carmichael number is a composite number p, such that for every co-prime in the range
1 ≤ a < p, a
(p−1) ≡p 1. Define a function (carmichael n) which will give the nth
Carmichael number.
8. Write a function (inverse e n) which will return the inverse of e, modulo n.
9. Write a function (is-prime n) to implement the Fermats little theorem based probabilistic
algorithm to test whether n is a prime. Assume that n is not a Carmichael number. Use
the function (random k) to generate a random number in the range 0 . . . k − 1.
10. Goldbachs 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 seeming fact
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. Write a function (goldbach m) to find
the two prime numbers that sum up to a given number m.