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)$.
if (n == 1) return 3; else if (n == 2) return 4; else throw new ArgumentOutOfRangeException()is not the correct answer, the question needs improving. $\endgroup$ – Peter Taylor Mar 27 '18 at 7:33