The Golden String of 0s and 1s

This page is all about the sequence
10110101101101011010110110101101 ...
We could just have easily swopped the 0s and 1s to form its complement:
01001010010010100101001001010010...
but the first version will be used on this page though all the results apply to the complement also.
Here we will call this bit-sequence the RabBIT sequence since it is a sequence of BITS (0s and 1s) that naturally arises when we look at Fibonacci's Rabbit problem.
But because the golden section numbers Phi (1.6180339...) and phi (0.6180339...) - and therefore the Fibonacci numbers - are also intimately related to this sequence in many and varied ways and in practically everything we look at to do with this string, it is also called the golden string and the Fibonacci word.

Contents

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

--------

Fibonacci Numbers and the Rabbit sequence

This page is all about a remarkable sequence of 0s and 1s which is intimately related to the Fibonacci numbers and to Phi:
1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 ...

First we re-examine Fibonacci's original Rabbit problem and see how it can generate an infinite sequence of two symbols and in a later section we see how the same sequence is very simply related to Phi also.

1 Lining up the Rabbits

If we return to Fibonacci's original problem - about the rabbits (see the Fibonacci home page if you want to remind yourself) then we start with a single New pair of rabbits in the field. Call this pair N for "new".
  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.
Hence MNM goes to MN M MN .

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

   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:

1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 ...

By Using the rules that a New rabbit becomes Mature in the next month and also that a Mature rabbit stays Mature and also produces a New rabbit, we have the rules
N → M
M → MN
or, using bits:
0 → 1
1 → 10
then each generation produces the following bit-strings, called (finite) Fibonacci Words:
1
10
101
10110
10110101
1011010110110
...

1.1 Another way to generate The Rabbit sequence

Using 1s and 0s (for Ms and Ns), we can make the rabbit sequence for month x by taking the sequence from month x-1 and writing it out again, following it by a copy of the sequence of month x-2.
So, starting from
0: 0 and
1: 1
the next is M (last month) followed by N (the previous month) giving
2: 10
The following month (3) there will be 10 from month 2 followed by 1 from month 1 giving 101
3: 10 1
and the one after that is 101 followed by 10:
4: 10 1 10

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.


1.2 Computers use The Rabbit sequence!

Our use of 0s and 1s above is not just arbitrary - it actually occurs in a real-life situation, albeit inside a computer!
In this section we show how the definition of the Fibonacci numbers leads us directly to the Fibonacci Rabbit sequence.
We see how a computer actually carries out the evaluation of a Fibonacci number using the Rabbit sequence secretly behind the scenes!

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

f(0)=0
f(1)=1
f(n)=f(n-1)+f(n-2) for n>1
We will be interested in how the computer is evaluating a call of f on a number n - in particular, what are the actual numbers added (and in what order) when computing f(n). The third line of the definition means that to compute f(n) we first need to compute f(n-1) as a separate computation and then remember its result so that, when we have then computed f(n-2) - another separate computation - we can add the two values to find f(n). The first line of the definition means that
to compute f(0)
the program function immediately returns the answer 0.
The second line of the definition means that
to compute f(1)
the computer again immediately returns the answer 1.

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
to show that
a call of f(0) is replaced by (gets expanded to) 0

Similarly,
f(1)
  1
shows that f(1) gets expanded to 1, shown on the line below it, using the function definition given above.
What happens for larger values of n?
To compute f(2)
since n>1 we will be using the third line of the definition
f(n)=f(n-1)+f(n-2)
For f(2), n is 2 so we need to compute f(1)+f(0).
First f(1) is computed, giving 1 and then we compute and add on f(0), which is recomputed as 0. The pattern of calls of f when computing f(2) is therefore shown in our calling sequence diagram as follows:
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 
Note that the actual additions performed are 1+0+1, and that these numbers appear the lower end of the "branches" in the "calling tree".
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 
so the actual addition performed is
1+0+1+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 
The actual additions this time are
1+0+1+1+0+1+0+1=5
You should now be able to see that the sequence of 0's and 1's used in the additions is defined as follows: let's let s(n) stand for the sequence of 0's and 1's used in computing f(n) so that:
s(0)=0
s(1)=1
s(n)=s(n-1)
"followed by" s(n-2)
so we have
                                    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
...
and we see s(n) gives a sequence of additions involving 0s and 1s which defined the Fibonacci numbers.

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.

1.2.1 The number of additions when computing f(n)

When computing f(n) by the recursive formula at the start of this section:
f(0)=0; f(1)=1; f(n)=f(n-1)+f(n-2) for n<0 or n>1
it takes longer to compute the larger values. This is because the computer is doing a lot of recalculation as we have just seen above. So we can ask
How much work does it take to compute f(n)?
This is measured by the number of additions performed.
We have already written out the actual additions in the table above, up to s(6). Let's look at it again and count the number of addition operations this time:
                                    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
...
What is the pattern in the series 0,0,1,2,4,7,12,...?
Let's call this the A series (for Additions):
n:0123456...
A(n):00124712...
We can see some information by just looking at the recursion formula:
f(n) = f(n-1)+ f(n-2)
so
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)
or, using the A(i) notation for 'the number of additions in computing f(i)':
A(n) = A(n-1) + A(n-2) + 1; A(0)=0; A(1)=0
This is now a complete (recursive) definition of A. We can now use it to find A(7), the number of additions needed to compute f(7) (=13).
It is A(6)+A(5)+1 or 7+12+1 which is 20.
Here are a few more values:
n:012345678910
A(n):0012471220335488

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:

