The Golden String of 0s and 1s

Contents

The icon means there are You Do The Maths... investigations at the end of that section.

Fibonacci Numbers and the Rabbit sequence

Lining up the Rabbits

  Month 0:
        N
  

Next month, the pair become Mature, denoted by "M".

  Month 0:  1:
        N   M
  

The following month, the M becomes "MN" since they have produced a new pair (and the original pair also survives).

  Month 0:  1:  2:
        N   M   M
                N
  

The M of month 2 becomes MN again and the N of month 2 has become M, so month 3 is: "MNM"

  Month 0:   1:   2:   3:
        N -  M -  M -  M
                \   \  N
                  N -  M
  

The next month it is "MNMMN".

The general rule is

replacing every M in one month by MN in the next and similarly replace every N by M.

We have now got a collection of sequences of M's and N's which begins:

   0: N            =N
   
   1: M            =M
   
   2: M      N     =MN
   
   3: M   N  M     =MNM
   
   4: M N M  M N   =MNMMN
   
   5: MNM MN MNM   =MNMMNMNM
      ...           ...
   

Compare this with the picture we had of the Rabbit Family Tree where sometimes M is replaced by NM and sometimes by MN.

We often use 1s and 0s for this sequence, so here we have replaced M by 1 and N by 0:

Another way to generate The Rabbit sequence

0: 0 and
1: 1

From this definition we can see that
each monthly sequence is the start of the following month's sequence.

This means that (after the first sequence which begins with N), there is really just one infinitely long sequence, which we call the rabbit sequence or the golden sequence or the golden string.
Since the monthly bit-sequences are called (finite) Fibonacci Words, the whole infinite string of which each is at the start is called the Infinite Fibonacci Word or just the Fibonacci Word but on this page we call it the rabBIT sequence.

Computers use The Rabbit sequence!

We can write a computer program to compute the Fibonacci numbers using the recursive definition:

We will examine the calls to the function f and represent them in diagrams of "calling sequences" so that we have the following diagram for f(0):

f(0)
  0

f(1)
  1

f(2)
f(1)+f(0)
  1    0 

To compute f(3)
the function tells us to call f(2) and f(1) to compute f(2)+f(1). f(2) is called first, repeating the above computations and eventually returning 1+0=1 and after this f(1) is called, returning 1, so the final result of (1+0)+1=2 is returned.
In this case, the calling sequence in the computer again forms a "tree":

f(3)
f(2)––––––+f(1)
f(1)+f(0)    1 
  1    0 

A note on trees in computing
In computing science such tree diagrams are very useful and they appear in many different situations.
The natural way to represent them is as above, where the "root" from which the "tree" grows is at the top (since we read from top down a page of text) and so the ends of the "branches" - often called "leaves" - appear at the lowest level! So our trees are antipodean i.e. Australian since they grow upside-down!

For f(4)
the calling sequence tree is f(3) as in the last calling tree diagram but now including the call of f(2) since f(4)=f(3)+f(2):

f(4)
f(3)––––––––––––+f(2)
f(2)––––––+f(1)  f(1)+f(0)
f(1)+f(0)    1     1    0
  1    0 

If we consider further calls of f(n) for n=5 and above
then since f(n)=f(n-1)+f(n-2), each tree begins with the previous tree [used to compute f(n-1)] and is followed by the whole of the tree before that, namely for f(n-2).

For instance, here is the calling tree for f(5) which starts with f(4) and, on the right, we include f(3):

f(5)
f(4)–––––––––––––––––––––––+f(3)
f(3)––––––––––––+f(2)       f(2)––––––+f(1)
f(2)––––––+f(1)  f(1)+f(0)  f(1)+f(0)    1
f(1)+f(0)    1     1    0     1    0 
  1    0 

                                    number of
                                    0s  1s in s(n):
s(0)=0                          =0  1   0
s(1)=1                          =1  0   1
s(2)=1+0                        =1  1   1
s(3)=1+0+1                      =2  1   2
s(4)=1+0+1+1+0                  =3  2   3
s(5)=1+0+1+1+0+1+0+1            =5  3   5
s(6)=1+0+1+1+0+1+0+1+1+0+1+1+0  =8  5   8
...

There is no "last" sequence in the s(n) series but we see that a unique sequence of infinitely many 0's and 1's is defined by this process and is the one we call the Fibonacci Rabbit sequence or the Golden Sequence.

