Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP1730/6730 Mathematics
The assignment is an exercise in elementary mathematics which, however, has interesting
connections with computing and information theory. This project will be suitable
to COMP6730 students, or for Honours students studying Science and Mathematics.
Background knowledge (or additional research) regarding the number representation
in different bases will be needed, as well as elementary geometry of periodic lattices. The
estimated size (including the code comments and docstrings) is approximately 250–300
lines of code. The time effort is about 15 hours.
The problem
Consider a rational number Q = MN , M < N which when expanded in a basis β , is
described by a periodic sequence of digits. The digits, βi are bounded by 0≤ βi < β :
Q =
∞∑
i=1
β i
β i
= (0.β1β2β3 . . .)β , 0≤ β i < β , ∀i,
(do not be confused with notations (0.β1β2 . . .)β — it is a generalisation of the
decimal expansion like (0.123456 . . .)10 where the base value 10 is usually omitted).
The sequence βi is periodic: βi+T = βi starting from some number N : i ≥ N . For
some rationals (like 14 or
17
150 , which are expanded in base 10 as follows: 0.250000 . . .
and 0.1133333333333 . . .), the period T=1. These kind of rationals are not very
interesting. Rationals with longer expansion period, for example, are
7
11
= 0.6363636363 . . . , period T = 2,
or
1
990
= 0.001010101010101010 . . . , period T = 2,
or
1
117
151
= 0.77483443708609271523178 . . . , period T = 75,
One may consider a simple problem of finding the period of expansion of a rational
number in the base β . You may take it as a warming up example. But more
interesting numerical studies emerge when we consider a particular expansion base
β = 4.
When the base of expansion is 4, the digits take 4 possible values 0,1,2,3 which
can be considered as the directions of discrete step walks – “East”, “North”,
“West” and “South”. When we accept the interpretation, each rational number will
be represented by a two-dimensional walk on a plane. Each step of the walk has a
length of 1, and the direction of the n-th step corresponds to the n-th digit of the
decimal in base 4. For example, the number 711 has this expansion in the base 4:
7
11
= 0.2202322023 . . . , period T = 5.
The 100 step walk which this number generates looks like this
Figure 1: “Seven-11” walk
here the directions are chosen as {0: "East", 1: "North", 2: "West", 3:
"South"}, and the colour-coding is used to show the “time” of steps (the further the
2
time step from the start the redder is the colour — “the red shift”, like in Universe
expansion).
Sometimes, walks look like random. For example the walks on Fig. 2 are created by
two pairs of relatively small integers, the length is 250,000 in both cases:
Figure 2: Pseudo-random walk on “small” numbers: 36243600697000000001 and
123456789012
1000000000061 .
3
And sometimes, the walks show surprising regularity. For example, for two integers
M = 1049012271677499437486619280565448601617567358491560876166848380843144358447252875551
62924702775955557045371567931305878324772977202177081818796590637365767487981422801328592
0278610192581409571357487047122902674651513128059541953997504202061380373822338959713391954
N = 1612226962694290912940490066273549214229880755725468512353395718465191353017348814314
01750453996944547935301206438332726709700793305262920303509209736004509554561365966493250
7839146477284016238565137429529453089612268152748875615658076162410788075184599421938774835
the rational Q = MN generates a regular walk, which is also periodic, Fig. 3. (Do not
confuse a periodic walk with a periodic expansion — the walk may not be periodic,
but the expansion always is. For the walk to be periodic, it must return to the point
of origin after the number of step which is integer factor of the expansion period.)
Figure 3: A 440 step base-4 walk on the number Q.
There are more examples of such remarkably regular number walks, and some
mathematical theory behind this phenomenon. But we shall not pursue it further (if
you like, one can learn about it in Ref. 1). Instead, we will build programming tools
to explore these behaviours.
The choice of directions is somewhat arbitrary. For consistency, we shall assume
that the East direction corresponds to the value βi = 0, and that other directions are
chosen in the anti-clockwise order (βi = 1 corresponds to North, and so on).
4
It is interesting to note, that base-4 walks can be also generated using RNA/DNA
sequences (which is a subject of study in Project-3). We cannot say whether such
walks have any significance in the bioinformatics research, though.
Another consideration is about reversing the process of generating a walk from the
number. Ask yourself — how were numbers like Q in the above example found? If
we encode a trajectory which generates a target shape and use it as an expansion,
we will be able to compute the rational number, given by the this expansion. In
other words, if we know the shape (and its trajectory), we can calculate the rational
number.
The programming tasks
This is what you will have to do in your program:
1. Define a function which accepts a 2-tuple comprising a numerator and a
denominator, and a base of the numeral system in which to expand the rational
number, and returns the period of the expansion sequence.
2. Define a function which accepts a 2-tuple of integers, a numerator and denom-
inator representing a rational number, the base value and the positive integer
nsteps, and returns the sequence of the expansion digits of this rational of the
total length nsteps.
3. Using the plotting library matplotlib, create a walk which a rational (defined
by a 2-tuple of integers) generates on a square lattice.
4. A sequence representing a rational number expansion in the base β can be
written as a prefix sequence (in the above example
17
150
10 the prefix was
11) concatenated with a period sequence which is repeated infinitely (in the
same example, it was a single element sequence 3). A prefix can be an empty
sequence, a period sequence can consist of zeros (the example 14 above).
Write a function that is passed a sequence prefix, a sequence period and
a base b, which will return a 2-tuple of mutually prime integers to uniquely
represent a rational. Again using the example of rational 17150 , the asked
function should return (17,150) when the prefix (1,1), the period sequence
(3,) and the base 10 are passed for arguments.
5. Compute rationals which generate sample walks – a square, a circle (adopt a
discrete approximation of your choice), a figure “8”, Ying-Yang or some other
of your own choosing (for example, you can generate Homer Simpson which
should give some idea that the topics we discuss in this assignment are related
to the Fourier analysis).