n:012345678910
A(n):0012471220335488
f(n+1):1123581321345589
So
A(n) = f(n+1) - 1
This means that the work needed to compute f(n) is measured by f(n+1) because we can ignore the 'minus 1' as it is insignificant when f(n) is large.

With thanks to Aaron Goh for suggesting this section.

1.3 Listen to the golden sequence

The first 100 notes of the sequence are encoded in the sound track of a Quicktime movie made into notes with every "1" converted to 'D' (1173.33 Hz) and every "0" into the 'D' an octave higher (2346.66 Hz) played at about 5 notes per second (so the track lasts about 20 seconds), in a 467K file. The rhythm is quite fascinating - hypnotic even - and it seems to have a definite beat that keeps changing and keeping your attention.
Thanks too to Casey Mongoven for providing a slightly faster (9 seconds) MP3 version (150K), giving me the correct pitch of the recording and his amazing music based solely on the Fibonacci numbers, the golden section and the rabbit sequence (a.k.a. the Fibonacci word, the golden string).
Check out Casey's site for more on his own compositions based on several other sequences you'll find on this web site. They are often only a few seconds in length but they do render the mathematics as pure sound.

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.


2 Phi and the Rabbit sequence

Our "golden" sequence has many remarkable properties that involve the golden section.

2.1 The Phi line Graph

y = Phi x graph
If we draw the line y = Phi x on a graph, (that is, a line through the origin whose gradient is Phi) then we can see the Rabbit sequence directly.

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

and where the Phi line crosses a vertical grid line (x=1, x=2, etc) we record a 0.

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


1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 ...

This is called the cutting sequence of Phi.
If we take any number, θ, then we can draw a straight-line graph of y = θ x and find the cutting sequence for θ.
Since phi = 1/Phi then we can reflect the line y = Phi x in a mirror along y = x.
Such a reflection in the 45° line y = x will change vertical axis lines into horizontal and vice-versa, which changes 0s to 1s and 1s become 0s in the cutting sequence. The slope of the reflected line is 1/θ.
For example:
the cutting sequence of phi=0.6180339... is 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 ...
the cutting sequence of Phi=1.6180339... is 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 ...

The following sections explore this relationship using functions such as "the next integer below" (the floor function) and "the next integer above" (the ceiling function) which will tell us which grid-line we have just crossed.

2.2 The rabbit sequence defined using the whole part of Phi multiples

If we take the number Phi, which we have seen is closely related to the Fibonacci series, then it leads to another simple definition of the rabbit sequence.
With the definitions above, we have to find all the preceding bits (Ms or Ns) to find which letter occurs in place i in the sequence. Using Phi=1·618034... we can compute it directly:
If we let M = 1 and N=0 then the rabbit sequence is 101101... and:
rabbit(i) = floor( (i+1) Phi ) – floor( i Phi ) – 1 where Phi = (√5 + 1 )/2 = 1·618034...
or
rabbit(i) = floor( (i+1) phi ) – floor( i phi ) where phi = Phi – 1 = (√5 – 1)/2 = 0·618034...
floor(x) is the function which just forgets anything after a decimal point in x, for positive x, giving just the whole number part.
To see how this works, look at these tables of multiples of Phi and of phi = Phi – 1:

Multiples of Phi = 1.6180339...
i i Phi floor(i Phi)RabSeq
11.618034...1
2M
23.223606...3
1N
34.854101...4
2M
46.472135...6
2M
58.090169...8
1N
69.708203...9
2M
711.326237...11
...
Multiples of phi = 0.6180339...
i i phi floor(i phi)RabSeq
10.618034...0
1M
21.223606...1
0N
31.854101...1
1M
42.472135...2
1M
53.090169...3
0N
63.708203...3
1M
74.326237...4
...

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.

2.2.1/ You Do The Maths...

  1. Try extending the tables for a few more rows.

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

2.3.1 More or Less than the previous one?

Here is another method to generate the Rabbit sequence but this time using the bits we threw away above - the fractional parts of the multiples of Phi! Of the fractional parts, none except 1×phi is ever equal to phi.
i i Phi Rab Seq
11.618034...
Down M
23.223606...
Up N
34.854101...
Down M
46.472135...
Down M
58.090169...
Up N
69.708203...
Down M
711.326237...
...

multiples of Phi
y = FractionalPart(x Phi)

plot n*Phi fract parts An alternative way to generate the sequence of U's and D's is to look at this picture of the fractional parts of multiples of Phi from 1 Phi to 49 Phi.
Up and Down mean that the fractional part on the line below has gone Up or Down compared to the previous fractional value. A line goes from the multiple (a number) to the fractional part of that multiple of phi on the horizontal (x) axis.

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


2.3.2/ You Do The Maths...

  1. Note that sometimes a new point will be plotted further to the right than any previous one (i.e. its fractional part will be larger than any before it). What multiples of Phi result in these "furthest out" points?
  2. What multiples correspond to those points plotted furthest to the left?
  3. What if we used multiples of phi instead of Phi?

2.3.3 More or Less than Phi?

Surprisingly, we do not even need to compare a fractional part with its predecessor - just compare each with the fractional part of Phi or just to phi itself, 0.6180339... !
i Fractional
part of
i Phi
More or Less
than phi
=0.6180339..?
11.618034...=
23.223606Less
34.854101More
46.472135Less
58.090169Less
69.708203More
711.326237Less
812.944271More
914.562305Less
1016.180339Less
1117.798373More
1219.416407Less
...
  Frac(n phi) is More or less than phi plot

3 The rabbit sequence and the spectrum of Phi

