Assignment 2

Suppose that you are given a positive proper fraction a/b. Your problem is to write this fraction as

where

For example, consider the representations of the following two fractions:

Here is how such a representation can be computed. Follow an iterative procedure, where in each iteration the fraction a/b is decreased by 1/n for a suitable value of n. This value is chosen to be the positive integer satisfying the following:

Repeat the process until the fraction a/b reduces to zero.

Write a program that reads two integers a,b so that a/b is a positive proper fraction. Apply the above iterative algorithm. During each iteration, report the value of n for which 1/n is subtracted.

Report the output of your program on the following four fractions.

   11/31
   17/34
   17/53
   41/43

As a bonus exercise you may try running your program on the fraction 71/73. Use a calculator to check if your program gave the correct result. I believe it didn't!

Sample output

   Supply a proper positive fraction.
   Enter the numerator   : 4
   Enter the denominator : 9
   The sequence of values of n is: 3 9

   Supply a proper positive fraction.
   Enter the numerator   : 11
   Enter the denominator : 89
   The sequence of values of n is: 9 81 7209

Theoretical questions (Not for submission)

Mathematically inclined students may try to answer the following questions.

• Does the above algorithm print the values of n in strictly increasing order?

• Is the above algorithm guaranteed to terminate after only a finite number of iterations?

• If yes, what is the maximum number of iterations that may be required? If not, provide an example for which the algorithm does not terminate.

---

[Submission site] [Lab home] [Course home]