Ana's Golden Fractal

 

By

 

   Joseph L. Pe

 

iDEN System Engineering Tools and Statistics

                                    Motorola

                                    21440 West Lake Cook Road

                                    Deer Park, IL 60010

                                    Email: ajp070@email.mot.com

 

 

1. Summary

 

In his fascinating book “Wonders of Numbers” ([P], p. 167), Clifford Pickover introduces the Ana sequence and fractal, two self-referential constructions arising from the use of language. This paper answers Pickover’s questions on the relative composition of sequence terms and the dimension of the fractal. Also, it presents a beautiful variant of the Ana constructions involving the golden ratio.

 

2. The Ana sequence

 

Although Pickover considers a broad class of verbal sequences, for simplicity, he focuses on the most typical sequence, which I shall refer to as the Ana sequence. This sequence of words (or strings) is defined in stages by induction. At stage 1, start with the word a. To obtain the word at stage k+1, replace each occurrence of a in stage k by ana, and each occurrence of n in stage k by ann. 

 

The first four terms of the Ana sequence are

           

a

            ana

            anaannana

            anaannanaanaannannanaannana.

 

To see how the Ana sequence arises from a verbal context, observe that a letter is replaced in the next stage by its description using the indefinite articles a and an, appropriately. a is described by “an a”, so is replaced by ana, and n by “an n”, so is replaced by ann. (It helps to say the description aloud.) For example, the letter a in stage 1 is described as "an a", so the word at stage 2 is ana. The stage-2 letters are described as "an a, an n, an a", so the word at stage 3 is anaannana.

 

The number of letters in stage 1, 2, 3, 4 are 1, 3, 9, 27, respectively. Note that, since each letter is replaced by three letters, the number of letters is multiplied by three in the next stage. Hence, there are 3k-1 letters in each stage (term) k = 1, 2, 3, …

 

Pickover raises several questions on the Ana sequence. How do the number of a’s and the number of n’s grow? What is the ratio of a's to n's at each stage of construction? How about similarly defined sequences? This paper answers most of these questions.

 

The Ana sequence construction rule combines ideas from the Morse-Thue sequence and the “Look and Say” sequence. In the Morse-Thue sequence, start with 0; in general, obtain the next stage’s string by replacing 0 and 1 in the current string by 01 and 10, respectively. For example, the second stage’s string is 01, and third stage’s string is 0110. Since the next stage’s string extends the current stage’s string (for example, 0110 in the third stage is an extension of 01 in the second), the strings can be regarded as ever-longer initial segments of an infinite sequence, the Morse-Thue sequence, which begins: 0, 1, 1, 0, 1, 0, 0, 1 ... This sequence is self-similar in the sense that selecting every other term of the sequence, starting with the first term, reproduces the original sequence.

 

For the “Look and Say” sequence (called “audioactive decay” by John Conway), start with 1; in general, obtain the next term by describing the current term in terms of cardinality. For example, the first term is described as “one 1”, so the second term is 11; the second term is described as “two 1’s”, so the third term is 21; the third term is described as “one 2, one 1”, so the fourth term is 1211; the fourth term is described as “one 1, one 2, two 1’s”, so the fifth term is 111221, and so on.

 

For more information on the Morse-Thue and “Look and Say” sequences, see [S1] and [S2].

 

2. The Ana fractal

 

Pickover uses the Ana sequence to construct Cantor set-style graphics (a “fractal bar code”). a's are represented by dark bars, and n's by white spaces. Start with a closed interval I of fixed length L. For simplicity, let L = 1 in what follows. At each stage k, evenly partition I into 3k-1 subintervals, representing the 3k-1  letters in stage k of the sequence, and shade each closed subinterval Ia corresponding to an a. For example, the first four stages in the construction look like

 

            ▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

            ▬▬▬▬▬▬▬▬▬▬                                    ▬▬▬▬▬▬▬▬▬

            ▬▬▬                 ▬▬▬▬▬▬                       ▬▬▬            ▬▬▬

                ▬▬                 ▬▬    ▬▬                   ▬▬           

                       