Let's look again at the multiples of Phi, but this time concentrating on the whole number part of the multiples of Phi. We will find another extraordinary relationship.
The "whole number part" of x is written as floor(x) so we are looking at floor(i Phi) for i=1,2,3,... .
In this section on the Golden String (the Rabbit sequence) will only be interested in positive numbers, so the floor function is the same as the floor function.
The sequence of truncated multiples of a real number R is called the spectrum of R.
Here are the first few numbers of the spectrum of Phi, that is the values of the series floor(Phi), floor(2 Phi), floor(3 Phi), floor(4 Phi), ...:-

i12345678...
i Phi1.6183.2364.8546.4728.0909.70811.32612.944...
floor(i Phi)1346891112...
So the spectrum of Phi is the infinite series of numbers beginning 1, 3, 4, 6, 8, 9, 11, 12, ... .

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

i12345678910111213...
Rabbit sequence1011010110110...

This pattern provides another way of defining the Golden String:

The 1s in the Rabbit Sequence (a.k.a the Golden String) occur at
positions given by the spectrum of Phi
and zeroes occur at all the other positions.

3.1 Complementary Spectra

Remarkably, the positions of the 0s are also given by the spectrum of another number: Phi2 (which is also equal to Phi+1):
i12345678
i Phi22.6185.2367.85410.47213.09015.70818.32620.944
floor(i Phi2)2571013151820
These two sequences together, the spectrum of Phi and the spectrum of Phi2 therefore include every number once and once only between them, with no number in both series.
This is a property of all irrational numbers bigger than 1 that there is another number whose spectrum is just those numbers that are missing (a complementary spectrum number): for instance How are the two complementary spectra numbers a and b related?
 1 
a
+  1 
b
 = 1
The calculator below will compute spectra for you and find complementary numbers too.

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

4 The Mancala Game and the spectrum of Phi

Roland Schröder has invented (July 2010) a fascinating game for one which reveals the sequence 1,3,4,6,8, ... (the spectrum of Phi) based on the African game of Mancala. You play it on your own with coins or pebbles or just with paper-and-pencil. Here I will describe a slightly simpler version of my own and then expand it to Roland's game.

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.

1234
Mancala: o oo o
oo
oo
oo
No new pebbles are added during a game and no pots are removed or added. A move consists of redistributing the pebbles from one pot into others according to a simple rule. For convenience, we show the number of pebbles in each pot:
Start:1234
Pick up all the pebbles in the leftmost pile (here just 1 pebble) and drop one into each pot going right until they are all placed:
1234
-2+134
Move 1 -334
Repeat with the leftmost pot containing some pebbles, which is the second pot of 3 pebbles, putting one pebble in each of the pots to its right. Any pebbles left are lost from the game:
-334
--3+14+11
Move 2 --45
Keep doing this, moving the pebbles from the leftmost pot to those on its right until only one pot, the rightmost, has some pebbles in it and the final move is to remove those pebbles and see how many there are:
Move 2 --45
---5+13
Move 3 ---6
---6
Move 4----6
On the 4th move we are left with 6 pebbles in our hand and no pots to put them in so the game ends with a score of 6.
We started with 4 pots and the 4th number on the spectrum of Phi is 1, 3, 4, 6, 8, ... is 6, the number of pebbles left at the end of this game. It has taken 4 moves to empty 4 pots starting with 1,2,3 and 4 pebbles and we are left with 6 pebbles.
It will take 5 moves to empty 5 pots from 1,2,3,4 and 5 pebbles and we have 8 pebbles at the end.
If we start with n piles 1,2,3, ..., n then we will end up with the nth pot to empty finally and the number of pebbles in it will be the nth number in the sequence 1,3,4,6,8, ..., the spectrum of Phi!

4.1 Roland Schröder's Mancala Game

Roland Schröder invented this Mancala game that produces the spectrum of Phi but his version was an extended form of that which I described in the previous section.
In Roland's longer version:
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 nth 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,
In effect, we just continue the short game described above for a few more moves, so Roland's original version is a simple extension of my shorter version.
Here is an example again using 4 pots:
Start:1234
Move 1 -334
Note the appearance of a new pot on the right in the next move:
Move 2--451
We will omit the empty pots on the left:
Move 2451
Move 36211
The short game ends here, the original 4th pot containing 6 pebbles.
Move 4322111
Move 533211
Move 64321
The game ends now since no further moves alter the number of pebbles in the pots.
...4321
Starting with 4 pots, the 4th entry in the spectrum of Phi is 1, 3, 4, 6, 8, 9, 11, 12, ... and there were indeed 6 moves to reach the stable state where this extended game ends. The maximum number of pots in use is also 6.

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

4.2 The Infinite Mancala Game

An even easier version is to start with an infinite line of pots (!) containing 1,2,3,4,... pebbles in turn and play the game. Now no new pots are needed and of course we will never run short of pots to place the pebbles in on any move :-).
The (maximum) number of pebbles that each pot held just as it was emptied is as follows:
Pot number:123456789101112...n
Max number of
pebbles in it:
134689111214161719 ...floor(n Phi)
which is, again, the spectrum of Phi.

4.2.1 The Mancala Calculator

C A L C U L A T O R
the Mancala Game starting with piles

of from
up to

R E S U L T S

4.2.2/ You Do The Maths...

  1. What is the spectrum of phi=0·61803... ?
    Either use the calculator above or else your own calculator and repeatedly add phi, noting down the whole number part before the decimal point. It begins 0,1,1,2,3, ...
    You will find that some numbers are repeated and others are not. How do the repeated numbers relate to the rabBIT sequence and how do the others?
  2. Look at the differences between successive pairs of numbers in the spectrum of Phi=1·618034.
    Do you recognise the sequence of differences?

5 Patterns in the RabBIT Sequence

