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?
global s n ct
clc
for n=3:30
s='01'; ct=0;
addon;
s='11';
addon;
disp([n ct])
end
%ct
function addon
global s n ct
if length(s)==n-1
vv='';
end
if length(s)==n
if ~isequal(s([end-1 end]),'00') && ~isequal(s([end-1 end]),'01')
ct=ct+1;
% disp(s)
end
else
if ~isequal(s([end-1 end]),'00') && ~isequal(s([end-1 end]),'01')
s(end+1)='0';
addon
s=s(1:end-1);
end
s(end+1)='1';
addon
s=s(1:end-1);
end
end
n count
3 3
4 4
5 5
6 9
7 16
8 25
9 39
10 64
11 105
12 169
13 272
14 441
15 715
16 1156
17 1869
18 3025
19 4896
20 7921
21 12815
22 20736
23 33553
24 54289
25 87840
26 142129
27 229971
28 372100
29 602069
30 974169
There ae 7921 valid sequences of length 20, and the smallest N with over 100,000 sequences is 26.
The 5 sequences for n=5 are
01110
01111
11011
11110
11111
so that it can be seen that validity is counted correctly.
For N=6
011011
011110
011111
110011
110110
110111
111011
111110
111111
Looking up in OEIS finds this is A195971.
|
|
Posted by Charlie
on 2022-11-15 10:42:22 |
computer solution
