A Fresh Look at Number

by Jay Kappraff* and Gary W. Adamson**

New Jersey Institute of Technology, Newark, NJ, Kappraff@aol.com* ,

P.O. Box 124571,   San Diego, CA 92112 - 4571**

Abstract

A hierarchy of rational numbers is derived from the integers and shown to be related to naturally occurring resonances. The integers are also related to the Towers of Hanoi puzzle. Gray code is introduced as a tool to aid in understanding Towers of Hanoi and also used to predict the symbolic dynamics of the logistic equation of dynamical systems theory. The Towers of Hanoi and Gray code are both generalized to number systems base n and used to derive a probability density function for the divisibility of integers. The number system base 4 expressed in generalized Gray code is shown to be a natural framework for the representation of the 64 codons of DNA. Finally,  a  new algorithm is presented to compute the value of continued fractions with repeating indices.

1. Introduction

What do the divisibility properties of the positive integers have to do with the Towers of Hanoi puzzle, Gray code, dynamical systems theory, and the structure of DNA? This paper explores these relationships.

2. A Natural Hierarchy of Numbers

It is not commonly known that when one counts the positive integers one also counts a hierarchy of rational numbers, 0 < p/q < 1, in lowest terms in which the "most important" rational numbers appear higher on the list. Our meaning of "most important" will be defined below, but first we describe a procedure for determining location of a number in the hierarchy by giving an example. What is the 19th rational number in this hierarchy? To answer this, first write 19 in binary, i.e, 19 = (10011)2. Next duplicate the last digit and separate the contiguous 1s and 0s as follows:

1 00 111 corresponds to [1,2,3]

where the numbers in brackets are the number of 1s and 0s in each contiguous group, i.e., 1 one, followed by 2 zeros, followed by 3 ones.

The numbers in brackets are the indices of the continued or compound fraction expansion [1],[2] of the 19th rational number in the hierarchy, i.e.,

19 corresponds to [1,2,3] =1/ (1+1/(2+1/3)) = 1/1+1/2+1/3= 7/10

Note that the boldface indices appear as elements of the continued fraction and that the second representation is a shorthand form of the first. Given its indices, the continued fraction can be rapidly evaluated by the procedure given in Appendix A.

While continued fractions with a finite number of indices represent rational numbers, continued fractions with an infinite number of indices represent irrational numbers.  However, if the sequence of indices for a rational number are repeated in a periodic manner, i.e.,

[a1,a2,,an,a1,a2an,] = [a1,a2an]¥

a special class of irrational numbers are generated, one for each rational number.  These irrational numbers can be determined by a surprisingly simple algorithm based on generalizations of the golden mean due to Adamson and given in Appendix B

The following algorithm determines the rational number corresponding to any integer of the hierarchy.

Algorithm 1:

a) Write the number in binary.

b) Duplicate the last digit and write the numbers of 0s and 1s in each contiguous group, referred to as the indices, beginning from left to right.

c) These are the indices of the continued fraction expansion of the rational number in lowest terms, i.e.,

p/q = [a1,a2,,an] =   1/a1 +1/ a2 +  + 1/an

Note that [a1,a2,,an] = [a1,a2,,an-1,1] for an>1. By duplicating the last digit of the binary notation we have chosen the first rather than the second representation. The procedure for determining the rational number corresponding to a given integer can also be carried out in reverse by using the Euclidean Algorithm to determine the indices of the continued fraction of a given rational number (see Appendix C), and then working backwards to the corresponding integer. Using this algorithm 1/2 = [2] corresponds to the integer 1 after eliminating the duplicated last digit. Therefore 1/2 sits atop the hierarchy. Table 1 lists the first 15 numbers in the hierarchy. In this Table, the 2n-1 integers with n digits are grouped in blocks and their corresponding rational numbers have continued fraction representations with indices that sum to n+1, e.g, there are 8 integers with 4 digits whose corresponding rationals have indices that sum to 5.

Table 1.
A Hierarchy of Rational Numbers and their Representations as
Binary, Gray Code, and Tower of Hanoi Positions

 N Binary Gray Moduli Indices Fraction Pegs A B C TOH 3210 0 0 0 [0] 0/1 (Start) 1/2/3... 1 1 1 0 [2] 1/2 1 1 2 10 11 1 [1,2] 2/3 1 2 2 3 11 10 0 3 [3] 1/3 1/2 1 4 100 110 2 [1,3] 3/4 3 1/2 3 5 101 111 0 3 [1,1,2] 3/5 1 3 2 1 6 110 101 1 5 [2,2] 2/5 1 2/3 2 7 111 100 0 3 [4] 1/4 1/2/3 1 8 1000 1100 3 [1,4] 4/5 1/2/3 4 4 9 1001 1101 0 3 [1,2,2] 5/7 2/3 1/4 1 10 1010 1111 1 5 [1,1,1,2] 5/8 2 3 1/4 2 11 1011 1110 0 3 [1,1,3] 4/7 1/2 3 4 1 12 1100 1010 2 7 [2,3] 3/7 1/2 3/4 3 13 1101 1011 0 3 [2,1,2] 3/8 2 1 3/4 1 14 1110 1001 1 5 [3,2] 2/7 1 2/3/4 2 15 1111 1000 0 3 [5] 1/5 1/2/3/4 1

