Mark
Dow
Geek
art
Simple
recursive systems
and fractal patterns
Fibonacci
word
arithmetic subsequences
Arithmetic
subsequences of Fibonacci words, F( c*n - d )
The
Fibonacci word F(n), arithemetic
subsequences (with black and white
as symbols a
and b)
and their discrete Fourier
transform ampitude spectra:
Fibonacci
word - Fibonacci number self-similarity
It has been noted that the subsequences F( Fm*n
), where Fm is the mth Fibonacci number,
are composed of long runs of with sequentially alternating lengths that
get longer with Fm. This is easy to see in the diagrams above. Here
several
F( Fm*n ) sequences are stacked, each with a
height Fm
of the mth one. A self-similar pattern is clear. Coloring of
contiguous regions (right) shows how this pattern relates to the
original sequence F( n ), along the top row. This is very similar to
the Thue-Morse
self-similarity and its relationship to the relflected gray code.
 |
|
 |
| Each
row is an arithmetic
sub-sequence of the Fibonacci word, F(
Fm*n
), where Fm
is the mth Fibonacci number. The height of
each set of rows is Fm.
The top row is the beginning of the
infinite Fibonacci word F(
n ). |
|
Colored
by region. The colored
regions are related by a scale transformation related to the golden
ratio, in particular the ratio of sequential Fibonacci numbers,
Fm(m+1)/Fm(m). |
The even Fibonacci
number sub-sequences ( F( Fm*n
) with m even )
are all self-similar, and the odd Fibonacci number sub-sequences (
F( Fm*n
) with m odd ) are all self-similar.
What are the lengths, L, of the runs? It looks like
the lengths grow about linearly with Fm and the first two or three runs
have an additive equality:
L(n)(1) + L(n)(2) + L(n)(3)
= L(n+1)(1) + L(n+1)(2) with n odd
L(n)(1) + L(n)(2)
= L(n+1)(1)
with n even
Another approximate self-similarity has to do with
just one of the symbols of the Fibonacci word, the second to occur:
1 2 3 4 5
6 7 8 9 ... (index n)
F(n) = a b a a b a b a a ...
The second symbol, b, occurs at indices:
( n | F(n)=b ) =
2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44,
47, 49, 52, 54, 57, 60, 62, 65... (OEIS A001950
)
If the indices n at which F(n) = b are multiplied by
Fm, the sequences formed by the sequence values at these indices are
correlated with the sequence itself:
F( Fm(m+2) ) * (n
| F(n)=b) ) ~= F( Fm(m) * n )
e.g.:
F( 3*2 ), F( 3*5 ), F( 3*7 ), ...
~= F( 1*n )
F( 5*2 ), F( 5*5 ), F( 5*7 ), ... ~=
F( 2*n )
F( 8*2 ), F( 8*5 ), F( 8*7 ), ... ~=
F( 3*n )
F(13*2 ), F(13*5 ), F(13*7 ), ... ~=
F( 5*n )
...
Notes
The second symbol of the Fibonacci word, b, occurs
at indices:
n = 2, 5, 7, 10, 13, 15,
18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, 49, 52, 54, 57,
60, 62, 65...
(OEIS A001950,
the Upper Wythoff sequence (a Beatty sequence
): a(n) = floor(n*phi^2), where phi = (1+sqrt(5))/2 )
= 2, 5, 7, 2*5, 13, 3*5, 2*3*3, 2*2*5, 23, 2*13, 2*2*7, 31, 2*17,
2*2*3*3, 3*13, 41, 2*2*11, 47, 7*7, 2*2*13, 2*27, 3*19, 2*2*3*5, 2*31,
5*13, ...
parity of number of 2's in
factorization: 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0,
0, 1, 0, 1, 0, ...
parity of number of
factors:
1, 1, 1,
0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, ...
References
The
Fibonacci Word Fractal is a
self-similar fractal curve based on the Fibonacci word through a simple
and interesting drawing rule. This fractal reveals three types of
patterns and a great number of self-similarities. We show a strong link
with the Fibonacci numbers, prove several properties and conjecture
others, we calculate its Hausdorff Dimension. Among various modes of
construction, we define a word over a 3-letter alphabet that can
generate a whole family of curves converging to the Fibonacci Word
Fractal. We investigate the sturmian words that produce variants of
such a pattern. We describe an interesting dynamical process that,
also, creates that pattern. Finally, we generalize to any angle.
Infinite
self-similar words
Grytczuk J.
Discrete Mathematics,
Volume 161, Number 1, 5 December 1996
, pp. 133-141(9)
The
words we consider in this paper are defined by some self-similarity
conditions which in particular are satisfied by the well-known
Fibonacci word f = 1011010110110 ... . We discuss structural as well as
asymptotical properties of these words.
Lyndon
words and singular factors of Sturmian words
Guy
Melançon
Theoretical
Computer Science, Volume 218, Issue 1, 28 April 1999,
Pages 41-59
Two
different factorizations of the Fibonacci infinite word were given
independently in Wen and Wen (1994) and Melançon (1996). In
a certain
sense, these factorizations reveal a selfsimilarity property of the
Fibonacci word. We first describe the intimate links between these two
factorizations. We then propose a generalization to characteristic
sturmian words.
------------------------------------
This
work is dedicated to the
Public
Domain.
There are no restrictions on use of the images or code on this
page.
Claiming
to be the originator of the material,
explicitly or implicitly, is bad karma. A link (if
appropriate), a note to
dow[at]uoregon.edu, and credit are appreciated but not required.
Comments are
welcome (dow[at]uoregon.edu).
