Given an integer, compute its Levenshtein code

Question

^{Disclaimer: Levenshtein coding is completely unrelated to the Levenshtein edit distance metric.}

<Insert long story about why Levenshtein codes need to be calculated here.>

The code

Levenshtein coding is a system of assigning binary codes to nonnegative integers that retains some weird property in probability which isn't relevant for this challenge. We will denote this code as L(n). Wikipedia describes this as a five-step process:

1. Initialize the step count variable C to 1.
2. Write the binary representation of the number without the leading 1 to the beginning of the code.
3. Let M be the number of bits written in step 2.
4. If M is not 0, increment C, repeat from step 2 with M as the new number.
5. Write C 1 bits and a 0 to the beginning of the code.

However, the code can also be described recursively:

1. If the number is 0, then its code is 0.
2. Write the binary representation of the number without the leading 1 to the beginning of the code.
3. Let M be the number of bits written in step 2.
4. Write L(M) to the beginning of the code.
5. Write a 1 bit to the beginning of the code.

For those who prefer examples, here is the recursive process for L(87654321), with denoting concatenation:

The challenge

Write a program or function that, given a number n, outputs the bitstring L(n) in any reasonable format (this includes returning a number with said bits). Standard loopholes are, as always, disallowed.

Examples

Input: 5

Output: 1110001

Input: 30

Output: 111100001110

Input: 87654321

Output: 111110000101001001110010111111110110001

Input: 0

Output: 0

Answer 1

Haskell, 70 bytes

b 0=[]
b n=b(div n 2)++[mod n 2]
f 0=[0]
f n|1:t<-b n=1:f(length t)++t

Defines a function f : Int -> [Int]. For example, f 5 == [1,1,1,0,0,0,1].

Answer 2

Python, 49 bytes

f=lambda n:n and'1%s'%f(len(bin(n))-3)+bin(n)[3:]

Test it on Ideone.

Answer 3

Mathematica, 61 bytes

f@0={0};f@n_:=Join[{1},f@Length@#,#]&@Rest@IntegerDigits[n,2]

Answer 4

JavaScript (ES6), 54 52 bytes

f=n=>(s=n.toString(2)).replace(1,_=>1+f(s.length-1))

<input type=number oninput=o.textContent=f(+this.value)><pre id=o>

Edit: Saved 2 bytes thanks to @Arnauld.

Answer 5

Jelly, 13 11 bytes

Ḣ;LÑ$;
BÇṀ¡

Try it online! or verify all test cases.

How it works

The submission consists of a pair of mutually recursive links.

BÇṀ¡    Main link. Argument: n

B       Convert n to binary.
   ¡    Execute...
 Ç        the helper link...
  Ṁ       m times, where m is the maximum of n's binary digits.

Ḣ;LÑ$;  Helper link. Argument: A (array of binary digits)

Ḣ       Head; remove and return the first element of A.
    $   Combine the two links to the left into a monadic chain.
  L       Yield the length (l) of A without its first element.
   Ñ      Call the main link with argument l.
 ;      Concatenate the results to both sides.
     ;  Append the tail of A.

Answer 6

Pyth, 12 bytes

L&bX1.Bbyslb

Demonstration

(The y at the end is to run the resulting function on the input)

Explanation:

L&bX1.Bbyslb
L               def y(b):
 &b             If b is 0, return 0. This is returned as an int, but will be cast
                to a string later.
          lb    Take the log of b
         s      Floor
        y       Call y recursively
   X1           Insert at position 1 into
     .Bb        Convert b to binary.

Answer 7

SQF, 110

Recursive function:

f={params[["i",0],["l",[]]];if(i<1)exitWith{[0]};while{i>1}do{l=[i%2]+l;i=floor(i/2)};[1]+([count l]call f)+l}

Call as: [NUMBER] call f

Note this doesn't actually work for 87654321 or other large numbers due to a bug in the ArmA engine. Although it will probably be fixed soon, and should work according to spec.

(This Ticket Here)

Answer 8

PHP, 116 114 bytes

<?$f=function($i)use(&$f){$b=decbin($i);return!$b?0:preg_replace('/^1/',1 .$f(~~log10($b)),$b);};echo$f($argv[1]);

Provide the number as the first argument.

Update:

• Saved a byte by replacing strlen($b)-1 with ~~log10($b) (finally understood why everybody else was using logarithm) and another by concatenating differently.

Answer 9

Ruby, 38 bytes

Very similar to Neil's JavaScript answer.

f=->n{("%b"%n).sub(/1\K/){f[$'.size]}}

See it on repl.it: https://repl.it/CnhQ

Answer 10

Java 8 (Full Program), 257 249 bytes

interface M{static void main(String[]a)throws Exception{int i=0,j;while((j=System.in.read())>10)i=i*10+j-48;System.out.print(L(i));}static String L(int i){if(i==0)return "0";String s=Integer.toString(i,2);return "1"+L(s.length()-1)+s.substring(1);}}

Readable Version w/ Explanation (It's mostly just recursion):

interface M {
    static void main(String[]a) throws Exception { // Using Exception is unadvised in real coding, but this is Code Gold
        int i = 0, j; // i stores the input; j is a temporary variable
        while ((j = System.in.read()) > 10) // Read the input to j and stop if it is a newline. Technically this stops for tabulators as well, but we shouldn't encounter any of those...
            i = i * 10 + j - 48; // Looping this step eventually reads the whole number in from System.in without using a reader (those take up a lot of bytes)
        System.out.print(L(i)); // Make a method call
    }

    static String L(int i) { // This gets the actual Levenshtein Code
        if (i == 0)
            return "0"; // The program gets a StackOverflowException without this part
        String s = Integer.toString(i, 2); // Shorter than toBinaryString
        return "1" + L(s.length() - 1) + s.substring(1); // Write in the first character (which is always a one), followed by the next L-code, followed by the rest of the binary string
    }
}

EDIT 1: Saved 8 bytes: The first character of the binary string is always 1; therefore, rather than using s.charAt(0), a better option is simply "1".

Answer 11

Husk, 14 bytes

?ö:1Ṡ+o₀LtḋΘøI

Try it online!

Uses a simple recursive approach. (Dennis's double recursion is insane.)