It should be noted that, strictly speaking, it is the blocks in Table 1 that are ordered in the hierarchy. Within each block there is no strict ordering of "importance," e.g., in block 4, 3/4 is no more "important" than 1/4, 3/5, or 2/5. The numbering of rational numbers within each block of Table 1 follows the well-known Farey sequence shown in Table 2 [2],[3], [4].

Table 2.
Farey Sequence

 0/1 1/1 Row 0 1/2 Row 1 1/3 2/3 Row 2 1/4 2/5 3/5 3/4 Row 3 1/5 2/7 3/8 3/7 4/7 5/8 5/7 4/5 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

In this table each rational number is generated from the two that brace it from above by adding numerators and adding denominators of this pair, e.g., 5/8 is braced by 3/5 and 2/3 so that 5/8 = (2 +3)/(5+3) and 5/7 is braced by 2/3 and 3/4. Beginning in row 0 and counting right to left, we find that 5/8 is the 10th rational in the hierarchy. Applying the above procedure, 10 corresponds to 1 0 1 00 (with the last digit duplicated) which corresponds to the continued fraction [1,1,1,2] = 5/8. Continuing to the next row, you can check that 7/10 is indeed the 19th fraction in the hierarchy. It should also be noted that any term x in a row of the Farey sequence gives rise to two terms 1/(1+x) and x/(1+x) in the next row, e.g., x= 2/5 in row 2 gives rise to 5/7 and 2/7 in row 3.

Figure 1 illustrates the so-called devils or satanic staircase generic to almost all dynamic systems [3]. This figure graphs the winding number w vs a frequency ratio W that represents the ratio of a driving force frequency and the resonance frequency of an oscillator for a system known as the circle map [3]. In this map a sequence of points z0 , z1, z2  are generated by the application of the function ,

zj+1 = R(zj) where R(z) = z + W - k/2p sin 2p z.

Figure1. Devils staircase with plateaus at every rational number. From Fractals, Chaos and Power Laws by M.
Schroeder. By permission of W.H. Freeman and Company.

The j indices can be thought of as time intervals. The winding number w of the map is defined as the limit of (zn-z0)/n as n®¥ . Map R depends on a parameter k related to the energy of the system. As k® 1, a critical value, the system approaches a chaotic state in which every winding number from the unit interval [0,1] is obtained depending on the value of W with rational values of w phase locked to finite intervals of  W . By phase locking we mean that the same winding numbers are manifested for a finite interval of W values. The phase locked intervals for the irrationals have zero width and so the irrationals form a kind of "dust" between the rationals. We see that the higher a rational number is in the hierarchy the wider is the phase locked interval corresponding to it. Winding numbers represented by larger intervals correspond to resonances of dynamical systems with greater stability justifying our reference to the rationals corresponding to these intervals as being "more important." For example the three widest plateaus occur for 1/2, 2/3, and 1/3 corresponding to the first three rationals of the hierarchy. The relative widths of the plateaus are ordered according to the terms of the Farey sequence with elements within each row having approximately the same width. We make the following remarks about the relationship between the rational numbers in Table 1 and their continued fraction representations:

a) The greater the sum of the indices the smaller the plateau widths.

b) Within each block of Table 1 the continued fractions with the most dispersed series of indices occur for rational numbers that are the ratio of two integers from the Fibonacci series: 1 1 2 3 5 8 13 , e.g., when the sum of the indices equals 5 the most dispersed continued fraction indices occur for 5/8 and 3/8, e.g., 5/8 = [1,1,1,2] is highly dispersed in contrast to 3/7 = [2,3] , less dispersed. The ratio of Fibonacci numbers always appears at approximately the 1/3 and 2/3 positions of the integer block, e.g., for the integer block 8-15, ë1/3×8û = 2 and ë2/3×8û = 5 where ë û is the least integer function. Therefore the rationals 5/8 and 3/8 are positioned at 8 + 2 = 10 and 8 + 5 = 13 in the hierarchy.

c) Other widely dispersed index sets occur for the continued fraction representations of ratios of integers whose numerator is from the Fibonacci series and denominator is from the Lucas series. The Lucas series is the series: 1 3 4 7 11 18 29  , i.e., a series beginning with 1,3 in which each element is the sum of the previous two. These continued fractions are located approximately at the 1/6 and 5/6 positions in that segment of the table. For example, in integer block 64 -127 (not shown) the positions 64 +ë5/6×64û = 74 and 64 + ë5/6×64û = 117 correspond to the rationals 21/29 = [1,2,1,1,1,2] and 8/29 = [3,1,1,1,2] respectively.

3. Gray Code, Divisibility, and the Towers of Hanoi