Pickover refers to an Ana fractal, and asks for its fractal dimension, but does not specify the set he considers. I offer two interpretations of this set. (For background material on fractals, see [B] or [C].)

 

1. Let Ak the union of the dark-shaded closed subintervals (corresponding to a’s) in stage k. The first and most obvious interpretation is to consider the Ana fractal A to be the set of points of I that are in all the Ak’s. This is the way the Cantor (ternary) set C is defined. However, it is easy to see that A would then be identical to C, whose dimension is log 2 / log 3. (An a in one stage generates ana in the next, which is equivalent to deleting the (open) “middle third” of Ia—the same rule for forming the Cantor set. Although n’s generate ann’s, the new a’s introduced by the n’s are not in all of the Ak’s.) Obviously, this is not an interesting situation. For the remainder of this paper, I only consider the following interpretation.

 

2. In the second interpretation, A is considered to be the set of points of I that are eventually contained in the Ak’s. That is, a point x of I is in A if there is a stage kx for which x is in each Ak for k > kx.

 

This definition allows for a novel and more complex A. For example, in the construction of C, no point in the “middle third” at stage 2 is in C. For A, however, the n corresponding to the “middle third” at stage 2 produces an a with its subinterval Ia (n yields ann), some points of which could belong to A. As I shall show later, some points of this “middle third” are actually in Ak for k > 3, hence are in A.

 

Below, I analyze the structure of A and determine its fractal dimension. . Actually, the fractal dimension, which is defined for compact sets, will be computed for the closure of A, a closed and bounded, hence compact, set. Including the limit points of A in the definition of A, to make A compact, would have been artificial. Besides, the term fractal in this paper, as in many other discussions, refers to a (not necessarily compact) set exhibiting some self-similarity.

 

3. Some answers for Dr. Googol

 

Pickover’s book “Wonders of Numbers” unfolds as a series of stories in the career of the fictional hero-mathematician Dr. Googol. Here are answers to some of the good doctor’s questions. In the next sections, proofs appear in the context of another episode in his unswerving quest for mathematical truth.

 

1. Let a(k), n(k) denote the number of a's and n's, respectively, at stage k = 1, 2, 3, ... Then

 

a(k) = (3k-1 + 1)/2

n(k) = (3k-1 - 1)/2.

 

Hence, lim k a(k)/n(k) = 1.  (“lim k” denotes the limit as k goes to infinity.)

 

2. Using the plausible but ungrammatical "a n" instead of "an a" in describing the letter n, I obtain an Ana sequence variant with a(k) and n(k) for stage k > 1 given by consecutive Fibonacci numbers. In particular,

 

a(k) = F(2k-1)

            n(k) = F(2k-2),

 

where F(n) denotes the n-th Fibonacci number. Hence, lim k a(k)/n(k) = φ = (1 + 51/2) /2, the golden ratio. I call this sequence the golden Ana sequence, and its associated “bar code” fractal (defined similarly as A above) the golden Ana fractal.

 

3. The fractal dimensions of both the Ana and the golden Ana fractals equal 1

 

4. Ana's golden construction

 

The golden Ana construction is based upon a grammatical mistake. I would like to motivate this construction by imagining a further adventure of Dr. Googol. After much lecturing on the Ana sequence, he feels burned out, and takes a vacation in Guatemala, a venue befitting his unique and remarkable mind. At the summit of Temple I in the great Maya site of Tikal, he is stranded by an afternoon downpour. To pass the time, he scribbles the Ana sequence in his notebook. Ana, his Guatemalan tour guide, takes an interest, and attempts to reconstruct the sequence for herself. However, her English is not perfect, and she mistakenly uses "a n" instead of "an n". She writes

 

a

            an a

            an a             a n             an a

 

and draws the corresponding stages of the associated fractal:

 

            ▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

            ▬▬▬▬▬▬▬▬                                ▬▬▬▬▬▬▬▬

            ▬▬▬            ▬▬▬▬▬▬          ▬▬▬              ▬▬▬   

           

(For greater clarity, the words have been broken up to make the verbal descriptions explicit. As in the construction of the Ana fractal, the initial closed interval I is partitioned into congruent subintervals, one for each letter in the stage.) Dr. Googol, of course, corrects her. Puzzled, Ana asks, doesn't the rule "a before a consonant, an before a vowel" apply here? The doctor reminds her that the pronunciation takes precedence: this is an exception to the rule since n is pronounced en as if it began with a vowel.

 

