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 3^{k-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
3^{k-1} subintervals, representing the 3^{k-1} letters in stage k of the sequence, and
shade each closed subinterval I_{a} 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 A_{k} 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 A_{k}’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 I_{a}—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 A_{k}’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 A_{k}’s.
That is, a point x of I is in A if there is a stage k_{x} for which x
is in each A_{k} for k __>__ k_{x}.

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 I_{a} (*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 A_{k} 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) = (3^{k-1 }+ 1)/2

n(k) = (3^{k-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 + 5^{1/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) = (3^{k-1
}+ 1)/2 and n(k) = (3^{k-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) = (3^{k }+ 1)/2 and n(k) = (3^{k }- 1)/2. By the
recurrences and the induction hypothesis,

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

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

= (3^{k }+ 1)/2

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

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

= (3^{k }- 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 k_{x }at which x is in A_{k }for k __>__
k_{x. }This means that x is in a closed stage-k_{x} subinterval
I_{a} 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(I_{a}). Therefore, x is in A if and only if at some stage k_{x},
x is in C(I_{a}) for an an *a in *k_{x}. In other words, *A
is the union of all the Cantor sets C(I _{a})* where

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 **R ^{1}**, 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) = 3^{k-1},
and for G, r(k) = a(k) + n(k) = F(2k-1) + F(2k-2) = F(2k) à

1/5^{1/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/5^{1/2 }[((1 + 5^{1/2})/2)^{n
}- ((1 - 5^{1/2})/2)^{n}],

and the observation that in the second factor, the second
summand ((1 - 5^{1/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(I_{a}), where I_{a} 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) W_{n}
corresponding to an *n*, are needed to cover the Cantor sets C(I_{a})’s
of the *a*’s descending from that *n*. (These C(I_{a})’s * *get arbitrarily close to the endpoints of
W_{n}.) 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.

[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.