At first the string of 0s and 1s in the RabBIT sequence seem to have no pattern, but in fact it is full of surprises! In this section we explore some of its many and varied mathematical surprises.

5.1 The first 2000 bits of the Rabbit Sequence

Here are the first 2000 bits of the Rabbit sequence, from 0 to 1999, as produced by the calculator below. Use the calculator to produce longer tables or different parts of the rabbit sequence.
            1          2          3          4          5          6          7          8          9
 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789
0+ 0101101011 0110101101 0110110101 1011010110 1011011010 1101011011 0101101101 0110101101 1010110110 1011010110
100+ 1101011010 1101101011 0110101101 0110110101 1010110110 1011011010 1101011011 0101101101 0110101101 1010110101
200+ 1011010110 1101011010 1101101011 0110101101 0110110101 1010110110 1011011010 1101011011 0101101011 0110101101
300+ 1010110101 1011010110 1101011010 1101101011 0101101101 0110110101 1010110110 1011010110 1101011011 0101101011
400+ 0110101101 1010110101 1011010110 1011011010 1101101011 0101101101 0110110101 1010110110 1011010110 1101011011
500+ 0101101011 0110101101 0110110101 1011010110 1011011010 1101101011 0101101101 0110101101 1010110110 1011010110
600+ 1101011011 0101101011 0110101101 0110110101 1011010110 1011011010 1101011011 0101101101 0110101101 1010110110
700+ 1011010110 1101011010 1101101011 0110101101 0110110101 1010110110 1011011010 1101011011 0101101101 0110101101
800+ 1010110101 1011010110 1101011010 1101101011 0110101101 0110110101 1010110110 1011011010 1101011011 0101101011
900+ 0110101101 1010110101 1011010110 1101011010 1101101011 0101101101 0110110101 1010110110 1011010110 1101011011
1000+ 0101101011 0110101101 1010110101 1011010110 1011011010 1101101011 0101101101 0110110101 1010110110 1011010110
1100+ 1101011011 0101101011 0110101101 0110110101 1011010110 1011011010 1101101011 0101101101 0110101101 1010110110
1200+ 1011010110 1101011011 0101101011 0110101101 0110110101 1011010110 1011011010 1101011011 0101101101 0110101101
1300+ 1010110110 1011010110 1101011010 1101101011 0110101101 0110110101 1010110110 1011011010 1101011011 0101101101
1400+ 0110101101 1010110101 1011010110 1101011010 1101101011 0110101101 0110110101 1010110110 1011011010 1101011011
1500+ 0101101011 0110101101 1010110101 1011010110 1101011010 1101101011 0101101101 0110110101 1010110110 1011011010
1600+ 1101011011 0101101011 0110101101 1010110101 1011010110 1011011010 1101101011 0101101101 0110110101 1010110110
1700+ 1011010110 1101011011 0101101011 0110101101 0110110101 1011010110 1011011010 1101101011 0101101101 0110101101
1800+ 1010110110 1011010110 1101011011 0101101011 0110101101 0110110101 1011010110 1011011010 1101011011 0101101101
1900+ 0110101101 1010110110 1011010110 1101011010 1101101011 0110101101 0110110101 1010110110 1011011010 1101011011

5.2 Does the Golden String ever repeat?

Shown in different line-lengths, different patterns emerge. Explore the patterns and matches in the Rabbit sequence but although it looks as if you might have found a pattern where all the lines are identical so that it looks as if that pattern repeats forever, sooner or later it will change!
For instance, 300 bits (0-299)
at 30 bits per line we have:
Here it is split into blocks of length 34:
Rabbit 0-299 in 30s =
010110101101101011010110110101
101101011010110110101101011011
010110110101101011011010110110
101101011011010110101101101011
011010110101101101011010110110
101101101011010110110101101101
011010110110101101011011010110
110101101011011010110110101101
011011010110101101101011011010
110101101101011010110110101101
Rabbit 0-305 in 34s =
0101101011011010110101101101011011
0101101011011010110101101101011011
0101101011011010110110101101011011
0101101011011010110110101101011011
0101101011011010110110101101011011
0101101101011010110110101101011011
0101101101011010110110101101101011
0101101101011010110110101101101011
0101101101011010110110101101101011
If the Rabbit sequence is split up into lines with a Fibonacci number of bits in each line, it seems that the rabbit sequence is repeating, but, continued long enough, all such patterns will eventually break down. There is no pattern that eventually repeats forever.
With lines of length 34 (a Fibonacci number) shown on the right above, there are three differences between the rows and they can be hard to spot. How many can you find?

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.

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

There is a remarkable relationship between the spectrum of a number and those numbers missing from it.
All the integers appear in the spectra of two numbers, P and Q, and no number is in both spectra if a) the numbers P and Q are irrational and b) they satisfy this relationship:
1 = 1 = 1
PQ
therefore...
1 = 1 − 1 = P − 1
QPP
which is the same as
Q = P
P − 1
Such numbers - or rather the spectra of such numbers - are said to partition the integers since all the integers are in exactly one of the two sets (spectra). So if we let A be Phi, B is Phi/(Phi-1) = Phi/phi = Phi2 since 1/phi=Phi.
Phi2 = 1 + Phi also.
So the spectrum of Phi = 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, ...
omits those numbers which are exactly those of
the spectrum of Phi2 = 1 + Phi: 2, 5, 7, 10, 13, 15, 18, ...

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:-

5.4 Which bit patterns occur?

