Continuing on the theme from my last question Variable Length Encoding of Integers, I have come up with a simple encoding scheme, but for which an efficient algorithm eludes me.
The constraints are simple enough: no (binary representation) number is allowed where it is divisible by 3, or a subset (prefix) of that representation is divisible by 3.
To terminate the number two bits are added so that the number is divisible by 3.
For example 1101 is allowed since neither 1101, 101, 01 nor 1 are divisible by 3.
However, 1011 is not allowed since 11 is divisible by 3.
The representation 1101 would then have 10 prepended to make it divisible by 3 (101101).
All this allows a stream of bits to be read, at each point testing to see if the number is divisible by three. If not, keep reading the next bit, until it is divisble by three. Hence allowing for a (unique) variable length encoding.
My question is about the mapping of integers on to this encoding scheme. However hard I try I can't seem to create a straightforward algorithm to do the mapping. Is there one?
The examples above are to be read in the order right to left. So any prefix is on the right. So the stream of bits will be read right to left.