Notice that the strings of 0s and 1s (bit strings) in the third column of Table 1 are labeled as Gray code. Gray code is a system of representing integers as bit strings such that from integer to integer only a single bit changes in its representation unlike binary in which more than one bit can change from one integer to the next, e.g., 7 = 111 whereas 8= 1000. To go from one integer to the next in Gray code the value of the bit in the least significant digit changes (0 to 1 or 1 to 0) to give a bit string not already listed. Given the Gray code representation of an integer, the indices of the continued fraction corresponding to that integer can be obtained directly by a procedure given in Appendix D. The digits of the Gray code bit strings have been labeled 0,1,2, from right to left and the digit of the Gray code that changes is listed in column 4; it is the sequence,

0102010301020104                       (1)

Where does this sequence come from? Take the integers and divide a given integer by the highest powers of 2 that goes evenly into it and record the exponent of the highest power which we refer to as the index of the factor (see Table 3). If an integer is not divisible by 2 then its index is 0.

Table 3.
Divisibility of integers by powers of 2

 Integer N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... Index 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 4 ...

You will notice that Sequence 1 has made its appearance again. Now if you remove the 0s, or alternatively, add 1 to each term, you get another familiar sequence,

121312141213121                            (2)

This corresponds to the sequence of moves required to solve the Towers of Hanoi puzzle described below. Next reduce each integer in this series by 1 to get 010201030102010 a replication of Series 1. Of course this transformation (remove the zeros and reduce by one each of the remaining numbers in Sequence 1) can be repeated ad infinitum so that we have found a self-similar pattern within the number system related to division by 2.

Note that if the modulus of any pair of adjacent numbers a/b and c/d in the Farey Sequence of Table 2 is defined to be |ad-bc|, then the Towers of Hanoi sequence is asymptotically developed for Row n as n®¥ . For example, the sequence of moduli for Row 3 of Table 2 is 3537353 which corresponds to 1213121 with the following replacements: 3®1, 5®2, and 7®3. The moduli of the first 15 entries to the Farey sequence are shown in column 5 of Table 1

The final idea in this cycle of ideas requires us to describe the Towers of Hanoi puzzle (abbreviated TOH). The Towers of Hanoi puzzle, an invention of the French Mathematician Edouard Lucas in 1883, is rich in number theoretic relations [2],[5],[6]. N disks of increasing sizes, numbered 1,2,3,,N from smallest largest are placed on one of three posts (see Figure 2). The object of the puzzle is to move all the disks to another post in such a manner that a large sized disk never lies atop a smaller sized disk during the transfer. If the posts are labeled A,B,C in a clockwise manner and the first move is in a clockwise direction, then the shortest path to the final configuration is unique. The sequence of moves is shown in column 8 of Table 1. Here the configuration

d1/d2/d3dm

signifies that disk d1 lies atop disk d2 atop d3 etc., e.g., 1/2/3 means that disk 1 lies atop 2 which lies atop 3.

Figure 2. The Towers of Hanoi Puzzle with posts arranged in a circular fashion

An optimal transfer satisfies the following rules:

a) A smaller disk must always lie atop a larger disk;

b) The parity of two adjacent disks must also be different, i.e., adjacent disks must be even  odd or odd  even numbered, e.g., in the example, 1 lies on 2 and 2 lies on 3 in the above example.

c) During any transfer, an odd numbered disk moves clockwise (CW) while an even numbered disk moves counterclockwise (CCW).

The puzzle begins with all the disks on post A as shown in Table 1. In subsequent moves, only newly transferred disks are indicated on post A. Observe that the TOH positions are correlated with the integers. In fact the following algorithm enables one to convert from the binary representation of the integer to a TOH position:

Algorithm 2:

a) For a given integer, express its binary representation in terms of its number of repeated digits. For example, 22 = 1 0 11 0 is written as {1121} since the initial 1 and 0 and the final 0 are singletons whereas the middle 11 is a pair.

b) Starting at the right, this set of indices describes how to uniquely place n disks onto the three TOH posts. The quantities of disks corresponding to the first index are placed on a post in the order 1,2,3, The number of disks corresponding to the second index then go on another post.

c) The number of disks corresponding to the third index are then placed on a different post than the previous move. If a choice arises between an occupied post or a vacant post, always choose the occupied post. At all times the three rules stated above must be satisfied.

Following these rules for {1121} the TOH position is :

5    2/3    1/4

