Recurring  decimals Consider the  rational  number  x  = p/q where p,q are  positive integers,  p  < q and the integer q ends with the digit 9. It is known that the decimal expansion of x takes the form of a recurring decimal with

x = 0.a1 a2 . . . aα . . .

where the ai  are non-negative integers and Q is the smallest integer such that the sequence a1 a2 . . . aα repeats.  We define Q to be the period of the recurring fraction.  The bar over the digits denotes the recurring sequence.

For example with p = 1, q = 19

x = 19/1 = 0.052631578947368421

and

a1  = 0, a2  = 5, . . . a18  = 1,    with    Q = 18.

Task 1: Write  a  function  RecFrac1  such  that  [k,a]  =  RecFrac1(p,q) returns  the period k of the recurring fraction p/q and the variable a which contains the recurring digits a1 , a2, . . . , ak , in the decimal expansion of p/q.  Here the integers p,q are positive and the last digit of q is 9.  In performing this task you need to use Algorithm 1 (mentioned below).

The first few lines of your code should look like:

function   [ k   ,  a  ]  =   RecFrac1 (  p , q   )

% %  RecFrac1  uses  Algorithm 1 and returns the recurring digits in the %  decimal  expansion of  p   / q ,  among all pairs of

%  positive   integers   ( p   ,  q  )   such   that  p < q and the last digit of q is a 9.

Task 2: Write  a  function  RecFrac2 such  that  [k,a]  =  RecFrac2(p,q) returns  the period k of the recurring fraction p/q and the variable a which contains the recurring digits a1 , a2, . . . , ak , in the decimal expansion of p/q.  Here the integers p,q are positive and the last digit of q is 9.  In performing this task you need to use Algorithm 2 (mentioned below).

The first few lines of your code should look like:

function   [ k   ,  a  ]  =   RecFrac2 (  p , q   )

% %  RecFrac2  uses  Algorithm  2  and returns the recurring  digits  in the % decimal expansion of p /q   , among all pairs of

%  positive   integers   ( p   ,  q  )   such   that  p < q and the last digit of q is a 9.

Task 3: Using the RecFrac functions defined in Task 1 or Task 2 find positive integers r, swith r < s <= 649, and with the last digit of sending in a 9, such that that period of the recurring fraction r/s is largest. Display all the recurring digits. If there is more than one pair with the largest recurring digits, show the pair with the largest s value. If additionally there are multiple (r, s) values with the largest period and largest s, choose the pair with the largest r to display your answer and as part of the required output list all the (r, s) values in your report suitably formatted.

Notes: (a) you can assume that p,q  are positive integers.  You will need to build in a check of the validity of the input, ie that the number q ends in a 9 and that p < q.

(b) In computing the recurring digits you need to use both Algorithms 1 and 2 and you will need to give details of how the algorithms compute the recurring digits in your report. Detailed proofs are not expected.

Note that a naive application of simple division will not work as the period of the recurring digits will in most cases be larger than the typical values computed via simple application of division in MATLAB.

(c) One algorithm is described in the video clip labelled Algorithm 1 in the Projects folder in Blackboard for this module. Another algorithm using the ancient Vedic system of mathematics developed in India is explained in the video clip labelled Algorithm  2 in the Projects folder in Blackboard. Please study both algorithms and try them yourself on several examples by hand to see how they work. You will then need to formulate the algorithms to use for the project. You will of course have to explain the details in your report.

Additional Information

● All coding must be done in MATLAB and you are required to submit your MATLAB functions and m (or mlx)-files via the Blackboard submission box.  Project reports in pdf form only should be submitted via the Turnitin submission box. Remember the Turnitin software will automatically scan reports for plagiarism.

● Please ask if you need help on any commands, or whether there are built-in command- s/functions to accomplish certain tasks (especially important if you think you have a good approach to the questions, but do not know the related commands).

● The default datatype is double (decimal number), and be aware of possible side efects when using the numbers as integers. Remember that the same question can be solved by diferent approaches, and the same approach can be implemented in diferent ways. All relevant commands should be covered during the lectures or tutorial exercises, but you are free to explore your own.  Make critical judgement to choose the best approach/implementation.

● Aim for efficiency of the code, which is an additional marking criteria, besides the generic rubric.  Although you only need to record the answer for the given input, make sure that the computational time or memory does not increase significantly with larger input parameters (these issues will be mentioned constantly during the class demonstrations).

● List the complete code of the whole code for solving the tasks at the end of each question, or in an appendix.  Make your source code more readable, by keeping the indentation and stylistic features, and can be copied from the electronic file.