Binary Bunch on November 3rd

It appears there is no short,neat approach for this problem.

---

Counting Generalization

---

Let $B_j(k)$ denote the number of positive integers in $S$ containing $j$ number of $1$ 's. This can be expressed as $B_j(k) = \left\{ \begin{array}{rl} 0 & j = 0\\ \lfloor \log_2(k) \rfloor + 1 & j = 1 \\ \dbinom{\log_2(k)}{j} & j \geq 2, \quad k = 2^n, n \in \mathbb{Z}_{\geq 0} \\ \dbinom{\lfloor \log_2(k) \rfloor}{j} + B_{j - 1}\left(k - 2^{\lfloor \log_2(k)\rfloor}\right) & j \geq 2, \quad k \neq 2^n \end{array} \right.$ If $j = 0$ , clearly there is no positive integer that excludes $1$ 's.

If $j = 1$ , then the integers with singles are of the form $2^p$ , where $0 \leq p \leq \lfloor log_2(k)\rfloor$ .

Otherwise, if $2 \leq j \leq \lceil \log_2(k) \rceil$ , the counting depends on the $2$ -base-sum-representation of $k$ and the value of $j$ .

Subcase 1: If $k - 2^{\lfloor \log_2(k) \rfloor} = 0$ , then $k = 2^n$ for a positive integer $n$ . Then, we can freely count the number of $j$ -tuple integers with $\log_2(k)$ digits, which gives us $\binom{\log_2(k)}{j}$ .

Subcase 2: Otherwise, we determine the number of $(j - 1)$ -tuple integers for subset from $1$ to $k - 2^{\lfloor \log_2(k) \rfloor} > 0$ . Then, count all $j-tuples$ with $\lfloor \log_2(k)\rfloor$ digits.

Now, let's consider the leftmost digit, being $1$ . If $j - 1 = 1$ , then we simply substitute $(k - 2^{\lfloor \log_2(k) \rfloor})$ back to $B_1$ . Otherwise, $j - 1 \geq 2$ , which returns us to the subcases we consider. Repeat this until the sub $B$ 's in $B_j(k)$ terminate.

---

Problem

---

The value $k = 3^{11}$ can be presented as $3^{11} = 2^{17} + 2^{15} + 2^{13} + 2^{12} + 2^9 + 2^8 = 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2 + 1$ or the binary representation $101011001111111011_2$ . Since we are interested in finding the integer in the ordered set, compute the total number of integers in binary form, starting from $j = 1$ . Notice that the values in each $\log_2$ are in fact base- $2$ exponents in decreasing order from the sum.

So $\sum\limits_{p=1}^8 B_p(k) = 88047$ . So we look at the last of the first $88574 - 88047 = 527$ integers with nine $1$ 's. Digit-chasing, we have $1110111110010_2$ , which is equivalent to the integer $\boxed{7666}$ .