COMP1730/6730 2023 Semester 1, Project- 1 (Mathe-matics)

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 =  , 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 =   = (0.β1 β2 β3 . . .)β ,    0 ≤ β i < β , Ai,

(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  or , 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

 = 0.6363636363 . . . ,   period T = 2,

or

 = 0.001010101010101010 . . . ,   period T = 2,

or

 = 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  has this expansion in the base 4:

 = 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 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: 3624360069  and  123456789012

And sometimes, the walks show surprising regularity. For example, for two integers

M  =  1049012271677499437486619280565448601617567358491560876166848380843144358447252875551     62924702775955557045371567931305878324772977202177081818796590637365767487981422801328592     0278610192581409571357487047122902674651513128059541953997504202061380373822338959713391954

N  =  1612226962694290912940490066273549214229880755725468512353395718465191353017348814314     01750453996944547935301206438332726709700793305262920303509209736004509554561365966493250     7839146477284016238565137429529453089612268152748875615658076162410788075184599421938774835

the rational Q =  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).

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 ()10  the prefix was

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  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 , 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 Simpsonwhich should give some idea that the topics we discuss in this assignment are related to the Fourier analysis).

References

1.“Walking on Real Numbers”, by Francisco J. Aragon Artacho, David H. Bai- ley, Jonathan M. Borwein, and Peter B. Borwein, Mathematical Intelligencer, 2012, https://link.springer.com/article/10.1007/s00283-012-9340-x, DOI 10 . 1007/s00283 -012 -9340 -x