Science Fair Projects

Debruijn Sequence Taken to Higher Powers


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


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


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.


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


Related Projects : Multi-document Summarization using Spectral Clustering, Plotting Muon Pathways as a Source of Randomness, Nonlyrical Music Search Algorithm, Chinese Checkers Strategy, Effect of Impaired Judgment and Speed on Traffic Accidents, Non-Linear Optics of Interfaces in R^3, Determining the Fraction of Lattice Points Visible from the Origin in the Third Dimension, Salmonids by Numbers II, Mathematical Algorithms for Sensor Footprint Employment, Internet-Based Distributed Computing, Do Random Number Generators Follow Benford's Law, From the Nimber-Simplex Graph to Codes, Lattices, and Groups, Rollin' on Hoops, Efficient Strategy for Making a Choice from a Finite Stream of Offers, On the Flip Side


<<Back To Topics Page........................................................................................>> Next Topic



Copyright © 2013 through 2015