Ana frets over the irregularity of English. Why can’t it be more like Spanish, which is so regular? She thinks for a moment, and adds that using "a n" instead of "an n" makes the Ana construction much more interesting. When Dr. Googol asks why, she cites the remarkable occurrence of φ in her sequence. She goes on to present him with the statement and proof of results 1-3 above. Dr. Googol is impressed by his talented tour guide, whose remote Maya forbears had, after all, discovered positional numeration with zero, integral right triangles, and magic squares independently of the Old World.

 

Here are Ana’s proofs. Considering the golden Ana sequence, first, she observes that for stage k > 1, each a in stage k-1 becomes ana in stage k, contributing two a’s and one n to stage k. Also, each n in stage k-1 becomes an in stage k, contributing one a and one n to stage k. Therefore, she has the recurrence relations

 

           

 

a(k) = 2a(k-1) + n(k-1)

            n(k) = a(k-1) + n(k-1)

 

and initial conditions a(1) = 1, n(1) = 0.

 

To prove a(k) = F(2k-1), n(k) = F(2k-2) for k > 1, she uses induction on k. For the base step k = 2, clearly, a(2) = 2 = F(3) and n(2) = 1 = F(2) fit the pattern. For the induction step, assume that a(k) = F(2k-1) and n(k) = F(2k-2). She must show that a(k+1) = F(2k+1) and n(k+1) = F(2k). By the recurrences, the induction hypothesis, and the definition of the Fibonacci sequence,

 

            a(k+1) = 2a(k) + n(k)

                        = 2F(2k-1) + F(2k-2)

                        = F(2k-1) + [F(2k-1) + F(2k-2)]

                        = F(2k-1) + F(2k)

                        = F(2k+1)

 

           

n(k+1) = a(k) + n(k)

                        = F(2k-1) + F(2k-2)

                        = F(2k).

 

This completes the induction proof. Therefore, a(k) > n(k) are consecutive Fibonacci numbers for k > 1. Since F(n+1) / F(n) approaches φ as n grows large, then a(k)/n(k) approaches φ as a limit.

 

A similar calculation shows result 1 for the (standard) Ana sequence. The initial conditions are as before, but the recurrence relations are now

a(k) = 2a(k-1) + n(k-1)

n(k) = a(k-1) + 2n(k-1).

 

To prove a(k) =  (3k-1 + 1)/2 and  n(k) = (3k-1 - 1)/2, she uses induction on k. For the base step k = 1, clearly, a(1) = 1 and n(1) = 0  fit the pattern. For the induction step, she assumes the result for k > 1; she must show that a(k+1) =  (3k + 1)/2 and  n(k) = (3k - 1)/2. By the recurrences and the induction hypothesis,

 

            a(k+1) = 2a(k) + n(k)

                        = 2[(3k-1 + 1)/2] + (3k-1 - 1)/2

                        = (3k + 1)/2

 

           

n(k+1) = a(k) + 2n(k)

                        = (3k-1 + 1)/2 + 2[(3k-1 - 1)/2]

                        = (3k - 1)/2.

 

This completes the induction proof. Obviously, the expressions for a(k) and n(k) imply that lim k a(k)/n(k) = 1.

 

5. Structure and dimension of the Ana fractals

 

This section uses the terminology of Section 2. Let C(I) denote the Cantor set with initial closed interval I. (The Cantor set as usually defined is C = C([0,1]).)

 

To characterize the Ana fractal A, suppose that x is in A. Then there is a stage kx at which x is in Ak for k > kx. This means that x is in a closed stage-kx subinterval Ia corresponding to an a, and will never be removed by a deletion of “middle thirds” (resulting from n generating ann) at any later stage. By the remarks in 1 of Section 2, x is in the the Cantor set C(Ia). Therefore, x is in A if and only if at some stage kx, x is in C(Ia) for an an a in kx. In other words, A is the union of all the Cantor sets C(Ia) where a appears in some stage in the construction of A.

 

