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.a1a2 . . . aα . . .
where the ai are integers and α is the smallest integer such that the sequence a1a2 . . . aα
repeats. We define α 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 =
1
19
= 0.052631578947368421
and
a1 = 0, a2 = 5, . . . a18 = 1, with α = 18.
Task 1: Write a function RecFrac1 such that [k,a] = RecFrac1(p,q) returns the
period k of the recurring fraction 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 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, s with r < s <= 449, and with the last digit of s ending 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
1
additionally there are multiple (r, s) values with the largest period and largest s, choose one
pair 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 m-files via
Blackboard.
� 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 effects
when using the numbers as integers. Remember that the same question can be solved
by different approaches, and the same approach can be implemented in different 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 function 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. Your result should be
reproducible from the code attached.
2
3