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.


Input: 5

Output: 1110001

Input: 30

Output: 111100001110

Input: 87654321

Output: 111110000101001001110010111111110110001

Input: 0

Output: 0


11 Answers 11


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


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

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

JavaScript (ES6), 54 52 bytes

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

Edit: Saved 2 bytes thanks to @Arnauld.

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

Jelly, 13 11 bytes


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.

Pyth, 12 bytes



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


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.


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


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


Try it online!

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.