Thinking Mathematically - P192 Sequence

I could not find a direct method in finding out the final digit. However, I found a shortcut. It is most easily explained by taking a closer look at page 2. So how does this shortcut work.

Take a look the example at the bottom of page 2. I am taking the 1st and 5th bits and putting it through an exclusive OR gate.

Exclusive OR gate:
inputs output
x y z
0 0 0
0 1 1
1 0 1
1 1 0

The output is 1 only if one of the two inputs are 1. So, I am taking the 1st and 5th bits and putting it through an exclusive OR gate. Then I take the 2nd and 6th, 3rd and 7th... Using this method I can skip 3 lines of binary strings.

I tried extending it and found that it works for every 9 bits, 13 bits and 17 bits. 13 is a special case though. If you are going to do every 13 bits you need an Exclusive NOR gate which looks like:

Exclusive NOR gate:
inputs output
x y z
0 0 1
0 1 0
1 0 0
1 1 1

I believe this also works with 25, 33, 45, 57, 73, 89... with 25, 45, 73 needing a Exclusive NOR gate.

You can see a pattern by subtracting each working number from the number prior. Starting at 9 you add 4 + 4 + 8 + 8 + 16 +16 + 32 + 32... Notice all of the numbers are 2 to the power of something.

----------------------------

I have something to add, a better explanation following my above method.

Given a bit string of any length, it can quickly be reduced by skipping bits! The problem is, which bits can you skip?

This is how it is done:

1. Take any bit in the string, n
2. Take a second bit, n + or - 2^m (Stay within your max string length)
3. Compare these 2 bits using an Exclusive OR gate, as written above
4. The output is your single resultant bit 2^m rows down

Example: A string of 20 bits

11101 00110 10100 00101

Take the first bit and another bit 2^m bits away. If m is 4, 2^4 = 16. If m is 5, 2^5 = 32. 32 is too large so take m = 4.

Looking at bits 1 and 17 (1+2^4) you compare them using an Exclusive Or gate. --> 1 + 0 = 1
Bit1 Bit2 Output
1(1) 17(0) 1
2(1) 18(1) 0
3(1) 19(0) 1
4(0) 20(1) 1

The new string is

1011

This is now easy to reduce to:

110
01
1

And we are done!