<s>[INST] Finding how many numbers in a given set contain a given binary pattern I came across a weird question recently in a competition, and now that the competition is complete I'm wondering how to solve similar problems (the actual competition was non-calculator and had values in place of $n_{10}$ and $k_{10}$.
Given $S = \{x_{10} | x_{10} \in \mathbb{N},  n_{10} < x_{10} < k_{10}\}$, I want to find how many $y_{10}$ exist such that $y_{10} \in S$ and $y_2$ contains the string "101"
I had no idea where to even begin this problem, so I brute-forced the solution.
What is the "proper" approach that won't take up ten minutes?
 [/INST] A practical method for tests
I had a go at solving your problem by recurrence relations in 'test conditions'. This did work but I found it much easier to write out the solution by splitting up the interval into simple chunks. So for your example the working would be as follows
$\begin{vmatrix}1&1&0&0&0&1&1&1 \\1&1&0&0&0&0&0&0\\\end{vmatrix}  1 \text { number}$
$\begin{vmatrix}1&0&1&1&1&1&1&1 \\1&0&1&0&0&0&0&0\\\end{vmatrix}  2^5 \text { numbers} $
$\begin{vmatrix}1&0&0&1&1&1&1&1 \\1&0&0&0&0&0&0&0\\\end{vmatrix}  3\times4-1 $
Then we can ignore the two most significant bits
$\begin{vmatrix}1&1&1&1&1&1 \\1&1&0&0&0&0\\\end{vmatrix}   3\times4-1-4$
$\begin{vmatrix}1&0&1&1&1&1 \\1&0&1&0&0&0\\\end{vmatrix}   2^3 \text{ numbers}$
$\begin{vmatrix}1&0&0&1&1&1 \\1&0&0&1&0&0\\\end{vmatrix}   1 \text { number}$
Total=$60$.
This example is 'general' in the sense that it shows how one can deal with all three possibilities for the most significant bits:-
$\begin{vmatrix}1&1\\\end{vmatrix}$
$\begin{vmatrix}1&0&1\\\end{vmatrix}$
$\begin{vmatrix}1&0&0\\\end{vmatrix}$
</s>