# De Bruijn Sequences Provide Compact Initial Conditions

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

A de Bruijn sequence is the shortest sequence of numbers from a given alphabet that contains all possible subsequences of length . As such, it becomes the perfect initial condition for a cellular automaton (CA) where it is desirable to insure that all possible neighborhoods are explored.

[more]
Contributed by: John Kiehl (March 2011)

Open content licensed under CC BY-NC-SA

## Snapshots

## Details

Snapshot 1: The 160 binary bits needed to represent all 32-digit sequences of a , rule space can be collapsed to just a 27-digit sequence.

Snapshot 2: The 1215 base-3 digits of a , rule space can be collapsed to just 238 digits.

Snapshot 3: The 5120 base-4 digits of a , rule space can be collapsed to just 1019 digits.

Snapshot 4: On the border of intelligibility, these 3129 digits were formatted trivially using *Mathematica*'s new Pane graphics.

Use the slider to convince yourself that all the digit sequences from 0 to are represented in these patterns. Other digit sequences can be explored with *Mathematica*'s DeBruijnSequence function from the *Combinatorica* add-on package. In general, the length of a de Bruijn sequence for a -digit alphabet with -length subsequences is simply . These sequences are not unique, but rather have permutations.

## Permanent Citation