I'm curious about a number series

  • Thread starter BenchTop
  • Start date
  • #1
40
0
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?
 

Answers and Replies

  • #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
1111000010100110
There are others.
Ouroborean rings exists for all m-tuples of n digits: for example, in this one
000111222121102202101201002
each triple of the three digits 0, 1, 2 occurs exactly once.
There are also 2D ourotorus.
 

Related Threads on I'm curious about a number series

  • Last Post
Replies
4
Views
3K
Replies
13
Views
3K
  • Last Post
Replies
3
Views
9K
  • Last Post
Replies
11
Views
4K
  • Last Post
Replies
3
Views
2K
Replies
3
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
Top