Or, starting at the right, the first disk (#1) must go onto a post. Then the next two disks (#2 and #3) must go onto a different post. Then disk #4 must go onto a different post from the preceding one. However, according to rule c, we now have a choice:

Vacant post or occupied post

Always choose the occupied post as long a the parity rule is not violated. Therefore, #4 goes beneath #1. Then #5 must go onto a different post since it cannot go beneath disk #3 because of parity (no two odds together), so it must go onto the vacant post.

In this manner, each integer n is uniquely associated with a TOH position.

Let us now make a short digression to convert a binary number directly to its equivalent Gray code representation. Consider 19, represented in binary as 10011. Multiplying by 2 and adding the next digit we get the sequence 1, 2, 4, 9, 19. These are the decimal representations, B19, of the family of binary numbers: 1, 10, 100, 1001, 10011. Next take the differences of adjacent terms of the B19 sequence which we refer to as the Gray code sort,

 n 5 4 3 2 1 Binary 1 0 0 1 1 B19 1 2 4 9 19 Gray code sort 1 1 2 5 10 Gray code 1 1 0 1 0

Taking each number of the Gray code sort mod 2 (i.e., even is 0 and odd is 1) yields the Gray code equivalent, 11010. However, perhaps more significantly, the Gray code sort indicates the number of times the nth disk moved, up to the Nth move in the transfer to the final TOH position, e.g., up to the 19th move: disk 1 moves 10 times, while disks 2,3,4, and 5 move 5,2,1, and 1 times respectively.

Binary numbers can also be converted directly to Gray code by Algorithm 3.

Algorithm 3:

a) Record the leftmost digit of the binary representation.

b) If the k+1-th digit of binary is equal to or larger than the k-th digit then the k+1-th digit of the Gray code representation is the difference between these digits.

c) If the k+1-th digit is less than the k-th digit, then add 2 (base number of binary) to the k+1-th digit, and then subtract the k-th digit from it to obtain the k+1-th digit of Gray code.

For example,   1 0 0 1 0 ® 1 1 0 1 0

4. The Generalized Towers of Hanoi Problem

We refer to the Towers of Hanoi puzzle as TOH:2 because, as we have seen, it is based on the binary numbers. We have been able to generalize this puzzle to the transfer of disks between n+1 posts which we refer to as TOH:n. Once again the n posts are arranged in a circular formation and a small sized disk must always lie atop a larger disk. However, in any given move a disk can only move to an adjacent post and, as before, we begin by moving the first disk clockwise.   For example, let us consider TOH:3 with four posts.  Labeling the posts A, B, C, D arranged in a clockwise fashion, i.e., A ® B ® C ® D ® A,  and beginning with two disks on post A, using the previous notation, the following sequence transfers these disks optimally to another post:

 A B C D A B C D A B C D A B C D A B C D 1/2 2 1 2 1 1 2 1/2

This sequence of moves follows the pattern 1121.  As before odd numbered disks move CW while even numbered disks move CCW.   Also, on any post, adjacent disks must have different parities.

The sequence of moves for the optimal transfer for TOH:n are again related to the exponent of the greatest power of n, referred to as the index, that divides evenly into a given integer. Table 4 illustrates the divisibility sequence for TOH:3.

Table 4.
Divisibility by powers of 3

 Integer N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ... Index 0 0 1 0 0 1 0 0 2 0 0 1 0 0 1 0 0 2 ...

Eliminating the zeros results in the TOH:3 sequence 112112 reproducing the sequence for the transfer of two disks described above, then continuing on.

We can also determine the Gray code sort corresponding to the n-ary, or base n, representation of the number of moves N and use this to predict the number of moves each sized disk makes during the optimal transfer. To do this express the TOH:n position in the number system base n. For example, step number 137 is represented in base 3 as (12002)3. The sequence B137 in base 3 is then obtained by multiplying each digit of the binary representation by 3 and adding the next digit to get: 1,5,15,45,137 which gives the decimal values of the base 3 sequence: 1,12,120,1200, 12002. Next take the difference to yield the Gray code sort:

 n 5 4 3 2 1 3-ary 1 2 0 0 2 B137 1 5 15 45 137 Gray code sort 1 4 10 30 92 Gray code 1 1 1 0 2

Thus, disk 1 moves 92 times and disks 2,3,4,5 move 30, 10, 4, 1 time respectively. If the Gray code sort numbers are expressed mod 3 we get the generalized Gray code representation of 137 or 11102.

We can get the generalized Gray code of integer N directly from the base n representation by slightly modifying Algorithm 3 so that in step c the base number n is added to the k+1-th digit if it is less than the k-th digit. Just as for Gray code, a single digit changes between successive integers represented by generalized Gray code and the place value of the change numbered 0,1,2,from the right represents the highest power of n that divides evenly into N. For example, expressing the following numbers in the base 4, 31 = (133)4 and 32 = (200)4 with Gray code representations, 31 = (120)4 and 32 = (220)4. Notice that a single digit changes in the third place (i.e., place value 2). Therefore 42 is highest power of 4 that divides evenly into 32. Also note that 31 mod 4 is gotten by adding the digits of the Gray code representation mod 4, e.g., 31 mod 4 = (1+2+0) mod 4 = 3. This holds for any integer N written in any base n. Table 5 lists the generalized Gray code for the first 64 numbers of the 4-ary system. The DNA codons in this table are listed for future reference.