The number of additions when computing f(n)

                                    number of +'s
s(0)=0                          0 
s(1)=1                          0
s(2)=1+0                        1
s(3)=1+0+1                      2
s(4)=1+0+1+1+0                  4
s(5)=1+0+1+1+0+1+0+1            7
s(6)=1+0+1+1+0+1+0+1+1+0+1+1+0  12
...

A(n) is the number of additions in computing F(n-1)
PLUS the number of additions in computing F(n-2)
PLUS 1 in order to add f(n-1) to f(n-2)

There is another of the Fibonacci surprises here. Though the numbers are not the Fibonacci numbers, they have a similar method of construction (add the last two and then add 1). Have you noticed how the A series is related to the Fibonacci numbers themselves? The answer....

The A numbers are just 1 less than a Fibonacci number:

With thanks to Aaron Goh for suggesting this section.

Listen to the golden sequence

Mark of Perfect Fifth mentioned that the group have composed a short electronic piece called "Fibonacci" using the Golden String. You can hear it in MP3 or RealPlayer format by following the link.

Phi and the Rabbit sequence

The Phi line Graph

Where the Phi line crosses a horizontal grid line (y=1, y=2, etc) we write 1 by it on the line

Now as we travel along the Phi line from the origin, we meet a sequence of 1s and 0s - the Rabbit sequence again!

The rabbit sequence defined using the whole part of Phi multiples

The differences between the floor item on one the row and the next produces the Rabbit sequence:
we replace 2 by M and 1 by N in the Multiples of Phi table and
we replace 1 by M and 0 by N in the Multiples of phi table.

You Do The Maths...

Two ways to make the rabbit sequence defined using the fractional parts of Phi multiples

More or Less than the previous one?

i	i Phi	Rab Seq
1	1.618034...
		Down	↔	M
2	3.223606...
		Up	↔	N
3	4.854101...
		Down	↔	M
4	6.472135...
		Down	↔	M
5	8.090169...
		Up	↔	N
6	9.708203...
		Down	↔	M
7	11.326237...
		...

y = FractionalPart(x Phi)

As the multiple increases, does the point on the line move to the Right of the previous one or to the Left?

You Do The Maths...

More or Less than Phi?

i Fractional part of i Phi More or Less than phi =0.6180339..? 1 1.618034... = 2 3.223606 Less 3 4.854101 More 4 6.472135 Less 5 8.090169 Less 6 9.708203 More 7 11.326237 Less 8 12.944271 More 9 14.562305 Less 10 16.180339 Less 11 17.798373 More 12 19.416407 Less ...

The rabbit sequence and the spectrum of Phi

Now look at the Rabbit sequence and in particular at the multiples of Phi where the 1s occur:

This pattern provides another way of defining the Golden String:

Complementary Spectra

• √2 = 1.41421356 has spectrum 1,2,4,5,7,8,9,11,12,14,15,16,18,19, ...
  whereas
  2+√2 = 3.41421356 has spectrum 3,6,10,13,17,20, ...
• √3 = 1.7320508 has spectrum 1,3,5,6,8,10,12,13,15,17,19,20, ...
  and
  (3+√3)/2 = 2.36602540 has spectrum 2,4,7,9,11,14,16,18, ...
• e = 2.718281828 has spectrum 2,5,8,10,13,16,19, ...
  and
  e/(e-1)= 1.581976706869 has spectrum 1,3,4,6,7,9,11,12,14,15,17,18,20, ...

But first, let's look at a little game that produces the spectrum of Phi very simply.

The Mancala Game and the spectrum of Phi

We start with a row of pots each containing some pebbles or seeds, coins, beads etc. The first pot has 1 pebble, the second has 2, then 3 and so on. Starting with a different number of pots, each containing 1,2,3, ... pebbles in order, gives rise to a different game. Each game, with n pots takes n moves.
The game is related to the spectrum of Phi because the games with a total of 1,2,3,4, ... pots end with the number of seeds in the final pot being 1,3,4,6,8,9,11,12, ... .

As an example, let's use 4 pots to start: So we start with 4 pots containing 1, 2, 3 and 4 pebbles respectively.

Roland Schröder's Mancala Game

No pebbles are lost

Instead, any left over are added one at a time, each to a new pot on the right, for as many pots are as needed.

