Find n-th number in a number system with only 3 and 4

Question

There is a solution given here but its very vague without explaining the mathematics/ concept behind it. Can someone please help derive the logic for framing an algorithm for this question?

One approach that crosses my mind is, we can think of this number system as also a binary one ( in 3 and 4, instead of 1 and 0) Thus, we could possibly convert the nth number to its corresponding binary format and replace 0 with 3 and 1 with 4. One problem here though is that say the nth number is 333. This in the regular (0 and 1) binary system would be 000 = 0, which evidently is wrong since the nth number is not 0.

How do we go about this question?

Answer 1

See bijective numeration, especially the algorithm that gives the digit-string representing the integer $m > 0$. (I.e., find the bijective base-2 expression for $m$, then replace each $1\to 3$ and each $2\to 4$.)

Answer 2

In terms of the usual binary representation of numbers, you can find the $\{3,4\}$-representation of a number $n$ as follows:

1. Let $k = \lfloor \log_2 (n+1)\rfloor$, so that $2^k-1 \le n < 2^{k+1}-1$. We know that there are a total of $2 + 4 + 8 + \dots + 2^{k-1} = 2^k - 2$ numbers whose $\{3,4\}$-representation will have $k-1$ or fewer digits, so $n$ will use $k$ digits.
2. Find the binary representation of $n - 2^k + 1$. Pad it with $0$'s at the beginning, if necessary, to make sure it has length $k$.
3. Add $3$ to each digit of that representation to get the $\{3,4\}$-representation of $n$.

(This works because step 1 ensures that the correct numbers have a $k$-digit representation, while steps 2-3 ensures that the numbers with a $k$-digit representation are correctly ordered.)

For example, if we start with $n = 20$:

1. We get $k = \lfloor\log_2(20+1)\rfloor = 4$, so we know that the $\{3,4\}$-representation of $20$ has $4$ digits.
2. We write $n - 2^k + 1 = 20 - 16 + 1 = 5$ in binary as $101_2$, and then pad it to $0101_2$.
3. We add $3$ to each digit, concluding that $20 = 3434_{\{3,4\}}$.