Table 5.
4-ary Gray Code and its Relationship to the DNA Codons

 0 000 CCC 16 130 AUC 32 220 GGC 48 310 UAC 1 001 CCA 17 131 AUA 33 221 GGA 49 311 UAA 2 002 CCG 18 132 AUG 34 222 GGG 50 312 UAG 3 003 CCU 19 133 AUU 35 223 GGU 51 313 UAU 4 013 CAU 20 103 ACU 36 233 GUU 52 323 UGU 5 010 CAC 21 100 ACC 37 230 GUC 53 320 UCC 6 011 CAA 22 101 ACA 38 231 GUA 54 321 UGA 7 012 CGA 23 102 ACG 39 232 GUG 55 322 UGG 8 022 CGG 24 112 AAG 40 202 GCG 56 332 UUG 9 023 CGU 25 113 AAU 41 203 GCU 57 333 UUU 10 020 CGC 26 110 AAC 42 200 GCC 58 330 UUC 11 021 CGA 27 111 AAA 43 201 GCA 59 331 UUA 12 031 CUA 28 121 AGA 44 211 GAA 60 301 UCA 13 032 CUG 29 122 AGG 45 212 GAG 61 302 UCG 14 033 CUU 30 123 AGU 46 213 GAU 62 303 UCU 15 030 CUC 31 120 AGC 47 210 GAC 63 300 UCC

5. A Probability density function for divisibility of integers.

We have previously shown that if each integer from the TOH:2 series , 12131214, is reduced by 1 unit, the indices of Table 2 : 01020103 result. If the zeros are removed from this series, the TOH:2 series is replicated. This process can be repeated ad infinitum and also applied to the generalized TOH:n series to reveal the self-similarity of the TOH:n series. The following theorem is the result of this self-similarity process.

Theorem: The probability p that a randomly chosen integer is divisible by nd but no higher power of n is given by,

p(nd) = (1-x)xd                                    (3)

where x = 1/n

Proof:Since every n-th integer is divisible by n, the probability x that an integer is divisible by n is x = 1/n , and the probability that an integer is not divisible by n is 1-x. Therefore, the probability that an integer has index 0 (not divisible by n) in the TOH:n table corresponding to Table 4 is 1-x while the probability that it has a non-zero index (divisible by n) is x. By the self-similarity of the TOH:n series, the probability that an integer has index 1 (divisible by n1 but no higher power of n) is (1-x)x, while the probability that the index is 2 or higher (divisible by all powers of n greater than 1) is x2. That the probability of an integer having index d is (1-x)xd follows by induction.

Corollary:

 1 = ¥ å d = 0 p(nd)

Proof Since

 1/(1-x) = ¥ å d = 0 xd
 1 = ¥ å d = 0 (1-x)xd                      (4)

The corollary follows from p(nd) = (1-x)xd

Example 1: The probability that an integer is divisible by 32 but no higher power of 3 is (1-1/3)(1/3)2 = 2/27. Therefore the number of integers smaller than 137 and divisible by 32 but no higher power of 3 is approximately: (2/27)(137) = 10.148 @ 10 as derived above. The numbers are: 9,18,36,45,63,72,90,99,117,126. This result is approximate since the probability distribution applies asympotically as the integer approaches infinity. The probability distribution function given by Equation 4 is:

 0 1 2 3 1 = (2/3) + (2/3)(1/3) + (2/3)(1/9) + (2/3)(1/27) +...

where the numbers above the terms in this equation refer to the probability distribution of 1,3,32,33,e.g., the total number of integers less than 137 divisible by any power of 3 is the sum of terms 1,2,3, and 4 of this probability distribution multiplied by 137 or
(137)(2/3)(1/3+1/9+1/27+1/81) = 45.102 » 45.

Example 2: The relative frequency of clockwise (CW) movements of the TOH:2 disks is gotten by adding the even terms of Equation 4, to get 1/(x+1), while the relative frequencies of the counterclockwise (CCW) terms are gotten from the odd terms of Equation 4, or x/(1+x) =1-1/(1+x) . For example, for TOH:2 x = 1/2, and two-thirds of the moves are CW while one-third are CCW, a ratio of CW to CCW movements of 2:1. Note that 1/(1+x) and x/(1+x) are the pair of terms of the Farey series resulting from the fraction x = 1/n.

6. Relationship between 2-ary Gray Code and the
Logistic Equation of Dynamical SystemsTheory

We have shown that the Towers of Hanoi puzzle is intimately connected with the divisibility of integers.  However, this game arises mysteriously in other places in the mathematical terrain, most notably, in the symbolic dynamics of the logistic equation of dynamical systems theory.

The logistic equation of dynamical systems theory [3] is given by,

xn+1 = a xn(1-xn)                            (5)

Given a sufficiently small value of a and beginning with x0 on the interval [0,1], the successive iterates (considered to be time intervals) of Equation 5 constitute a trajectory on [0,1]. It is well known that as values of a are increased to the critical value of 3.5699, the trajectories approach periodic orbits of periods 2n for n = 1,2,3, For values of a exceeding the critical value, the system enters the realm of chaos in which small changes in the initial conditions result in wildly different trajectories given a sufficient number of iterates (time). If we label values of xn by 0 if they lie either at the maximum point or to the left of the maximum point of the logistic function y = ax(1-x) , and 1 if they lie to the right of the maximum, the resulting string of 0s and 1s is known as the symbolic dynamics of the logistic equation.

