Find n-th number in a number system with only 3 and 4 Given a number system with only 3 and 4. Find the nth number in the number system.

There is a solution given here but its very vague without explaining the mathematics/ concept behind it. Can someone please help me 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.
You're on the right track, it is similar to binary in a way.

The first step to coming up with an efficient solution is to recognize that to convert a number from the $3,4$ system to decimal, you can treat $3$'s like a $1$ in binary, they have a value equivalent to $2^n$ where $n$ is the position of the digit, starting from the right $n$ starting at $0$.  Thus $3 \equiv 1$, $33 \equiv 3$, $333\equiv 7$, etc.

A $4$ has a value equivalent to $2^{n+1}$ starting from the right $n$ starting at $0$, so $4\equiv2$, $44 \equiv 6$, etc.

Because of the similarity to binary, we can convert our input (the decimal number) to binary, and then convert that to $3,4$.  To do so, we can use the following algorithm.

Given a binary number, iterate through the digits from right to left.


If the digit encountered is a $1$, place a $3$ for that digit in the result.
If the digit encountered is a $0$, and there are more digits following, place a $4$ for this digit in the result, and for any consecutive $0$'s, place a $3$ for those digits until a $1$ is encountered.  When a $1$ is encountered following a $0$ or series of $0$'s, if there are more digits following, change this $1$ to a $0$, and repeat step $2$ as if this were the first $0$ you've encountered.  When a $1$ is encountered and no more digits are following it, do nothing and return the result.


This reason this works is the following


Step $1$ uses the fact that $3$ has the same value in $3,4$ as $1$ does in binary.
Step $2$ is necessary because in $3,4$ there is no $0$ value for any digit.  Using the fact that $2^n = 2^{n-1} \times 2 = 2^{n-1} + 2^{n-1}$ we convert a $1$ followed by $n$ $0$'s to its equivalent form in $3,4$ of $n-2$ $3$'s followed by a $4$. The first $3$ has a value of $2^{n-1}$ and the remaining $3$'s and $4$ sum up to $2^{n-1}$.


This algorithm is roughly $O(\log n)$.