First let's look at which bit patterns appear in the rabBIT string and which do not.
LengthpatternsNumber of
patterns
examples from
10110101101...
10
1
2 10110...
10110...
201
10
11
3101101...
101101011...
101101011...
3010
011
101
110
4 101101011
1011010..
10110...
101101011...,
40101
0110
1010
1011
1101
5 1011010110101...
101101011...
10110101101...
101101011...
1011010110...
It has been proved that there are exactly n+1 different bit patterns of length n that appear in the rabBIT string! Can you find the 6 of length 5 and the 7 of length 6?

5.5 Where do the bit patterns occur?

Here are the first 100 rabBITS indexed from 0 to 99 in a table:
            1          2          3          4          5          6          7          8          9
 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789
 0101101011 0110101101 0110110101 1011010110 1011011010 1101011011 0101101101 0110101101 1010110110 1011010110
We have just looked at where the 0s and 1s appear in the rabBIT sequence and found the formula for their positions.
But what about other strings of 0s and 1s?
Do all strings of 0s and 1s of any length appear in the rabBIT sequence eventually?
The answer to this is No! since 00 and 111 are never seen in the sequence anywhere.
But some patterns of bits appear infinitely often, for example 1 and 10 and yet others never appear at all such as 00 and 111.
For instance:
Patternstarts at
positions:
11,3,4,6,8,9,11,...
0
01
0,2,5,7,10,13,...
00 does not occur
11
110
1101
3,8,11,16,21,...
10
101
1,4,6,9,12,14,...
010
0101
01011
0,5,13,18,26,...
Other "forbidden" patterns include 01010 and 11011011.
What is special about these patterns?
Why do they not appear?
Can we predict where a given pattern will occur?
There are several surprises here:
  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 nth 0 and 1 appear. These two functions alone predict where all the other patterns appear for the nth time.
The functions that predict the starting positions are made up solely of applications of the spectrums of Phi and Phi^2 which are the starting positions of 1s and 0s!

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

The nth 1 in the rabBIT sequence appears at position floor(n Phi) which we denote by A(n)
The 0's are slightly more rare (there are approximately Phi times as many 1s as 0s in any initial part of the rabBIT sequence), and they appear at positions 0,2,5,7,10,13,... which is the spectrum of (1+Phi)=Phi2
The nth 0 in the rabBIT sequence appears at position floor(n Phi2) which we denote by B(n)
These two functions have some interesting properties too, such as B(n) = A(n) + n, for all n.

n1234567891011121314151617181920
A(n)1346891112141617192122242527293032
B(n)2571013151820232628313436394144474952
Notice that every number appears just once in the two rows of A(n) and B(n) values.

5.6 Forced Patterns

Using the Calculator below you can perform many investigations, such as finding the forced patterns, that is, the sequences of 0s and 1s that determine their next bit. For instance:
  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
A forced pattern means that whenever the those bits appear, the next bit (on the right of →) is always the same.
Other patterns such as 01 can be followed sometimes by 0 and sometimes by 1, so they do not force any particular bit to follow them.
The forced patterns, wherever they appear, which always determine the following bit, in order of length are:
Pattern:next bit
01
110
01011
11011010
0101101011011
110110101101101011010
0101101011011010110101101101011011
What do you notice about the length of these forced patterns?

The forced patterns are of length 2,3,5,8,13,21,... - the Fibonacci Numbers!
Here is the start of the rabBIT sequence:
            1          2          3          4          5          6          7          8          9
 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789
 0101101011 0110101101 0110110101 1011010110 1011011010 1101011011 0101101101 0110101101 1010110110 1011010110
Can you spot the Fibonacci-type rule here where each forced pattern is a combination of the previous two?

The nth is formed by copying the last forced pattern (n-1), but flipping the first bit (a 1 is replaced by 0 if it began with 0, and a 0 replaces the first bit if it began with a 1). We extend the pattern by copying the pattern-before-the-last (n-1) and again flipping its first bit.
For example, the 4th:
OR.....a little more complicated is.....
The nth is formed by copying the one before the last (n-2), including its forced bit and then we extend it by copying the last forced pattern (n-1) but in reverse. The final bit in this combination is the forced bit.
For example, the 4th:
OR.....the easiest method of all to describe them is ....
So we alternate taking the first Fib(n+2) bits of rabBIT sequence, but if n is even, we flip the first bit.
Thus the next (number 7, odd) is the first Fib(7+2)=Fib(9)=34 bits :
0101101011 0110101101 0110110101 1011
and we can do a quick check using the calculator above and searching for this string:
7: 0101101011 0110101101 0110110101 1010
No matter where we search in the rabBIT string, it never occurs, but the first 33 bits do, so this pattern forces a 1 to follow it.
The next, number 8, is the first Fib(10)=55 bits but 8 is even, so we must change the initial 0 into a 1
8: 1101101011 0110101101 0110110101 1011010110 1011011010 110101

5.7 AB Sequences

All the other patterns that occur have their starting positions described by combinations or repetitions of functions A and B. For instance:
11 starts at positions 3,8,11,16,21,... and this is the sequence A(B(n)) for n=1,2,...
10 starts at positions 1,4,6,9,12,14,...and this is A(A(n))

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:

Patternstarts at:Formula
00,2,5,7,10,13,...B
00 does not occur
010,2,5,7,10,13,...B
000
001
do not occur
0100,5,13,18,26,...BB
0112,7,10,15,20,23,...BA
0000
0001
0010
0011
0100
do not occur
01010,5,13,18,26,...BB
01102,7,10,15,20,23,...BA
0111does not occur
Patternstarts at:Formula
11,3,4,6,8,9,11,...A
101,4,6,9,12,14,...AA
113,8,11,16,21,...AB
100 does not occur
1011,4,6,9,12,14, ...AA
1103,8,11,16,21, ...AB
111
1000
1001
do not occur
10104,12,17,25, ...AAB
10111,6,9,14,19,22, ...AAA
1100 does not occur
11013,8,11,16,21, ...AB
1110
1111
do not occur
Some patterns have the same formula (occur at the same positions) because they are forced; thus 0 and 01 have the same formula since 01 is a forced pattern and 1 must follow any 0. Similarly with 010 which must be followed by 1 again, so occurs at the same positions as the pattern 0101.

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.