The symbolic dynamics of the logistic equation can be generated from the binary sequence of integers in two steps:

a) Add the digits of the binary numbers mod 2 to get the so-called Morse-Thue sequence [3] , e.g,

0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010,  ® 0 1 1 0 1 0 0 1 1 0 0

b) The symbolic dynamics is gotten by transforming the Morse-Thue sequence to Gray code by Algorithm 3. This is equivalent to adding adjacent binary digits mod 2 to get what we refer to as the Complementary Morse-Thue sequence (CMT).

1 0 1 1 1 0 1 0 1 0

Notice that the symbolic dynamics of the CMT sequence is equivalent to the parity of the Towers of Hanoi sequence 121312141213121 where even digits are assigned 0 and odd digits 1 (i.e., CW = 1 and CCW = 0). Therefore, the 1s and 0s of CMT are governed by the probability density function of Equation 3, i.e., the ratio of 1s to 0s is 2:1.

7. The Relationship between 4-ary Gray Code and DNA

The 64 three letter code words, known as codons, that make up DNA can be encoded by a base four number system in a natural way. However, when the encoding numbers are represented by 4-ary Gray code this system has additional biological meaning.

It is well known that DNA is composed of 64 codons. Each codon is a three letter "word" made up of one of four bases C (Cytosine), A (Adenine), G (Guanine), U/T (Uracil/Thymine). There is a natural way to relate the DNA codons to Gray code. Use the following assignments:

 C ® 0, G ® 1, A ® 0, U/T ® 1. 0 1 1 0

For example CUG ® 011 and GAC ® 100. GAC is called the anti-codon of CUG since
001                     110

1 of the codon is replaced by 0 and 0 by 1 of the codon to get the anti-codon. Notice that the upper and lower bit strings of both the codon and anti-codon differ in a single bit, e.g., they have a Hamming distance of 1. Subtracting the Hamming distance from 9 yields the number of hydrogen bonds per codon/anti-codon pair [7]. For example, both CUG and GAC have 9  1 = 8 hydrogen bonds.

Table 6. Gray Code DNA Matrix

 0 1 2 3 4 5 6 7 000 001 011 010 110 111 101 100 0 000 000 000 000 000 000 000 000 CCC 9 CCU 8 CUU 7 CUC 8 UUC 7 UUU 6 UCU 7 UCC 8 000 001 011 010 110 110 101 100 1 001 001 001 001 001 001 001 001 CCA 8 CCG 9 CUG 8 CUA 7 UUA 6 UUG 7 UCG 8 UCA 7 000 001 011 010 110 111 101 100 2 011 011 011 011 011 011 011 011 CAA 7 CAG 8 CGG 9 CGA 8 UGA 7 UGG 8 UAG 7 UAA 6 000 001 011 010 110 111 101 100 3 010 010 010 010 010 010 010 010 CAC 8 CAU 7 CGU 8 CGU 9 UGC 8 UGU 7 UAU 6 UAC 7 000 001 011 010 110 111 101 100 4 110 110 110 110 110 110 110 110 AAC 7 AAU 6 AGU 7 AGC 8 GGC 9 GGU 8 GAU 7 GAC 8 000 001 011 010 110 111 101 100 5 111 111 111 111 111 111 111 111 AAA 6 AAG 7 AGG 8 AGA 7 GGA 8 GGG 9 GAG 8 GAA 7 000 001 011 010 110 111 101 100 6 101 101 101 101 101 101 101 101 ACA 7 ACG 8 AUG 7 AUA 6 GUA 7 GUG 8 GCG 9 GCA 8 000 001 011 010 110 111 101 100 7 100 100 100 100 100 100 100 100 ACC 8 ACU 7 AUU 6 AUC 7 GUC 8 GUU 8 GCU 8 GCC 9

In Table 6 the codons are arranged in an 8×8 square pattern along with their number of hydrogen bonds. In this square both the row and column numbers are labeled 0 to 7 in the standard Gray code, e.g., 000, 001, 011, 010, 110, 111, 101, 100, and each element of the table is listed by a 6-bit representation. This is equivalent to a Karnaugh map for a Boolean system with six variables. The Karnaugh map is a commonly used tool to simplify compound statements in Boolean (2-valued) logic [8]. In this table, as in all Karnaugh maps, adjacent elements to the left, right, up, down, or wrap-around of any element differs from that element in a single bit. Also to find the location of an anti-codon given the position (row and column) of a codon, or vice versa, use the following algorithm: row (column) 0 matches row (column) 5, 1 matches 4, 2 matches 7, 3 matches 6. For example, GGU is located in row R4 and column C5 which becomes R1 and C0 for the anti-codon CCA and each have 8 hydrogen bonds.

