Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I'm curious about a number series

  1. Nov 5, 2009 #1
    This is an interesting type of number series I found. I have no idea if it's good for anything, but somehow it's captured my interest.

    the first example, the simplest is 0,1,1,0

    the rules of operation are that you start at each position and take a pair of numbers. At the end, you wrap to get the last member of the last pair.

    In the simple series, you get 01,11,10,00. This is every possible pair of numbers.
    They are 'compressed' in a series that only requires n elements but produces all n possible pairs.

    The next exampe is 0,0,0,1,1,1,0,1

    When taken in triplets, you get 000,001,011,111,110,101,010,100 (wrapping as needed)
    This is every possible triple of numbers. They are represented by a string of only 8 numbers. So the 'compressed' string of n numbers yields all n * 3 triples.

    There should be a string, then, which is 256 characters long which produces all 256 8 character words, I think.

    It's not quite a gray code, because 2 bits can change at each step, but I haven't figured out a formula to generate these strings.

    There is something interesting about exponents becoming geometric that fascinates me and I wondered does anybody know anything about this or have thoughts on it?
  2. jcsd
  3. Dec 18, 2010 #2
    --arranging 2^n bits in circle so all 2^n consecutive strings of length n are distinct.
    Those are called De Bruijn's sequence. (also Ouroboros Snake, Ouroborean ring)

    How many De Bruijn's sequence for n-strings of 0-1?
    This is sequence A016031 in OEIS http://oeis.org/A016031
    De Bruijn's sequence: 2^(2^(n-1) - n): ways of arranging 2^n bits in circle so all 2^n consecutive strings of length n are distinct.
    (n=1..9): 1, 1, 2, 16, 2048, 67108864, 144115188075855872, 1329227995784915872903807060280344576, 226156424291633194186662080095093570025917938800079226639565593765455331328

    See also: http://en.wikipedia.org/wiki/De_Bruijn_sequence

    One possible ouroborean ring for quadruplets is
    There are others.
    Ouroborean rings exists for all m-tuples of n digits: for example, in this one
    each triple of the three digits 0, 1, 2 occurs exactly once.
    There are also 2D ourotorus.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook