Some time ago I received a very interesting and challenging algorithmic exercise. It is based on Fibonacci numbers. And here it is…

We have the following sequence:

1. a
2. b
3. ab
4. bab
5. abbab
6. bababbab
7. abbabbababbab
8. bababbababbabbababbab
9. abbabbababbabbababbababbabbababbab

In words it si like this: the Nth line is (N-2)th line concatenated with (N-1)th line where N is starting from 2. So the second line is line 0 + line 1 which equals “ab”. The third line is line 1 + line 2 which gives us “bab” and so on.

We had to find the Xth character on the Yth row and if the Yth row doesn’t as much characters as requested by Xth character then we must specify that the search is out of range or that the input values are invaild.

Example 1: Row 8, Character 4 -> returns character “b”
Example 2: Row 6, Character 6 -> returns character “a”
Example 3: Row 2, Character 10 -> returns “Invalid input values”

This was the exercise.

We searched a lot and found very interesting things like:

• one millionth Fibonacci number – http://www.upl.cs.wisc.edu/~bethenco/fibo/
• every Fibonacci number bigger than 1 (except F(6)=8 and F(12)=144) has at least one prime factor that is not a factor of any earlier Fibonacci number – http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibtable.html
• an interesting number, golden ratio, used in arts and mathematics – http://en.wikipedia.org/wiki/Golden_ratio
• article on Wikipedia regarding L-Systems – http://en.wikipedia.org/wiki/L-System

There are many other interesting things regarding Fibonacci series but what was needed was found on the L-System Wikipedia article: Fibonacci and Algae L-System. The Algae is the inverse of Fibonacci.

Using golden ratio is relatively easy to find the Nth character in the the series but what is limiting us is the Example 3 – to tell when the requested character position is out of the number of characters on the specified row. This is because for that we need to calculate the length of the string which eventually will be bigger that any number that can be store in the computer memory.

There is the example in flex and you can download the source at the end of the article.

To find the Xth character we followed these steps:

1. Xth / golden ratio
2. floor on the number found at step 1
3. multiply the number from step 2 with golden ratio
4. if the number at step 3 is in the (Xth-1, Xth] interval (excluding Xth-1) we have a “b” character otherwise “a” character

This is mainly the algorithm to find the character.

We implemented an example using both Algae and Fibonacci L-System and we were helped a lot by our friends at East (east.fi) with the Algae implementation.

This is all for now.