### Brain Teasers

# 0-1-3-2-6-7-5-4-12-_-_-_

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?

0-1-3-2-6-7-5-4-12-_-_-_

0-1-3-2-6-7-5-4-12-_-_-_

### Hint

This 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.### Answer

13-15-14-10-11-...The sequence is called "Gray Code" or sometimes "Gray's Binary" and has many real-world 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 4-bit 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 5-bit 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 n-bit Gray Code describes the moves needed to solve an n-disc Towers of Hanoi.

Hide Hint Show Hint Hide Answer Show Answer

## What Next?

**Solve a Similar Brain Teaser...**

Or, get a random brain teaser.

If you become a registered user you can vote on this brain teaser, keep track of

which ones you have seen, and even make your own.

## Follow Braingle!