It has been found that the amino acids are formed from contiguous groups of codons, e.g., proline: CCC, CCU, CCA, CCG; glutamine: CAA, CAG; leucine: CUU, CUC, CUG, CUA, UUA, UUG; etc. [7]. Apparently Gray code arises in genetics as a means of minimizing the "cliffs" or mismatches between the digits encoding adjacent bases and therefore the degree of mutation or differences between nearby chromosome segments. The requirement in an encoding scheme is that changing one bit in the segment of the chromosome should cause that segment to map to an element which is adjacent to the premutated element.

There is a natural relationship between 4-ary Gray code and the DNA codons which can be understood by making the following correspondences:

0® C,  1® A, 2® G, 3® U/T in Table 5 and C ® 0, A® 0, G ® 1, U/T  ® 1 in Table 6.
0         1           1               0

This enables Table 6 to be rewritten as Table 7 using the 4-ary Gray code in Table 5. The corresponding decimal values are listed in Table 8. For example, the bit string in Row 3, Column 7 of Table 6 is

 101 011

which corresponds to UAG or Gray code 312 according to Table 7 or decimal 50 according to Table 8. Notice that Table 7 inherits the property that each codon differs from an adjacent codon: up, down, right, left, wrap-around, in a single bit. Table 7 reveals the 4-ary number system as the natural system with which to characterize the DNA codons. The integers from 0 to 63 are divided into four quadrants. Each quadrant is subdivided into four compartments of four codons where each digit of the codon representation follows the pattern:

 0 3 | | 1 --- 2

Table 7. 4-ary Gray Code Matrix

 000 003 033 030 330 333 303 300 001 002 032 031 331 332 302 301 011 012 022 021 321 322 312 311 010 013 023 020 320 323 313 310 110 113 123 120 220 223 213 210 111 112 122 121 221 222 212 211 101 102 132 131 231 232 202 201 100 103 133 130 230 233 203 200

Table 8. Decimal Values for 4-ary Gray Code Matrix

 0 3 14 15 58 57 62 63 1 2 13 12 59 56 61 60 6 7 8 11 54 55 50 49 5 4 9 10 53 52 51 48 26 25 30 31 32 35 46 47 27 24 29 28 33 34 45 44 22 23 18 17 38 39 40 43 21 20 19 16 37 36 41 42

The circle of Figure 3 is another representation of the DNA codons as a 4-ary system. The circle is divided into four compartments labeled C,A,G,U. Each compartment is subdivided into four compartments with each compartment containing four codons. The codons, their number of hydrogen bonds, and decimal values according to Table 5 are arranged in the circle with each codon connected by a line to its anticodon. The following rules match codon with anti-codon:

a) For decimal numbers 0 through 31, perform the operation of taking the mod 4 value. If the result is 0 or 1 then add 34. If the result is 2 or 3 then add 30.

b) For decimal numbers 32 through 63, perform the operation of mod 4. If the result is 0 or 1 then subtract 30. If the result is 2 or 3 then subtract 34.

For example, according to Table 5, GGU corresponds to decimal 35 where 35 mod 4 = 3. Therefore, according to rule b, subtract 34 to get decimal 1 which corresponds to CCA the anticodon of GGU.

Figure 3. 4-ary circular representation of the 64 DNA codons

Conclusion

Galileo stated that, "Natures great book is written in mathematical symbols." We have shown that we can uncover the secrets of number by holding it up to the light in the proper way. Information about naturally occurring resonances, the nature of dynamical systems, and the structure of DNA are already built into the number system through a natural hierarchy of rational numbers. The Farey sequence and continued fractions were introduced as tools to facilitate an understanding of this hierarchy. We have also shown that the structure of the integers in terms of their divisiblilty is isomorphic to the Towers of Hanoi puzzle and its generalizations. Gray code and its generalizations was introduced as an aid to understand this puzzle and also as the natural framework for systematizing the 64 codons of DNA.

Appendix A

Given the indices of a compound fraction expansion, p/q = [a1,a2,a3,,an], the approximating rational numbers, called approximants, obtained by truncating the compound fraction at successive levels can be computed by the following procedure:

1. Invert the first index so that the first approximant is p1/q1 = 1/a1.
2. The second approximant is then p2/q2 = a2/(q1a2 + 1).
3. All other approximants are determined by

pn+1/qn+1 =  (an+1pn + pn-1)/(an+1qn + qn-1).

The pn/qn approximant is the best approximation to p/q by a rational number with denominator  no larger than qn.  For example, [3,1,2] is found as follows:

3      1      2
1/3  1/4   3/11

Therefore, 1/4 is the best approximation to 3/11 with denominator no larger than 4 while 1/3 is the best approximation to 3/11 with denominator no larger than 3.

Appendix B

The following algorithm determines the irrrational number corresponding to the periodic continued fraction

[a1,a2an]¥

1. Form a matrix from the last two approximants a/b, c/d derived as in Appendix A, e.g.,

A æ
ç
è
 a
 c
 b
 d
ö
÷
ø

2. The irrational number is c/Q where Q = l1 - a with l1 the larger of the two positive eigenvalues  l1 and  l2 of  the matrix A

