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