Hover your mouse over any 0 or 1 to see the AB sequence for the pattern up to that bit
12345678910111213141516...AB seq
010110101101101 0 1 1 0 1BBB
10101 1 0 1BBA
10101101BAA
101011 0 1BAB
10101101011 0 1 1 0 1 0 1 1 0 1AABB
101 0 1 1 0 1AABA
10101101AAAA
10101 1 0 1AAAB
1010110101101101 0 1 1 0 1ABAB
10101101ABAA
1010110 1ABB
The dotted lines show where there is no forced bit but both 0 and 1 are possible extensions of the pattern on its left. Since there is only one pattern of each length where there is a choice, all the other patterns of that length are forced into one particular bit to follow the pattern.

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:

Length of pattern:12345678...
Number of patterns:23456789...
So:
There are exactly n+1 possible patterns of length n in the rabBIT sequence!
Another consequence is that
the number of forced bits between choice-points is always a Fibonacci number.
Between choice-points, all strings of length Fib(n) are identical.
Thus after 1, if we choose 1, then the forcing pattern to the next choice is of length 3: 101.
Also, after 01, if we choose 1, then the next 3 bits are forced and again they are 101.
This happens wherever exactly 3 bits are forced: they will always be 101.
Where 5 bits are forced, they will be 01101.
The table of forced bits of a particular length is as follows:
Length:bits forced
201
3101
501101
810101101
130110110101101
...and can you spot how each is formed from the two before it?!?

5.8 Alternative forms for AB sequences

Have a look at this table of A and B functions:

n12345678910
A(n)13468911121416
B(n)25710131518202326
AB(n)381116212429323742
You can see that AB(n) = A(n) + B(n) and B(n) = A(n) + n both of which are provably true for all n > 0.

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 A form with no B terms: p A + q n – r
the B form with no A terms: p B – q n – r
the A+B form with no n term: p A + q B - r
Here are some examples of the equivalent forms and the calculator below will take any AB sequence and show its other forms:
AB form = A form = B form = A+B formvalues
A = A =B–n =A   1,3,4,6,8,...
B = A + n =B =B   2,5,7,10,13,...
AA = A + n – 1 =B – 1 =B – 1   1,4,6,9,12,...
BA = 2 A + n – 1 = 2 B – n – 1 = A + B – 1   2,7,10,15,20,...
AB = 2 A + n =2 B – n =A + B   3,8,11,16,21,...
BB = 3 A + 2 n = 3 B – n = A + 2 B   5,13,18,26,34,...
AAA = 2 A + n – 2 = 2 B – n – 2 = A + B – 2   1,6,9,14,19,...
BAA = 3 A + 2 n – 3 = 3 B – n – 3 = A + 2 B – 3   2,10,15,23,31,...
ABA = 3 A + 2 n – 2 = 3 B – n – 2 = A + 2 B – 2   3,11,16,24,32,...
AAB = 3 A + 2 n – 1 = 3 B – n – 1 = A + 2 B – 1   4,12,17,25,33,...
BBA = 5 A + 3 n – 3 = 5 B – 2 n – 3 = 2 A + 3 B – 3   5,18,26,39,52,...
BAB = 5 A + 3 n – 1 = 5 B – 2 n – 1 = 2 A + 3 B – 1   7,20,28,41,54,...
ABB = 5 A + 3 n = 5 B – 2 n = 2 A + 3 B    8,21,29,42,55,...
BBB = 8 A + 5 n = 8 B – 3 n = 3 A + 5 B    13,34,47,68,89,...
Did you notice that, when converted to the p A + q B – r form, then p and q are successive Fibonacci numbers and r relates the first non-zero number in the AB sequence to a third Fibonacci number?
Can you spot how the number of B's in the AB form affects the other forms?
How is the first numerical value of the series related to the – r term?

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

6 Covering patterns and what's in the gaps

Some substrings of rabBITs (patterns) are so common that every rabBIT is in some match of that pattern.
An example is rabBITs(1..3) = 101.
This pattern 101 occurs in the rabBITs sequence in positions 1..3, 4..6, 6..8, 9..11, ... , and in general we have a matching at positions AA(n)..AA(n)+2. Because every rabBIT is in a matching-range in that list, we can say that 101 covers all the bits from position 1 upwards.

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.

So what is in the gaps between the matchings?
For 010, we represent a matching in the rabBITs sequence by * so we can see what is in the gaps:
rabBITs(0,96)=11*11011*11*11011*11011*11*11011*11*11011*11011*11*11011*11011*11
so we see two kinds of gap-pattern. Represent 11 by X and 11011 by Y and, ignoring the *'s we have:
XYXYYXYXYYXYYX which is, of course, the start of the rabBIT pattern itself but with new symbols!

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:

7 A Spectrum, rabBITs and AB sequence Calculator

