Tutorial Problem Set 1

CS 152 – 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.

## Reviews

There are no reviews yet.