Gray Code

I'd never heard of this before. I came across it when looking at the properties associated with my diurnal age of 27104. One of its properties is that it's a member of OEIS A265385:

A265385

Sequence defined by a(1) = a(2) = 1 and a(\(n\)) = gray(a(\(n\)-1) + a(\(n\)-2)), with gray(\(m\)) = A003188(\(m\)).

Here's what Wikipedia has to say on the topic:

The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit).

For example, the representation of the decimal value "1" in binary would normally be "001" and "2" would be "010". In Gray code, these values are represented as "001" and "011". That way, incrementing a value from 1 to 2 requires only one bit to change, instead of two.

Gray codes are widely used to prevent spurious output from electromechanical switches and to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.

Table 1 shows the relationships between binary, gray code and decimal.

Table 1: source

To understand how this OEIS arises, I needed a way to convert binary to gray code and this site provided some Python code to achieve this. I modified it slightly to accept decimal input (permalink). Armed with this, I began to investigate the sequence. 

The initial values are 1 and 1 and these sum to 2. The binary code for 2, as can be seen from Table 1, is 0010 which the Gray code converts to 0011 and this has a decimal equivalent of 3. Proceeding like this we have:

• 1 first seed value
• 1 second seed value
• 1 + 1 = 2 --> 3
• 1 + 3 = 4 --> 6
• 3 + 6 = 9 --> 13
• 6 + 13 =19 --> 26
• 13 + 26 = 39 --> 52
• 26 + 52 = 78 --> 105
• 52 + 105 = 157 --> 211
• 105 + 211 = 316 --> 418
• 211 + 418 = 629 --> 847
• 418 + 847 = 1265 --> 1673
• 847 + 1673 = 2520 --> 3380
• 1673 + 3380 = 5053 --> 6755
• 3380 + 6755 = 10135 --> 13404
• 6755 + 13404 = 20159 --> 27104

The OEIS comments note that:

This recurrence is reminiscent of Fibonacci's, except that the result of each step is passed through the binary-reflected Gray code mapping, which introduces a degree of pseudo-randomness. 

However, the ratio of successive terms doesn't approach the Golden Ratio but instead fluctuates around 2 with a variation of about 1% above and below. Here are the successive ratios of \( \frac{(n+1)^{th} \text{ term}}{n^{th} \text{ term}}\):

3.0000000, 2.0000000, 2.1666667, 2.0000000, 2.0000000, 2.0192308, 2.0095238, 1.9810427, 2.0263158, 1.9752066, 2.0203228, 1.9985207, 1.9843079, 2.0220830, 1.9752804, 2.0203033, 1.9986779, 1.9841292, 2.0220523, 1.9752920, 2.0202956, 1.9986750, 1.9841298, 2.0220479, 1.9752930, 2.0202950, 1.9986749, 1.9841299, 2.0220478, 1.9752930, 2.0202950, 1.9986725

There's lots of YouTube videos explaining about Gray code and I'm happy to have finally stumbled upon this clever manipulation of binary code. The OEIS A003188 referred to above lists the decimal equivalents of the Gray code for integers \(n\). The result is a permutation of the order of the cardinal numbers as shown for \(n\) up to 70:

• 0 --> 0
• 1 --> 1
• 2 --> 3
• 3 --> 2
• 4 --> 6
• 5 --> 7
• 6 --> 5
• 7 --> 4
• 8 --> 12
• 9 --> 13
• 10 --> 15
• 11 --> 14
• 12 --> 10
• 13 --> 11
• 14 --> 9
• 15 --> 8
• 16 --> 24
• 17 --> 25
• 18 --> 27
• 19 --> 26
• 20 --> 30
• 21 --> 31
• 22 --> 29
• 23 --> 28
• 24 --> 20
• 25 --> 21
• 26 --> 23
• 27 --> 22
• 28 --> 18
• 29 --> 19
• 30 --> 17
• 31 --> 16
• 32 --> 48
• 33 --> 49
• 34 --> 51
• 35 --> 50
• 36 --> 54
• 37 --> 55
• 38 --> 53
• 39 --> 52
• 40 --> 60
• 41 --> 61
• 42 --> 63
• 43 --> 62
• 44 --> 58
• 45 --> 59
• 46 --> 57
• 47 --> 56
• 48 --> 40
• 49 --> 41
• 50 --> 43
• 51 --> 42
• 52 --> 46
• 53 --> 47
• 54 --> 45
• 55 --> 44
• 56 --> 36
• 57 --> 37
• 58 --> 39
• 59 --> 38
• 60 --> 34
• 61 --> 35
• 62 --> 33
• 63 --> 32
• 64 --> 96
• 65 --> 97
• 66 --> 99
• 67 --> 98
• 68 --> 102
• 69 --> 103
• 70 --> 101