The game continues until a stable arrangement of the pebbles is reached

Starting from 1,2,3,...,n the goal is reached when the line of filled pots have n,n-1,...,3,2,1 pebbles in them since any subsequent moves will not alter this arrangement of pebbles.

The number of moves gives the element of the spectrum of Phi

The 'score' for the game when it finishes is not the number of pebbles in the first pot but the number of moves which will be the n^th element of the spectrum of Phi.

The maximum number of pots with pebbles in them is also the number of moves

You will see also that as new pots are introduced, the maximum number of pots holding pebbles is the same the number of moves in this game,

The calculator below has both versions of the game for you to explore, the short version and Roland's original version.

The Infinite Mancala Game

The Mancala Calculator

You Do The Maths...

Patterns in the RabBIT Sequence

The first 2000 bits of the Rabbit Sequence

Does the Golden String ever repeat?

The Calculator later on this page can quickly find all places where a pattern of bits occurs in the rabbit sequence enabling you to examine repeating patterns in as much details as you like.

The positions of the 0s and the 1s in the Rabbit string

Above we have used Phi=1.618... so what about phi=0.618... ?
Can you find any similar relationships using the spectrum of phi?
Try the following:-

Which bit patterns occur?

Where do the bit patterns occur?

1. There is a formula for the starting positions of each and every pattern that does appear.
2. Each pattern that does appear, appears infinitely many times in the rabBIT sequence.
3. We have found a function to predict where the n^th 0 and 1 appear. These two functions alone predict where all the other patterns appear for the n^th time.

The 1's appear at positions 1,3,4,6,8,.... and the spectrum of Phi is exactly this sequence, so we have:

Forced Patterns

1. 00 never appears in the rabBIT sequence, so any 0 must be followed by a 1 and so "0 forces the next bit to be 1" is a forced pattern which we can write as
   01,
2. Similarly, 111 never appears anywhere but 11 does. So whenever we see 11 it forces the following bit to be 0: it is a forced pattern. We can write this as
   110

AB Sequences

For convenience we will write the composition of A and B functions without all the brackets to make it easier to read so that A(B(A(A(n)))) is written as ABAA(n) or just ABAA. Such compositions are called AB sequences.

For example AB is A(B(n)) so that A(B(5)) = A(13) = 21.

Some more formulae are:

Here are the patterns in the rabBIT sequence classified by AB sequence.
Choose the row that corresponds to a pattern.
The dotted vertical line indicates that both 0 and 1 are possible next bits to extend a pattern; otherwise the bits are forced.
All patterns of up to 10 bits are in this table; a pattern of up to 10 bits not in this table will never occur in the rabBITs sequence.
The final column is the AB sequences for the 10-bit pattern on that row.

Another consequence of there being just one pattern of any given length that can be followed by either 0 or 1, all the others of that length determining the succeeding bit (i.e. are forcing patterns), is the following:

Alternative forms for AB sequences

We will write these in an abbreviated form similar to our AB sequences so that
3 A(n) + 2 n – 1 is 3 A + 2 n – 1 (which is also AAB) and
2 A(n) + 3 B(n) is 2 A + 3 B (which is also ABB)
or, in other words, we drop the (n) after A or B.

Any AB sequence can be converted to the forms with no A's or no B's.
So our combinations of A's and B's can be written in alternative forms where p, q, r are whole numbers

The Calculator below will show you conversions for any other AB sequence.

Covering patterns and what's in the gaps

For other subtrings of rabBITs, such as rabBITs(0..2)= 010, which also occur infinitely often, not every rabBIT is in some matching of this pattern.
This time, the matchings are at 0..2,5..7,13..15,18..20, ... or BB(n)..BB(n)+2 in general.
There are gaps here so we say that 010 is not a covering pattern.

In the case of 101, sometimes there was nothing in the gaps where a second two copies of the pattern neatly followed on after a matching, and sometimes the patterns overlapped:

A Spectrum, rabBITs and AB sequence Calculator

