НУ я хз число фибоначи или когонить другова, чисто эксперементально рашил провести собственный опыт.

Искать через перебор в данном случае очень не рационально.
В большинстве случаев, там где есть перебор всех возможных комбинаций
На конечном множестве, то такие вещи почти всегда имеют формулы.
Или их можно вывести опытным путем.

Вот небольшие рассуждения:

Формула для полного числа комбинаций:
K= 2 ^ N.
И так.
если N = 1 то K = 2 ^ 1 = 2
0
1
Непоходят 0


если N = 2 то K = 2 ^ 2 = 4

00
01
10
11
Из низ видно что тока 1 неподходит.

Если N = 3 то K = 2 ^ 3 = 8
000
001
010
011
100
101
110
111
Из них 3 неподходит


Если N = 4 то K = 2 ^ 4 = 16
0000
0001
0010
0011
0100
0101
0110
0111

1000
1001
1010
1011
1100
1101
1110
1111
Из них 8 неподходит.

Если N = 5 то K = 2 ^ 5 = 32

00000
00001
00010
00011
00100
00101
00110
00111

01000
01001
01010
01011
01100
01101
01110
01111

10000
10001
10010
10011
10100
10101
10110
10111

11000
11001
11010
11011
11100
11101
11110
11111

Из них 19 не неподходит

ВОт простые вычисления. далее Строим таблицу.
N = длинна ряда
K = число комбинаций
G = Число подходящих вариант
B = Число не подходящих вариантов


0) N0 = 1 K0 = 2 G0 = 2 B0 = 0
1) N1 = 2 K1 = 4 G1 = 3 B1 = 1
2) N2 = 3 K2 = 8 G2 = 5 B2 = 3
3) N3 = 4 K3 = 16 G3 = 8 B3 = 8
4) N4 = 5 K4 = 32 G4 = 13 B4 = 19

Теперь простейшим поиском закономерности можно найти вот что:

G0 = 2
G1 = G0 + 1
G2 = G1 + G0
G3 = G2 + G1
G4 = G3 + G2

теперь видна сразу закономерность распределения подходящих чисел
и считатсья будет примерно так