Title: Calculate Fibonacci words in C#
You can find Fibonacci words by concatenating previous Fibonacci words much as you calculate the Fibonacci sequence by adding previous values in the sequence. The first two Fibonacci words are:
S_{0} = 0
S_{1} = 01
The following Fibonacci words are given by:
S_{n} = S_{n1} + S_{n2}
For example, the following list shows the first few Fibonacci words.
0
01
010
01001
01001010
0100101001001
010010100100101001010
0100101001001010010100100101001001
0100101001001010010100100101001001010010100100101001010
To distinguish these "words" from another set that I will describe shortly, I'll call these values Fibonacci subwords.
If you define a unique "Fibonacci word," it is the infinite expansion of the subwords.
The Fibonacci subwords have many interesting properties such as:
 Each subword begins with the previous subword. (Due to the way you find S_{n}.)
 Every subword appears infinitely many times. (Because of the preceding property, each subword begins all of the subwords that follow it.)
 The subwords alternately end with 01 and 10.
 If you remove the last two letters from a subword (except for the first one, which doesn't have two letters), you get a palindrome.
 S_{n1} + S_{n2} and S_{n2} + S_{n1} differ only in their last two letters.
 The infinite Fibonacci word never ends and is not periodic. That means the decimal value built by using the Fibonacci digits 0.0100101001001... is transcendental (like π and e).
For other properties of Fibonacci words, see the Wikipedia article
When you click the Go button, the example program uses the following method to generate Fibonacci subwords.
// Calculate the nth Fibonacci subword.
private string FiboS(int n)
{
if (n == 0) return "0";
if (n == 1) return "01";
string s2 = "0"; // s  2
string s1 = "01"; // s  1
string s0 = "010"; // s (Initially s = 2.)
for (int i = 2; i < n; i++)
{
s0 = s1 + s2;
s2 = s1;
s1 = s0;
}
return s0;
}
This method simply follows the rules for building Fibonacci subwords. The example program uses the following code to loop through the desired number of words and displays them in the upper list box.
int num_words = int.Parse(txtN.Text);
// List subwords.
lstS.Items.Clear();
for (int i = 0; i < num_words; i++)
{
lstS.Items.Add(FiboS(i));
}
Note that the Fibonacci subwords become very long quickly. If you set n too big, the program will use up all of your computer's memory and crash. The list boxes can't display more than about 20 subwords anyway before the subwords get too long. For that reason, you may want to limit n to 20 or so.
There's another definition for Fibonacci words that I want to use in my next post. In this version, the Nth Fibonacci word has length equal to the Nth Fibonacci number. The example program uses the following method to calculate Fibonacci numbers.
// Return the nth Fibonacci number.
private int Fibo(int n)
{
if (n <= 1) return n;
int n2 = 0; // n  2
int n1 = 1; // n  1
int n0 = n1 + n2; // n (Initially n = 2.)
for (int i = 2; i < n; i++)
{
n2 = n1;
n1 = n0;
n0 = n1 + n2;
}
return n0;
}
This method simply uses the following definition of the Fibonacci sequence.
Fibo(0) = 0
Fibo(1) = 1
Fibo(n) = Fibo(n1) + Fibo(n2)
The example uses the following method to calculate Fibonacci words using the new definition with defined lengths.
// Calculate the nth Fibonacci word.
private string FiboWord(int n)
{
// See how long it should be.
int length = Fibo(n);
string s2 = "0"; // s  2
string s1 = "01"; // s  1
string s0 = "010"; // s (Initially s = 2.)
while (s0.Length < length)
{
s0 = s1 + s2;
s2 = s1;
s1 = s0;
}
return s0.Substring(0, length);
}
This method works much as the previous version did except it doesn't create a specific number of subwords. Instead it continues its loop until it generates a subword that is long enough. It then returns a substring from that subword with the desired length.
The program uses the following code to display this kind of Fibonacci word in the lower list box.
// List words.
lstWords.Items.Clear();
for (int i = 0; i < num_words; i++)
{
lstWords.Items.Add(Fibo(i).ToString() +
": " + FiboWord(i));
}
In my next post, I'll show how you can use a slightly modified version of Fibonacci words to create an interesting curve called the Fibonacci word fractal.
Download the example to experiment with it and to see additional details.
