Variable Length Encoding of Integers Using a Modulus Algorithm
The first step is counting the number of strings of length $n$ in which no non-empty prefix is divisible by $3$. Surprisingly enough, these are given by Fibonacci numbers $F_n$ for $n &gt; 0$ (exercise). I will show how to map the natural numbers to strings of these forms, from which your encoding will follow. Divide the natural numbers into parts of lengths $1,F_1,F_2,F_3,\ldots$. Using the formula $F_1+\cdots+F_n = F_{n+2}-1$, we see that numbers $m$ in the range $F_{n+1} \leq m &lt; F_{n+2}$ will be encoded using strings of length $n$; additionally, $0$ will be encoded by the empty string. Given $m$, it should be straightforward to find $n$, for example using the Fibonacci recurrence or the approximate formula $F_n \approx \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n$.

Suppose $m &gt; 0$, and let $x = m - F_{n+1}$, so that $0 \leq x &lt; F_n$. It remains to encode $x$ as a string of length $n$ in which no non-empty prefix is divisible by $3$. The idea is to interpret the recurrence $F_n = F_{n-1} + F_{n-2}$ accordingly. There are many ways of doing it, here is one. There are $F_{n-1}$ legal strings of the form $0s$, and $F_{n-2}$ legal strings of the form $1\alpha s$, where $\alpha$ is determined so neither $\alpha s$ nor $1\alpha s$ are divisible by $3$. We can encode the first $F_{n-1}$ values of $x$ using strings of the form $0s$, and the latter $F_{n-2}$ values of $x$ using strings of the form $1\alpha s$. To determine $s$ itself, we run this procedure recursively. The base case is the unique string of length $1$, namely $1$.

To illustrate the entire procedure, let us show how to encode $m = 7$. First we find that $F_5 = 5 \leq 7 &lt; F_6 = 8$, and so $n = 4$ and $x = 7 - 5 = 2$. We write $F_4 = F_3 + F_2 = 2 + 1$, so that the encoded string is of the form $s_4 = 1\alpha_4 s_2$. The string $s_2$ itself is the encoding of $x - F_3 = 0$ of length $2$. Writing $F_3 = F_2 + F_1 = 1 + 1$, we see that $s_2$ has the form $s_2 = 0s_1$. The string $s_1$ itself is the encoding of $0$ of length $1$, which is $s_1 = 1$. Therefore $s_4 = 1\alpha_4 s_2 = 1\alpha_4 0s_1 = 1\alpha_4 01$. If $\alpha_4 = 0$ then $1001$ would be divisible by $3$, so $\alpha_4 = 1$ and the output is $1101$.