# Given an integer, compute its Levenshtein code

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

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].

# Python, 49 bytes

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


Test it on Ideone.

# Mathematica, 61 bytes

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

• I'm pretty sure you can save a few bytes by defining a unary operator ± instead of a function f. Aug 15, 2016 at 7:43

## 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.

• I think you can safely use replace(1,... instead of replace(/1/,... => 52 bytes Aug 15, 2016 at 20:31

# Jelly, 13 11 bytes

Ḣ;LÑ$; BÇṀ¡  ### 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.  # 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.  # 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) # 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.

# 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

# 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".

# Husk, 14 bytes

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


Try it online!

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

• Nice! I tried answering this challenge myself but had trouble with the inference. Oct 29, 2020 at 15:35
• @LegionMammal978 Somehow making a [0] list was difficult. :D Oct 29, 2020 at 15:36