fairfolio
Saved Projects

The Debruijn Sequence Taken to Higher Powers

CSEF · 2004 Mathematics & Software

Daiwei Li · Miller (Joaquin) Middle School, San Jose

Overview

Objectives/Goals 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.... 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) Doing this project helped me find out many new things about the Debruijn Sequence and hopefully will for you too.

Summary statement

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

Help received

Dad helped with setting up the board.

Competition history

  • CSEF 2004 Mathematics & Software · Entry J1214

Resources

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

Source: California Science & Engineering Fair public projects

Save projects to your library

Sign in with Google to keep track of projects you find interesting, organized into folders. An account also raises your daily allowance for “Has this been done?”, and lets you create a key for the MCP server with a much higher limit than anonymous use. Browsing stays public.

Continue with Google