0132675412___
Series teasers are where you try to complete the sequence of a series of letters, numbers or objects.
The following series is an alternate method of counting. Every whole number will appear in the series exactly once. What are the next three numbers?
0132675412___
HintThis sequence was derived in binary. Many types of digital error correction are based on this series due to an important characteristic of the binary pattern.
Hide
Answer
1315141011...
The sequence is called "Gray Code" or sometimes "Gray's Binary" and has many realworld applications. The sequence will count all of the numbers less than 2^n before counting any of the numbers greater than or equal to 2^n.
If you look at the differences between the terms you get:
+1, +2, 1, +4, +1, 2, 1, +8
Looking at every 2nd delta you get:
+1, 1, +1, 1 ...
Every 4th delta:
+2, 2 ...
This continues with every 8th:
+4, 4 ...
and so on.
The pattern is most easily demonstrated in binary. Each successive code in the series has exactly one bit (binary digit) changed, either from 0 to 1 or from 1 to 0. This is the complete 4bit Gray Code:
0000 = 0
0001 = 1
0011 = 3
0010 = 2
0110 = 6
0111 = 7
0101 = 5
0100 = 4
1100 = 12
1101 = 13
1111 = 15
1110 = 14
1010 = 10
1011 = 11
1001 = 9
1000 = 8
The first 5bit code is:
11000 = 24
A simple application of this pattern is that it describes the sequence of discs to move in solving the Towers of Hanoi puzzle. Numbering the binary digits from right to left as:
3210
then gives the following sequence when identifying the bit number that is changed:
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
This sequence continues with:
bit 0 changed every 2nd time;
bit 1 changed every 4th time;
bit 2 changed every 8th time;
.
.
.
bit n changed every 2^(n+1) time
If you number the discs with 0 being the smallest disc, 1 the next smallest and so on, then the bit number changed each time is the disc number to move each time. An nbit Gray Code describes the moves needed to solve an ndisc Towers of Hanoi.
Hide
Back to Top
 

Follow Braingle!