Key: .. indicates a range of index values as in rabBITs(1..3) meaning bits 1 to 3 of the rabBITs string.
S p e c t r u m:
Show the spectrum of [Phi] from [1] to [3]
Spectrum (1..3) of Phi = 1.618033988749895 = 1,3,4
You can enter a variety of expressions in this input box.
Click on the by the input box to get a pop-up window with all the details.
Show the multiples of [phi] from [3] to [6]
Multiples of phi = 0.6180339887498949
3: 1.8541019662496847
4: 2.4721359549995796
5: 3.0901699437494745
6: 3.7082039324993694
r a b B I T s
Show the rabBITs in lines of length [] for rabBITs index from [0] to [14]
RabBIT(0..14) = 010110101101101
Leave the line-length box empty to show all the rabBITs on one line with no line-breaks.
Show the rabBITs in lines of length [5] for rabBITs index from [0] to [14]
Rabbit 0..14 in 5s =
01011
01011
01101

Show the rabBITs table rabBITs index from [0] to [30]
RabBIT(0..30) =
           1          2          3          4          5          6          7          8          9
0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789
0101101011 0110101101 0110110101 1
P a t t e r n s
Tell me about rabBITs([1]..[4])
rabBITS[1..4]=1011 (4 bits) found at 1..4,6..9,9..12,14..17,19..22, starting at AAA(n)
it is always followed by 01=rabBITs[5..6]
no smaller pattern starts at all these positions
palindromic: false, covering: false
In the gaps: rabBITs(1,59)=*0*(1)*0*0*(1)*0*(1)*0*0*(1)*0*0

Its entension is the bits that must always follow the pattern whereever it occurs in the rabBITs sequence (i.e. they are forced).
If the pattern occurs so frequently that every bit of the rabBIT sequence is in a copy of this pattern then we say the pattern is a covering pattern (see after the calculator).
If the pattern is the same forwards and backwards then it is palindromic.
The gaps show what is between the patterns in the rabBITs string. Bracketted bits show overlaps of the end of one occurrence of the pattern and the start of the next, the pattern itself is shown by * so that in this example 1011011 is shown as *(1)* .
Use the <-> button to swop the values to find the reverse string:
Tell me about rabBITs([4]..[1]):
rabBITS[4..1]=1101 (4 bits) found at 3..6,8..11,11..14,16..19,21..24, starting at AB(n)
it can be followed by 0 or 1
the smallest pattern starting at the same positions is 11
palindromic: false, covering: false
In the gaps: rabBITs(1,61)=010*0*(1)*0*0*(1)*0*(1)*0*0*(1)*0*0

Here the pattern appears among rabBITs followed by either 0 or 1 so we can choose which bit follows it to extend the pattern, i.e no bits are forced after this pattern.
Tell me about pattern: 101011
Pattern 101011 (6 bits) found at 4..9,12..17,17..22,25..30,33..38, starting at AAB(n)
it is always followed by 01=rabBITs[10..11]
the smallest pattern starting at the same positions is 1010
palindromic: false, covering: false
In the gaps: rabBITs(1,98)=0101*01*(1)*01*01*(1)*01*(1)*01*01*(1)*01*01
Enter any bit pattern. If it appears in the rabBIT sequence, it is reported with the details as above; but if it does not, it contains a forbidden sequence such as 111 or 00 and such a sequence in the pattern is shown.
Find {palindromic} rabBIT patterns of length [2] .. [3] Choose {all} patterns of the given lengths that occur in the rabBITs or choose just the {palindromic} or {covering} patterns to be reported.
AB Sequence
Calculate AB sequence [baa] {for values of n} from [5] up to [18]
This finds all the values of BAA(n) for n=5 up to n=18:
BAA(5..18) = 31,36,44,49,57,65,70,78,86,91,99,104,112,120
Calculate AB sequence [baa](n) {values in the range} from [5] up to [18]
This finds BAA(n) values that are in the given range 5..18, which it calculates are for n=2 and 3:
BAA values in range 5..18: BAA(2..3) = 10,15
Show other forms of [BAA]
Finds the equivalent A+n form, the B+n form and the A+B form of the AB sequence:
BAA = 3 A + 2 n - 3 = 3 B - n - 3 = A + 2 B - 3
Calculate A+B sequence [2n -3 +3A] for values of n from [5] up to [18]
3 A + 2 n - 3(5..18) = 31,36,44,49,57,65,70,78,86,91,99,104,112,120
Since this is another form of BAA, it has the same values as in the example above.
Find patterns which start at AB sequence [ABB]
Longest pattern with AB sequence ABB is:
Pattern 110110101101 (12 bits) found at 8..19,21..32,29..40,42..53,55..66, starting at ABB(n)
it can be followed by 0 or 1
the smallest pattern starting at the same positions is 11011
palindromic: false, covering: false
Find patterns which start at AB sequences with [1] A's and [2] B's
Reports the patterns which start at positions given by AAB, ABA and BAA.
The equivalent forms of an AB sequence are related to the number of A's and B's.
Let your mouse rest on any input box for more details about its input.
C A L C U L A T O R

of from
to
in lines of length :
rabBITs index:
from
to
table for:
rabBITs ( <->
..
)
pattern:
a pattern starting at positions
rabBIT patterns of length ..

(n)

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
Here are some ideas for your own explorations:

7.1 / You Do The Maths...

  1. Patterns in the rabBIT sequence?
    1. Look at the rabBIT sequence using line-lengths of 21 and 13 or other Fibonacci numbers. Can you find any patterns?
    2. What about the Lucas numbers as line-lengths?
    3. Investigate one line-length more deeply.
      Can you find a formula or method for predicting exactly where the differences between lines occur?

8 Fractals

There is a lot of interest currently in Fractals. A Fractal is a shape or sequence or system that is infinite and contains a copy of itself within itself. Such pictures or series are called self-replicating or self-generating.

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.

8.1 Another way to make the Fibonacci Rabbit sequence