The same remarks and characterization hold for the golden Ana fractal G.

 

It is not hard to show that the closures of A and G both equal the initial interval I, which has fractal dimension = 1, but a direct computation from the definition will be given. To compute the fractal dimensions of (the closures of) A and G, recall the definition of the fractal dimension (or Minkowski dimension) D of a compact set S (here specialized for a subset S of the real line R1, such as the Cantor set; cf. [B] or [C] for background material). Let ε > 0 and N(ε) denote the smallest number of closed intervals of length 2 ε (i.e., with "radius" = ε) needed to cover S. Then

 

            D = lim εà0 log N(ε) / log(1/ε).

 

 

This general definition of dimension applies to sets that do not necessarily exhibit any obvious self-similarity.

 

Let r(k) denote the number of subintervals in the partition of the closed interval I at stage k. For A, r(k) = 3k-1, and for G, r(k) = a(k) + n(k) = F(2k-1) + F(2k-2) = F(2k) à

1/51/2  φ2k as k grows large. The latter observation follows from the closed form expression for the n-th Fibonacci number F(n), that is,

 

F(n) = 1/51/2 [((1 + 51/2)/2)n - ((1 - 51/2)/2)n],

 

and the observation that in the second factor, the second summand ((1 - 51/2)/2)n à 0.

 

It then suffices to consider ε = 1/(2r(k)) for k = 1, 2, 3, … in the calculation of D (cf. [B], Theorem 1, p. 176 in the chapter on fractal dimension). More precisely, if εk = 1/(2r(k)), then

 

            D = lim k log N(εk) / log(1/εk).

 

Note that since I has length L = 1, εk equals half the length (i.e., the “radius”) of a stage-k subinterval, so N(εk) equals the smallest number of closed intervals, each congruent to a stage-k subinterval, needed to cover the set S = A or G..

 

Clearly, a(k) such subintervals are needed to cover just the Cantor sets C(Ia), where Ia is the closed subinterval corresponding to an a at stage k. Also, it is not hard to see that n(k) such subintervals, one for each white space (unshaded open interval) Wn corresponding to an n, are needed to cover the Cantor sets C(Ia)’s of the a’s descending from that n. (These C(Ia)’s  get arbitrarily close to the endpoints of Wn.) Therefore, N(εk) = a(k) + n(k) = r(k). Also, 1/εk = 2r(k).

 

Substituting in the above definition of D,

 

            D = lim k log r(k) / log(2r(k))

                = lim k log r(k) / [log(2) + log r(k)]

                = 1

 

for both A and G.

 

Although they are somewhat atypical, Cantor set-style fractals having fractal dimension equal to 1 have been studied; see for example, Magdi Mohamed’s construction in [C], p. 33.

 

6. Fractals on similar sequences

 

The analysis of the Ana fractal in this paper can be easily modified to the study of a similar fractal on the Morse-Thue sequence. I leave this as an exercise for the interested reader.

 

The “Look and Say” sequence presents more of a challenge since it is not generated by simple replacements as in the Ana and Morse-Thue sequences. It is possible to define fractals on the “Look and Say” sequence in the style of 1 and 2 of Section 2 above. However, their analysis appears to be difficult.

 

 

 

Acknowledgement. The author thanks Dr. Mohammad Khadivi for reviewing this paper and providing valuable suggestions.     

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

References

 

[A] Andrews, G. Number Theory. Dover Publications, 1994.

 

[B] Barnsley, M. Fractals Everywhere. Academic Press, 1988.

 

[C]  Crownover, C. An Introduction to Fractals and Chaos. Jones and Bartlett, 1995.

 

[P]  Pickover, C. Wonders of Numbers. Oxford University Press, 2001.

 

[S] Schroeder, M. Fractals, Chaos, Power Laws. W. H. Freeman, 1991.

 

[S1] Sloane, N. and Plouffe, S. The Encyclopedia of Integer Sequences. Academic Press, 1995.

 

[S2] Sloane, N. The Online Encyclopedia of Integer Sequences at the following URL:

http://www.research.att.com/~njas/sequences/Seis.html

 

[W] Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Penguin    Books, 1998.