Science Models
1000sciencefairprojects
Science Fair Projects

Published on Feb 11, 2016

Abstract

The objective: My intention with this project was to see what would happen if I allowed the use of different base numers in a Debruijn Sequence. The original Debruijn Sequence only includes binary digits (base two numbers) and includes all the possible subsequences (0,0), (0,1), (1,0), and (1,1).

Methods/Materials

An example of a Debruijn sequence of width two might be this: (0,0,1,1,0)(the number of digits in the Debruijn sequence is called the length, so in our example the length would be five).

The formula to obtain the width of a Debruijn sequence (the width is how many digits are in the subsequences) is w+2w-1. My hypothesis was that when I changed it so you could use base 3 numbers (0,1,2), you'd end up with a width to length formula of w+3w-1, the base 4 width to length to length formula would be w+4w-1...

Results


Through experimenting with these sequences and sets, I found that the formulas to get from width to length actually are w+3w-1, w+4w-1... Many interesting patterns emerged from my study of in the Debruijn sequence.

One thing I noticed that in all the sets, there was either all the same number of each number, (e.g., in the base 2 set of width 2 (0,1,1,0,0) there are 2 ones and 3 zeros and it is impossible for you to get a set of 4 ones and 1 zero or vice versa), or one more of some of the numbers.

This basically means that the amounts of each element in a set are as close as possible.

Conclusions/Discussion

According to the data, my hypothesis was correct and from it many patterns. Another pattern I noticed involves difference between the number of sequence elements. [of elements in set of width x and base (y+1) - of elements in a set of width (x-1) and base (y+1)] - [of elements in set of width x with base y - of elements in set of width (x-1) and base y]= [of elements in set of width x and base (y+2)- of elements in a set of width (x-1) and base (y+2)] - [of elements in set of width x with base (y+1) - of elements in set of width (x-1) and base (y+1)]+2. (Note, - stands for subtract).

This Mathematical project is about what would happen if you changed a variable in a set called the Debruijn Sequnece.

Science Fair Project done By Daiwei Li