Above, we started with M and then replaced M by MN. From then on, we repeatedly replace M by MN and each N by M which was the process whereby we made the Fibonacci rabbit sequence at the top of this page.

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.
Here is how the process starts, where the underlined bit is the symbol pointed at:
animated alg
   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  ...
   
Since we are writing more symbols than we are "reading", the process never ends and the string grows ever longer.

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

Using the rule 1 adds on 10 at the end, what are the positions of the 1 and the 0 that we add on?
If the 1 is at position i in the list, then the 1 is added at position floor(i Phi) and the 0 at position floor(i Phi) + 1.
Pointing at
position:
12345678910
Bit:1011010110
New bits:1 011 01 011 011 01 01
at positions:1 234 56 789 101112 1314 1516

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):

Position12345678910
Bit1011010110
from1123344566
These positions are summarized in the following table of the Spectrums of Phi and phi:
floor(i Phi)13468911121416
i12345678910
RabBit1011010110
floor(i phi)1123344566

9 The Golden String contains a copy of itself

The sequence contains a copy of itself since we can apply the above process backwards: You will find that your right hand is copying the original sequence, but at something like 0·6 of the speed (actually, at 0·618034... of the speed!!).
This works because we are merely using the substitution rule "1 → 10, 0 → 1" backwards.

9.1 More copies...

If we used the substitution rules once, we can use them twice to get the substitutions
1 → 10 → 101 and 0 → 1 → 10, i.e.:
1 → 101and0 → 10
index:12345678910
rabBITs:1011010110
0→1;1→10110110101101101011010110110
and the new sequence is:
10110101101101011010110110
which is, of course, identical to the original.

If we have used the substitution rule twice:

1 → 10 → 101 → 10 1 10 and 0 → 1 → 10 → 10 1 i.e.:
1 → 10110and0 → 101
index:12345678910
rabBITs:1011010110
0→1;1→10110110101101101011010110110
same again101101011011010110101101101011011010110101
and the new sequence this time is:
10110 101 10110 10110 101 10110 ...
giving the RabBIT sequence again.

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:

1 →0 →
101
10 110
10 1 1010 1
10 1 10 10 110 1 10
......

9.1.1/ You Do The Maths...

  1. Looking at the other ways of generating the Rabbit sequence above, can you adapt them to
    • find another way of writing down the golden string by replacing groups of bits pointed at by your left hand by bits written with your right hand?
    • Use your answer "backwards" to find another way in which the golden string contains a complete copy of itself
  2. Look at the number of bits read and the number of bits written at each stage. Make a table of these two. What is the ratio between them? Do you notice the Fibonacci numbers appearing? This shows that the ratio of the two (the number of bits used to the number of bits written) will approach phi (0·6180339..).
  3. For which n is rabBIT(1..n) a covering substring?
  4. Here is another way to show the Golden sequence contains a copy of itself.
    We "read" digits with our left hand again, one at a time, and the right hand will hop over one or two digits, crossing off the next digit. Both hands start at the leftmost digit of the golden sequence. The crossed off digits are still "readable" by the left hand when we come to them, by the way.
    If we are pointing at a 1 with the left hand, then hop over TWO digits with the right hand and cross off the next.
    If we are pointing at a 0 then hop over ONE digit with the right hand and cross off the next. [In other words, hop over one more digit than you are looking at and cross off the next.]

    Here's how the process starts:

     
    ^ is left-hand-pointer  and v is the right hand pointer
    - indicates a digit hopped over by the right hand
    X indicates the digit below is to be crossed off by the right hand
    1 is a crossed-out 1 and 
    0 is a crossed-out 0:
    Here is the starting position:
     v
     1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 ...
     ^
     
     - - X  
     1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 ...
     ^ Hop over the first two digits and cross off the third
     
           - X
     1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 ...
       ^   Hop over one and cross off the next
       
               - - X  
     1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 ...
         ^  Hop over two since we are pointing at a (crossed-out) 1
         
                     - - X
     1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 ...
           ^         
                           - X
     1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 ...
             ^             
                               - - X
     1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 ...
               ^               
                                     - X
     1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 ...
                 ^                   
                                         - - X
     1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 ...
                   ^                     
     We now have:     
     1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 ... 
     and removing the crossed-off digits gives:
     1 0   1   1 0   1 0   1   1 0   1   1 0   1 0 ... 
    
    which is, of course, the original sequence.
    We have shown the golden sequence is self-similar.
    • Continue the process above for some more digits of the golden sequence and check it.
    • What do you notice about the sequence of 0s and 1s that we have crossed out?

9.2 The RabBIT Fractals

Original rabBIT Fractal
Generation 20: Large: Small:
The rabBIT sequence can be made into a fractal, that is a shape in two dimensions where parts of it are similar to the whole.
Here the shape is a single path made from straight line,s all the same length, using the rabBIT sequence as a list of instruction. Since the rabBIT sequence is unbounded in length, the shape will be infinitely long, but its structure is shown if we take the first Fibonacci number of bits and look at those fractal shapes. It was found by Alexis Monnerot-Dumaine (AMD) in 2008.
It reveals a number of white squares that the fractal line avoid, of just a few distinct sizes. The number of the squares of each size is a Fibonacci number.

rabBIT Fractal
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
rabBIT Fractal
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.
rabBIT Fractal
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)
With thanks to Alexis Monnerot-Dumaine for both his fractal and the information above.

10 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:
Mandelbrot diagram
  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).
image
Article: The Mandelbrot Set, the Farey Tree and the Fibonacci Sequence R L Delaney, American Mathematical Monthly vol 106 (1999), pages 289-302.

11 References and Links

© 1996-2023 Dr Ron Knott ronknott@mac.com
Updated: 30 August 2023