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.
The calculators on this page require JavaScript but you appear to have switched JavaScript off
(it is disabled). Please go to the Preferences for this browser and enable it if you want to use the
calculators, then Reload this page.
Contents
The
icon means there are You Do The Maths...
investigations at the end of that section.
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:
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:
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):
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):
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:
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:
0
1
2
3
4
5
6
...
A(n):
0
0
1
2
4
7
12
...
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:
0
1
2
3
4
5
6
7
8
9
10
A(n):
0
0
1
2
4
7
12
20
33
54
88
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:
0
1
2
3
4
5
6
7
8
9
10
A(n):
0
0
1
2
4
7
12
20
33
54
88
f(n+1):
1
1
2
3
5
8
13
21
34
55
89
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
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!
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/θ.
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
1
1.618034...
1
2
↔
M
2
3.223606...
3
1
↔
N
3
4.854101...
4
2
↔
M
4
6.472135...
6
2
↔
M
5
8.090169...
8
1
↔
N
6
9.708203...
9
2
↔
M
7
11.326237...
11
...
Multiples of phi = 0.6180339...
i
i phi
floor(i phi)
RabSeq
1
0.618034...
0
1
↔
M
2
1.223606...
1
0
↔
N
3
1.854101...
1
1
↔
M
4
2.472135...
2
1
↔
M
5
3.090169...
3
0
↔
N
6
3.708203...
3
1
↔
M
7
4.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...
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
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)
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...
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?
What multiples correspond to those points plotted furthest to the left?
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..?
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
...
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), ...:-
i
1
2
3
4
5
6
7
8
...
i Phi
1.618
3.236
4.854
6.472
8.090
9.708
11.326
12.944
...
floor(i Phi)
1
3
4
6
8
9
11
12
...
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:
i
1
2
3
4
5
6
7
8
9
10
11
12
13
...
Rabbit sequence
1
0
1
1
0
1
0
1
1
0
1
1
0
...
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):
i
1
2
3
4
5
6
7
8
i Phi2
2.618
5.236
7.854
10.472
13.090
15.708
18.326
20.944
floor(i Phi2)
2
5
7
10
13
15
18
20
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
√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, ...
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.
1
2
3
4
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:
1
2
3
4
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:
1
2
3
4
-
2+1
3
4
Move 1
-
3
3
4
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:
-
3
3
4
-
-
3+1
4+1
1
Move 2
-
-
4
5
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
-
-
4
5
-
-
-
5+1
3
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:
1
2
3
4
Move 1
-
3
3
4
Note the appearance of a new pot on the right in the next move:
Move 2
-
-
4
5
1
We will omit the empty pots on the left:
Move 2
4
5
1
Move 3
6
2
1
1
The short game ends here, the original 4th pot containing 6 pebbles.
Move 4
3
2
2
1
1
1
Move 5
3
3
2
1
1
Move 6
4
3
2
1
The game ends now since no further moves alter the number of pebbles in the pots.
...
4
3
2
1
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:
1
2
3
4
5
6
7
8
9
10
11
12
...
n
Max number of pebbles in it:
1
3
4
6
8
9
11
12
14
16
17
19
...
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
4.2.2
You Do The Maths...
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?
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.
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:
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
P
Q
therefore...
1
= 1 −
1
=
P − 1
Q
P
P
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.
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:
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:
Pattern
starts at positions:
1
1,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:
There is a formula for the starting positions of each and every pattern that does appear.
Each pattern that does appear, appears infinitely many times in the rabBIT sequence.
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.
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A(n)
1
3
4
6
8
9
11
12
14
16
17
19
21
22
24
25
27
29
30
32
B(n)
2
5
7
10
13
15
18
20
23
26
28
31
34
36
39
41
44
47
49
52
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:
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,
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
0
1
11
0
0101
1
1101101
0
010110101101
1
11011010110110101101
0
010110101101101011010110110101101
1
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!
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:
is a copy of the number 3 pattern: 01011 but with its first bit flipped: 11011
followed by the number 2 pattern, 110 with its first bit flipped: 010
... making 11011 010 and it is the final bit here that is forced:
11011010
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:
is a copy of the number 2 pattern: 110
followed by the number 3 pattern, in reverse: 11010
... making 110 11010 and it is the final bit here that is forced:
11011010
OR.....the easiest method of all to describe them is ....
Those patterns beginning with 0 should be familiar: they are the first few bits of the rabBIT sequence itself.
Those beginning with 1 are also the start of the rabBIT sequence, but the first bit has been flipped!
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:
Pattern
starts at:
Formula
0
0,2,5,7,10,13,...
B
00
does not occur
01
0,2,5,7,10,13,...
B
000 001
do not occur
010
0,5,13,18,26,...
BB
011
2,7,10,15,20,23,...
BA
0000 0001 0010 0011 0100
do not occur
0101
0,5,13,18,26,...
BB
0110
2,7,10,15,20,23,...
BA
0111
does not occur
Pattern
starts at:
Formula
1
1,3,4,6,8,9,11,...
A
10
1,4,6,9,12,14,...
AA
11
3,8,11,16,21,...
AB
100
does not occur
101
1,4,6,9,12,14, ...
AA
110
3,8,11,16,21, ...
AB
111 1000 1001
do not occur
1010
4,12,17,25, ...
AAB
1011
1,6,9,14,19,22, ...
AAA
1100
does not occur
1101
3,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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
...
AB seq
0
1
0
1
1
0
1
0
1
1
0
1
1
0
1
0
1 1 0 1
BBB
1
0
1
0
1
1
0
1
BBA
1
0
1
0
1
1
0
1
BAA
1
0
1
0
1
1
0
1
BAB
1
0
1
0
1
1
0
1
0
1
1
0
1
1
0
1
0 1 1 0 1
AABB
1
0
1
0
1
1
0
1
AABA
1
0
1
0
1
1
0
1
AAAA
1
0
1
0
1
1
0
1
AAAB
1
0
1
0
1
1
0
1
0
1
1
0
1
1
0
1 0 1 1 0 1
ABAB
1
0
1
0
1
1
0
1
ABAA
1
0
1
0
1
1
0
1
ABB
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:
1
2
3
4
5
6
7
8
...
Number of patterns:
2
3
4
5
6
7
8
9
...
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
2
01
3
101
5
01101
8
10101101
13
0110110101101
...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:
n
1
2
3
4
5
6
7
8
9
10
A(n)
1
3
4
6
8
9
11
12
14
16
B(n)
2
5
7
10
13
15
18
20
23
26
AB(n)
3
8
11
16
21
24
29
32
37
42
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 form
values
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.
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.
Here are some ideas for your own explorations:
7.1
You Do The Maths...
Patterns in the rabBIT sequence?
Look at the rabBIT sequence using line-lengths of 21 and 13 or other Fibonacci numbers.
Can you find any patterns?
What about the Lucas numbers as line-lengths?
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):
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.
Use the symbol pointed at to determine how to extend the
sequence at the right hand end:
If you are pointing at a 1,
write 10 at the end of the string;
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.
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:
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:
1
2
3
4
5
6
7
8
9
10
Bit:
1
0
1
1
0
1
0
1
1
0
New bits:
1 0
1
1 0
1 0
1
1 0
1
1 0
1 0
1
at positions:
1 2
3
4 5
6 7
8
9 10
11
12 13
14 15
16
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):
Position
1
2
3
4
5
6
7
8
9
10
Bit
1
0
1
1
0
1
0
1
1
0
from
1
1
2
3
3
4
4
5
6
6
These positions are summarized in the following table of the Spectrums of Phi and phi:
floor(i Phi)
1
3
4
6
8
9
11
12
14
16
i
1
2
3
4
5
6
7
8
9
10
RabBit
1
0
1
1
0
1
0
1
1
0
floor(i phi)
1
1
2
3
3
4
4
5
6
6
9
The Golden String contains a copy of itself
The sequence contains a copy of itself since we can apply the above process backwards:
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.
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 → 101
and
0 → 10
index:
1
2
3
4
5
6
7
8
9
10
rabBITs:
1
0
1
1
0
1
0
1
1
0
0→1;1→101
101
10
101
101
10
101
10
101
101
10
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 → 10110
and
0 → 101
index:
1
2
3
4
5
6
7
8
9
10
rabBITs:
1
0
1
1
0
1
0
1
1
0
0→1;1→101
101
10
101
101
10
101
10
101
101
10
same again
10110
101
10110
10110
101
10110
101
10110
10110
101
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 →
10
1
10 1
10
10 1 10
10 1
10 1 10 10 1
10 1 10
...
...
9.1.1
You Do The Maths...
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
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..).
For which n is rabBIT(1..n) a covering substring?
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
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.
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)
With thanks to Alexis Monnerot-Dumaine for both his fractal and the information above.
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).
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
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!
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 xp, 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.
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