C A L C U L A T O R

	of You can enter numbers or expressions but all these names are case-sensitive - enter them exactly as shown: Operations: + - * / Constants: name: Phi phi E PI value: 1.618... 0.618... 2.718... 3.141... Functions: abs(real),pow(real,power),sqrt(real) sin(radians),cos(radians),tan(radians), asin(real),acos(real),atan(real) exp(real),log(real),log10(real),logBase(b,x) gcd(a,b),lcm(a,b),powmod(real,toPow,mod), EulerPhi(whole nb) FIB(i), LUC(i), G(A,b,i) from to
	in lines of length : rabBITs index: from to table for:
	rabBITs ( .. ) pattern: a pattern starting at positions all covering palindromic rabBIT patterns of length ..
	(n) for values of n values in the range from up to (n) which start at AB sequence which start at AB sequences with A's and B's

R E S U L T S

You Do The Maths...

Fractals

Our golden string contains copies of itself inside it. To see this we first show another way in which we can write down the golden string.

Another way to make the Fibonacci Rabbit sequence

Combining this with the fact that each time we replace all the letters and get a new string, the fact that the old string is the start of the new string, then we have the following simple method of generating the golden sequence (we use 1 for M and 0 for N so that it gives the list of bits above):

1. Start by writing 10 (which stands for MN above) and point to or mark the second symbol, the 0.
   Get ready to add some more symbols at the end of the sequence.
2. Use the symbol pointed at to determine how to extend the sequence at the right hand end:
   1. If you are pointing at a 1, write 10 at the end of the string;
   2. If you are pointing at a 0, write 1 at the end
   In both cases, tick off the current symbol pointed at and move to the next symbol along.
3. Repeat the step 2 for as long as you like.

   10   
   We are pointing at 0, so write a 1 at the end, 
   101
   and move on one place on (to point to the new symbol in fact):
   101 
   We are pointing at a 1, so write 10 at the end 
   10110
   and move on one place:
   10110 
   We are pointing at a 1 so write 10 at the end
   1011010
   and move on one place:
   1011010  ...
   

The rules 1 → 10 and 0 → 1 and the Spectrums of Phi and phi

When we use the rule 0 added on a 1 at the end, what position is the new 1 at?
If the 0 is at position i, the new 1 is added on at position floor(i Phi).

After the first couple of bits, all the 1s and 0s have been added on as a result of an earlier 1 or 0. What position was I pointing at when a particular bit was added on?
The position you were pointing at when the bit at position i was added on was position floor(i phi):

The Golden String contains a copy of itself

• Start by pointing at the left hand end of the (infinite) Fibonacci rabbit sequence with your left hand and with the right get ready to start writing another series.
• If you are pointing at "10", then write down "1".
  Otherwise you will be pointing at a "1", so write down a "0".
• Move your left hand past the symbols you have just "read" and repeat the previous step as often as you like.

More copies...

If we have used the substitution rule twice:

We can use the rule three times and so on to get the following infinite sequence of substitution rules all of which are guaranteed to give the rabBIT sequence:

You Do The Maths...

The RabBIT Fractals

Generation 20: Large: Small:

Show AMD fractal at Generation:	Alexis' fractal takes the finite Fibonacci words except for the final bit, that is the rabBITs from positions 1 to Fib(g)–1, and uses them as coded instructions to draw the fractal. We imagine we are at a given position on the page and facing in a certain direction. Each time we move forward in the (possibly new) direction we are facing for one "step", tracing our path as we go If the bit is a 1, we first turn on the spot to face a new direction: turn left if the 1 is in an even position in the rabBIT sequence turn right if the 1 was in an odd position in the rabBIT sequence If the bit is 0, don't turn, stay facing the same direction Then, whether it was 0 or 1, move forward one step Repeat for the next bit in the rabBIT string. In the fractals shown here, we begin at the bottom of the left hand side always. We continue doing this for each bit in the first Fib(g) bits to get generation g of the fractal. In generations 2, 8, 14, ... of AMD's fractal we have: The number of white squares of each size is always a Fibonacci number the Hausdorff Dimension of AMD's fractal is 3 log(phi)/log(1+√2) a value that involves both the golden ratio phi and the silver ratio 1+√2
Show RDK fractal at Generation:	Here is my version (RDK) which uses fewer lines but it is the same fractal. In my version, each bit of the rabBIT sequence corresponds to a straight line, as before and also, in this version we turn left or right and draw a line for each bit. Here though we always change direction: Initially we are facing east on the page and our direction of turn is "left". Move forward one step turning left or right as last time. For each 0 bit, we alter the direction of turn so that instead of turning in future to the left (or right), we will turn to the right (or left). We then look at the next bit. My version will have an exact Fibonacci number of line segments in each generation. rabBIT(1)=0: means turn left (facing North), walk one pace forward and in future turn right rabBIT(2)=1: means turn right (facing East), walk one pace forward rabBIT(3)=0: means turn right (facing South), walk one pace forward and in future turn left rabBIT(4)=1: means turn left (facing East), walk one pace forward rabBIT(5)=1: means turn left (facing North), walk one pace forward and so on.
Show AMD generation: Show RDK generation:	We see that in both versions: The fractal never intersects itself Each generation starts with the previous one and therefore all the previous generations it copies itself at different scales at generations that differ by 6 and each copy is expanded/shrunk by a factor of 1 + √2)

