It is definitely trivial if binary is less than 3 bits long, there are no consecutive ‘111‘s there.
But what if binary is three bits, or longer – how to approach this question?
Well, we can start from very beginning. Lets observe:
0 bits – 0 possibilities
1 bit – 0 possibilities
2 bits – 0 possibilities
3 bits – 1 possibility, out of 8 possible.
We can add any one bit (lets agree we add bits from right for convenience), so all combinations looking like 111x are fine, lets build function.
We can also add 1 to combinations ending in ‘o11’, but we shouldnt count sequences with ‘xx111xx’ somewhere inside, since those are already taken into count.
So – with initial values ,,,, and sequence itself goes:1, 3, 8, 20, 47, 107, 238, 520, 1121,…