A string of N binary bits has the property that every bit is adjacent to a '1' bit. An example for N=12 is 111011011110.
Note that 010 is not a valid sequence, the 1 bit is not adjacent to any other 1 bit.
How many valid binary sequences of length 20 exist?
What is the smallest length N such that there are over a hundred thousand valid binary sequences?
Rule One: 010 and 000 cannot be anywhere in the sequence
Rule Two: The penultimate bit at either end cannot be 0
Since 00 is not a valid beginning, one need not test any number smaller than 2^(N-2).
Here is the output of the Python code below; it starts with 2-digits and goes to 26-digits:
[1, 3, 4, 5, 9, 16, 25, 39, 64, 105, 169, 272, 441, 715, 1156, 1869, 3025, 4896, 7921, 12815, 20736, 33553, 54289, 87840, 142129]
There are 7921 valid binary sequences of length 20.
There are 142129 valid binary sequences of length 26.
observations:
Rule Two could be eliminated by simply appending a 0 before the 1st digit and appending another 0 after the last digit since those cases will then fail by Rule One; then you could do fewer tests on 'N+2 digit" sequences. But for now, I'll just check N-digit lengths and use both rules.
There is also probably a more efficient algorithm than I used using the result for i-digit sequences to compute the result for i+1 sequences, perhaps categorizing the result by the starting 2 bits and ending 2 bits, so 4 categories. But I have not explored that.
---------------------------------
def howManyOneAdjacents(n):
""" for an n-digit binary string, how many have every bit
being adjacent to a '1' bit """
length = n
result = 0
for i in range(2**(length-2), 2**length):
binary = format(i,'0'+str(length)+'b')
if binary[1] == '0' or binary[-2] == '0':
continue
if '000' in binary or '010' in binary:
continue
result += 1
return result
digitLength = 26
ansList = []
for i in range(2,digitLength+1):
ansList.append(howManyOneAdjacents(i))
print(ansList)
|
|
Posted by Larry
on 2022-11-15 10:13:11 |
Computer solution