3. By the nature of continued fraction expansions, the determinant of the matrix always equals 1 when there are an odd number of indices, and +1 when there are an even number of indices. Therefore, it is easy to show that l1 satisfies one of the following characteristic equations:

l1 - 1/l1 = Trace(A) = a+d if odd number of indices       (B1)

l1 + 1/l1 = Trace(A) = a+d if even number of indices

and that Trace A = l1 +  l2 where,

l2 = -1/l1    if odd number  of indices
l2 = 1/l1    if even number  of indices

Since the solution to l - 1/l = 1 is the golden mean or t = (1+ Ö 5)/2, I shall refer to the solutions to Equations B1 as generalized silver means of type 1 and type 2, i.e., l1 = SM1(n) for odd indices and l1 = SM2(n) for even indices. Therefore, golden mean t = SM1(1).The generalized silver mean has property that the sum of it and plus or minus its inverse is an integer. Note that the same holds for any power of the generalized silver mean, i.e., lm± (1/l )m = Integer. This follows from the fact that lm and (1/l )m or  (1/l )m are eigenvalues of Am, the matrix corresponding to m repetitions of the indices of the corresponding rational number.

Example 1: From the example in Appendix A, [3,1,2]¥ = 3/(l1 - 1) where l1 satisfies, l - 1/l = 12 and 12 is the trace of the matrix

A =  æ
ç
è
 1
 3
 4
 11
ö
÷
ø

Solving for l1 gives l1 = SM1(12) = 6 + Ö 37. Therefore, [3,1,2]¥ = 3/(5 +Ö 37) = 0.2707 (compared with 3/11 = 0.2727).

Example 2: From Appendix A, the approximants corresponding to indices [1,2]¥ are,

1    2
1/1 2/3

And, [1,2]¥ = 2/(l1 -1) where l1 + 1/l1 = 4 (an even number of indices) where 4 is the trace of

A =  æ
ç
è
 1
 2
 1
 3
ö
÷
ø
Therefore, [1,2]¥ = 2/(1+Ö 3) where l1= SM2(4) = 2 +Ö 3. This checks with the well known result that 1 + [1,2]¥ = Ö3.

The approximants corresponding to [1,2,1,2]   are

1        2      1      2
1/1   2/3   3/4   8/11

Therefore the matrix corresponding to [1,2,1,2]¥ is

A2 æ
ç
è
 3
 8
 4
 11
ö
÷
ø

where A is the matrix corresponding to [1,2]¥  and,  Trace A2 =  (l1)2 + (1/l1)2  = 14 where l1 =  2 + Ö3.    You may check to see that [1,2]¥ =  [1,2,1,2]¥.

Appendix C

Given a rational number P/Q where P<Q, the Euclidean Algorithm can be used to determine the indices of the continued fraction representation. The Euclidean Algorithm is based on the division algorithm in which an integer a divided by a positive integer d can be expressed in terms of quotient q and remainder r as:

a = qd + r where 0£r<d

Apply the division algorithm division algorithm recursively beginning with q/p as follows :

Q = q1P + r1
P = q2r1 + r2
r1 = q3r2 + r3

rk-2 = qkrk-1 + rk

rn-3 = qn-1rn-2 + 1
rn-2 = qnrn-1

where r1> r2 > >rk>>1> 0

That next to the last remainder equals 1 reflects the fact that P and Q are in lowest terms. The continued fraction representation of P/Q is then [q1,q2,,qn].

For example, consider 7/10:

 10 = 1×7 + 3 7 = 2×3 + 1 3 = 3×1
Therefore, 7/10 = [1,2,3]

Appendix D

The following algorithm may be used to determine the rational number corresponding to a Gray code representation of a given integer:

a) Add a zero to the end of the Gray code number.

b) In the Gray code representation starting from left to right, replace the following strings by the corresponding integers: 1 º 1, 10 º 2, 100 º 3, 1000 º 4, etc.

c) The resulting sequence of integers are the indices of the continued fraction.

For example, in Table 1 the integer 14 is represented in Gray code by 1001. Adding a 0 gives 10010. Replacing 100 by 3 and 10 by 2 yields the continued fraction [3,2] = 2/7.

Bibliography

[1]  Khinchin,  I.A.: Continued Fractions, Chicago: Univ. of Chicago Press. 1964.

[2]  Kappraff, J.: Beyond Measure: A Guided Tour through Nature, Myth and Number, In preparation.

[3]  Schroeder, M.: Fractals, Chaos, and Power Laws, New York: W.H. Freeman. 1991.

[4]  Beck, A.;  Bleicher, M.N.;   Crowe, D.W.:  Excursions in Mathematics, Worth, New York, 1969.

[5]  Gardner, M.: Towers of Hanoi: in the Icosian Game, Sci. Am.,  May 1957.

[6]  Kappraff, J.; Adamson, G.W.:  Unpublished Manuscript,  1999.

[7]  Walter, K.:  Tao of Chaos: Merging East and West, Kairos Center, Austin, 1994.

[8]  Rosen, K.: Discrete Mathematics and its Applications, McGraw-Hill, 1999.

VisMath HOME