• The Fibonacci Word fractal A Monnerot-Dumaine (2009)

Fibonacci and the Mandelbrot Set

The Mandelbrot set shown here has been written about often in maths books, it appears in magazines and on posters, greeting cards and wrapping paper:

A detail from the Mandelbrot set picture is shown here. It is also a link to a page on how the Fibonacci numbers occur in the Mandelbrot Set (at Boston University Mathematics Department).

References and Links

• Concrete Mathematics (2nd edition, 1994) by Graham, Knuth and Patashnik, Addison-Wesley.
  This is a book I go back to so very often. It is definitely at undergraduate mathematics level (sometimes even Master's level) but chapter 3 on Integer Functions has a marvellous section on Floors and Ceilings and spectra. Well worth looking at for the serious mathematician!
• M R Schroeder Number Theory in Science and Communication, With Applications in Cryptography, Springer-Verlag, 1990. ISBN 3540158006.
  For more on the golden string as well as many reference to the Fibonacci series and the golden section.
• Fractals, Chaos and Power Laws by M R Schroeder, 1992, Freeman, ISBN 0 716 72357 3. This is a fascinating book with interesting sections on Phi, the Golden sequence chaos and fractals, and the many places in nature and science where a power law applies (that is, a law of the form y=a x^p, where y is proportional to a power of x) although it is somewhat technical.
• Goedel, Escher, Bach, D Hofstadter, Basic Books, (20th Anniversary Edition, 1999), 800 pages, is a fascinating, funny, intriguing book introducing you to the Escher's amazing pictures, Bach's contrapuntal music and the mathematical patterns in his fugues and how these illustrate Goedel's foundational theorem proved in the 1930s. See page 137.
• The Fibonacci Tree, Hofstadter and the Golden String K P Togneti, G Winley, T van Ravenstein in Applications of Fibonacci Numbers, 3rd International Conference, (editor: G Bergum), pages 325-334.
• Automatic Sequences: Theory, Applications, Generalizations J-P Allouche and J Shallit (CUP 2003)
  is an academic book so uses mathematics in a totally formal sense, but it does contain a lot of the theory of the characteristic sequences, spectra and proof for the rabBIT sequence patterns and results which I present much more informally on this page.
  Many of the ideas of the characteristic sequences and what we now call Sturmian words were first investigated (not as fully as in Allouche and Shallit's book) by Johann Bernoulli (III) (1744-1807):
• Sur une nouvelle espece di calcul Recueil pour les Astronomes vol 1 (1772), J Bernoulli, pages 255-284
  in which he relates a Sturmian word similar to our golden string but involving rounding values to a continued fraction without proofs. PDF of the complete work (French)
• Characterization of the Set of values f(n)=[n alpha], n=1,2.. by A S Fraenkel, J Levitt, M Shimshoni, in Discrete Mathematics Vol 2, 1972, pages 332-345.
• Complementary Equations and Wythoff Sequences C Kimberling, J Integer Sequences (2008) Vol 11, Article 08.3.3 (available in pdf).
  proves the formula for an AB sequence in the form p A(n) + q B(n) – r where p and q are Fibonacci numbers and was the inspiration for the A Spectrum, rabBITs and AB sequence Calculator on this page. An earlier reference to this theorem is:
• Fibonacci Representations Carlitz, R Scoville, V E Hoggatt Jr Fib Quart vol 10 (1972) pages 1-28, see Theorem 13 on page 20 pdf

The Mathematical World of the Fibonacci and Phi

Fibonacci Home Page This is the first page on this Topic. WHERE TO NOW??? This is the only page on this Topic.

The next Topic is... Who was Fibonacci?