Elias omega coding: encoding

Question

Background

Elias omega coding is a universal code which can encode positive integers of any size into a stream of bits.

Given a positive integer \$N\$, the encoding algorithm is as follows:

1. Start with a single zero in the output.
2. If \$N=1\$, stop.
3. Prepend the binary digits of \$N\$ to the current output.
4. Let \$N\$ be the number of digits just prepended, minus one. Go back to step 2.

In Python-like pseudocode:

n = input()
s = "0"
while n > 1:
    # bin(n) is assumed to give a plain string of bits, without "0b" prefix
    s = bin(n) + s
    n = len(bin(n)) - 1
output(s)

Illustration

The number 1 gets encoded into a single 0.

The number 21 gets encoded into 10100101010, or 10 100 10101 0 in chunks, where each chunk is added to the output stream in the following order: first "0" by default, then the binary of 21, then 4 (the bit length of 21 minus 1), then 2, then stop.

Task

Given a positive integer \$N\$, output its Elias omega code.

You can take the input number \$N\$ in any convenient format, including its representation in binary.

The output must be a valid representation of a flat stream of bits, which includes:

• a plain string or array of zeros and ones, or
• a single integer whose binary representation corresponds to the stream of bits.

Outputting the bits in reverse or outputting a nested structure of bits (e.g. ["10", "100", "10101", "0"] for 21) is not allowed.

Shortest code in bytes wins.

Test cases

N     => Omega(N)
1        0
2        100
3        110
4        101000
5        101010
6        101100
7        101110
8        1110000
12       1111000
16       10100100000
21       10100101010
100      1011011001000
345      1110001010110010
1000     11100111111010000
6789     11110011010100001010
10000    111101100111000100000
1000000  1010010011111101000010010000000

This is OEIS A281193.

Answer 1

Dodos, 96 91 90 bytes

	> > E
	+ >
E
	E - + L B
	> B
B
	B + L H
	+ H
L
	>
	> -
H
	H - -
	+ >
-
	dip
+
	dot
>
	dab

Try it online!

I've re-discovered this crazy and wonderful language today, so I've wasted two hours building this :D

Explanation

Dodos programs are composed by a series of function definitions, each non-indented symbol here is a function name and the indented lines following the symbol are the definition (the first 2 lines are the definition of the main function).

Each function takes a list of number as input and produces new list by concatenating in a list the outputs of the definitions of each line. Each line can be interpreted as function composition, where F G H means F(G(H(input))).

Recursion is where the crazy part really start: if while computing a function F(x) we try computing F(y) for any y≤x, then Dodos surrenders and returns the input unchanged. This prevents infinite recursion from happening, and it is the only form of conditional branching in the language. It can take a while to enter the right mindset to write anything in Dodos ^^"

So, starting from the bottom let's see what these functions are doing:

dab, dot, and dip are the only three builtin commands in Dodos, here redefined as >, +, and - to save bytes in the rest of the program. dab returns the input list without the first element; dot sums all elements of the input list (and returns 0 if the list is empty); dip subtracts 1 from each element of the list and then takes the absolute value of each element: negative numbers don't exist in Dodos! Any time we try to subtract 1 from 0 we obtain 1 as a result.

I had originally written much more about the rest, but this post is long enough as it is, so I will only provide descriptions of the input/output of each function. Trying to understand how each function works can be a good exercise, but if you want more information leave me a comment and we can discuss more in chat :)

H - Input: a number n. Output: n%2 followed by (0 repeated n//2 times)

L - Input: a list of 0s and 1s l. Output: [tail(l),tail(l) with each bit flipped] (hint: + L will compute the length of l - 1)

B - Input: a number n. Output: the binary representation of n, with a leading 0

E - Input: a number n. Output: the Elias omega coding of n, with an extra leading 01 and missing the trailing 0.

main - Input: a number n. Output: the Elias omega coding of n.

Answer 2

Husk, ^{16 13} 11 bytes

ṁḋ↔Θ↑←¡ȯ←Lḋ

Try it online!

Outputs a flat boolean array.

-2 using the idea from Jonathan Allan's answer.

Explanation

ṁḋ↔Θ↑←¡ȯ←Lḋ
      ¡ȯ    create an infinite list using:
         Lḋ length of binary digits
        ←   decremented  
    ↑       take the longest prefix with:
     ←       elements that aren't falsy when decremented(1)
   Θ        prepend 0 to that
  ↔         reverse
ṁḋ          convert each to binary and flatten

Answer 3

Jelly,  11  10 bytes

^{Is there a trick to make for shorter code?}

BL’ƊƬṣ1UBF

A monadic Link accepting a positive integer which yields a list of ones and zeros.

Try it online!

How?

BL’ƊƬṣ1UBF - Link: n           e.g. n=12
    Ƭ      - collect up starting with n until no change:
   Ɗ       -   last three links as a monad:        (3)     (1)     (0)
B          -     to binary            [1,1,0,0]    [1,1]   [1]     [0]
 L         -     length               4            2       1       1
  ’        -     decrement            3            1       0       0   <- 0=0: stop
             }                     -> [12,3,1,0]
     ṣ1    - split at ones            [[12,3],[0]]
       U   - upend                    [[3,12],[0]]
      B    - to binary                [[[1,1],[1,1,0,0]],[0]]
         F - flatten                  [1,1,1,1,0,0,0]

Answer 4

JavaScript (ES6), 50 bytes

With .toString(2)

f=(n,s=0,b=n.toString(2))=>n-1?f(b.length-1,b+s):s

Try it online!

Without .toString(2)

f=(n,i,q=n*2>>i)=>n>!!i?q?f(n,-~i)+q%2:f(i-2,1):''

Try it online!

Answer 5

J, ²⁹ 28 bytes

1;@}.1#:&.>@|.&|.<:@#@#:^:a:

Try it online!

^{This approach, which I prefer to the strightforward recursion, is thanks to Jonathan Allen's nice idea.}

^{-1 thanks to Bubbler}

• <:@#@#:^:a: Iteratively convert to binary #:, get size #, and decrement <:, keeping track of results a:.
• 1...&|. Reverse both arguments &|. (1 on the left, and the output of the previous step on the right). A golfy way to include the constant 1 (which is unaffected by reversal, and which we'll use in the next step) while reversing step 1's output.
• |. Rotate by 1. So now we have the output of step 1 reversed and rotated left by 1. Importantly, the 0 is now in the correct place all the way on the right, though we still have a stray 1 at the beginning...
• #:&.>@ Convert to binary #: under open &.>. A golfy way to convert every element to binary and box it.
• 1;@}. Kill the first element 1...}. (the stray 1) and raze ; (unbox so we have a single list of numbers)

J, 29 bytes (recursive approach)

0&g=.((,~g<:@#@])#:)`[@.(1=])

Try it online!

^{-3 thanks to Bubbler's realization we could 1-line it}

Straightforward implementation of the recursion formula.

Answer 6

Add++, 70 bytes

D,f,@,BBBFJ
D,g,@,bL1_
+?
n:x
y:'0'
Wn,`s,$f>x,`x,$g>s,`y,s+,`n,x-1
Oy

Try it online!

Add++ isn't too golfy.

f is a function that converts its input to a binary string. g gets a string and returns it's length minus one.

We then set x and n equal to the input, and y equal to the string '0'. Now, we enter a while loop, looping while n is non-zero. The loop has the following steps:

• Set s equal to f(x)
• Set x equal to g(s)
• Prepend s to y
• Set n equal to x - 1

Finally, output y

Answer 7

Vyxal, d, 15 13 11 10 9 bytes

≬bL‹↔1€Rb

Try it Online!

Explained (old)

≬bL‹↔1€Rb
≬bL‹         # lambda: len(bin(argument)) - 1
   ↔        # generate_until_no_change(^, input)
     1€      # ^.split(1)
       R     # map(reverse, ^)
        b    # bin(^)
             # `d` flag: deep_sum(^)

Answer 8

Perl 5 -n, 58 bytes

while($_>1){unshift@a,$_=sprintf"%b",$_;$_=y///c-1}say@a,0

Try it online!

Answer 9

Rust, 129 87 bytes

|mut n|{let mut s=0.to_string();while n>1{let b=format!("{:b}",n);n=b.len()-1;s=b+&s}s}

Try it online!

My first Rust answer! (and first time appeasing the Rust compiler gods)

A straight translation of the algorithm in the main post.

Ungolfed:

fn e(mut n: usize) -> String {
    let mut s = "".to_string();
    while n > 1 {
        let mut b = format!("{:b}", n);
        n = b.len() - 1;
        b.push_str(&s);
        s = b;
    }
    s+"0"
}

• -42 bytes from @Bubbler through a closure and miscellaneous golfs

Answer 10

K (ngn/k), 25 20 18 bytes

-2 bytes thanks to coltim

1_,/|0,2\'(#1_2\)\

Try it online!

Answer 11

Ruby, 39 bytes

f=->n,s=?0{n>1?f[/.$/=~x="%b"%n,x+s]:s}

Try it online!

Recursive function that takes \$N\$ as an integer. A regex match returns the index of the last bit in the binary representation of \$N\$, which is equivalent to one less than the bit length of \$N\$.

Answer 12

Zsh, 50 bytes

<<<${${1#?}:+`$0 ${$(([#2]$#1-1))#??} ''`}$1${2-0}

Try it online!

Neat recursive solution

<<<${${1#?}:+`$0 ${$(([#2]$#1-1))#??} ''`}$1${2-0}
                                          $1         # N
                                            ${2-0}   # $2, unless it is unset; then substitute "0"
   ${${1#?}:+                            }           # If after removing ?any digit from $1 there is something left, then substitute
             `$0                        `            # Backtick subshell, $0 is the current program
                 ${$(([#2]$#1-1))#??}                # Take the #length of $1, subtract one, substitute as 2#binary, remove the "2#"
                                      ''             # Add empty second argument to cause ${2-0} to substitute nothing on recursion
<<<                                                  # Print to stdout

Answer 13

Python 3, 57 56 bytes

Saved a byte thanks to ovs!!!

f=lambda n:n>1and f(len(f'{n:b}')-1)[:-1]+f'{n:b}0'or'0'

Try it online!

Inputs an integer and returns a string.

Answer 14

Scala, 74 bytes

x=>{var n->r=x->"0";while(n>1){val b=n.toBinaryString;r=b+r;n=b.size-1};r}

Try it online!

So this is a bit embarrassing: the imperative version is 13 bytes shorter.

Scala, 87 bytes

Seq.unfold(_){n=>val b=n.toBinaryString;Option.when(n>1)(b,b.size-1)}./:("0")(_.++:(_))

Try it online!

Answer 15

Japt, 19 bytes

@=¤T=U+T U=ÊÉ}f
Tj0

Try it

@ ... }f - return first falsey value returned by @
=¤       - convert input(U) to binary
T=U+T    - append to variable T(initially 0)
U=ÊÉ     - returns lenght -1 and assigns to U
Tj0      - discards first bit of T and implicitly print

Answer 16

C (clang), 87 86 bytes

l,a;g(n,b)char*b;{l=1;for(*b=48;n>1;n=a)for(a=0;bcopy(b,b+1,++l),*b=48+n%2,n/=2;)a++;}

Try it online!

• saved 1 thanks to @ceilingcat suggestion of using Linux bcopy instead of memcpy.

• function tacking a number n and a buffer b.

Explanation

• l length of result, used to shift the buffer.
• a length of current n.
• second for loop shifts the buffer by one and push next bit at the beginning.
• first loop resets n to length a which is already minus 1.
• initially we set l to 1 and the first bit to '0'

Answer 17

Japt, 14 bytes

É?T=¢+T,ߢÊÉ:T 
É?             // If input U - 1, aka if U > 1,
   =           // then assign
    ¢          // U to a binary string
     +T        // plus builtin variable T (initially zero),
  T            // to the builtin variable T.
       ,       // Following that,
        ß      // recursively run the application again with a new input of
          Ê    // the length of
         ¢     // the current input to binary string
           É   // minus one.
            :  // If the initial check was falsy instead,
             T // we're finished, return the result which is stored in T.

Try it here.

Answer 18

Factor + math.extras, 73 bytes

[ { f } swap [ [ make-bits append ] keep log2 ] until-zero reverse rest ]

Try it online!

Takes an integer and returns an array of fs and ts to represent 0 and 1 bits respectively (which is the default bit array representation). until-zero is two bytes shorter than dup 0 > loop. Also, make-bits gives the binary representation in LSB-first order (so 4 make-bits is { f f t }), so a reverse is needed at the end.

[                              ! A quotation, input: n
  { f } swap                   ! Put the initial s="0" under n
  [ ... ] until-zero           ! Repeat until n becomes zero...
    [ make-bits append ] keep  !   Append bits of n to s, and keep n at the top
    log2                       !   Next term (floor of log 2 = bit length - 1)
  reverse rest                 ! Reverse s and remove the part representing 1
]

Answer 19

Stax, 13 bytes

┴P&:ë▄▒ë╙G²╟ì

Run and debug it

A generator with a filter.

Answer 20

Wolfram Language (Mathematica), 54 bytes

Rest[#<>0//.a_/;a>1:>Floor@Log2@a<>a~IntegerDigits~2]&

Try it online!

Returns a StringJoin of digits.

Answer 21

C (MinGW), 79 bytes

Uses itoa() which is woefully lacking from the standard, but present on Windows systems.

The TIO link therefore contains a shoddy version of that function that only supports base 2.

d;f(n){int s[9]={0};d++;n>1&&f(strlen(s)-1,itoa(n,s,2));printf(--d?s:"%s0",s);}

Try it online!

Answer 22

Java 8, 77 bytes

n->{String r="0",b;for(;n>1;r=b+r,n=b.length()-1)b=n.toString(n,2);return r;}

Try it online.

Explanation:

n->{                    // Method with Integer parameter and String return-type
  String r="0",         //  Result-String, starting at "0"
         b;             //  Temp-String, uninitialized
  for(;n>1              //  Loop as long as `n` is larger than 1:
      ;                 //    After every iteration;
       r=b+r,           //     Prepend `b` to the result-String
       n=b.length()-1)  //     Set `n` to the length of `b` minus 1
    b=n.toString(n,2);  //   Set `b` to `n` converted to a binary-String
  return r;}            //  After the loop, return the result-String `r`

Answer 23

Retina, 50 bytes

^.
$.%'*_¶$&
+`(_+)\1
${1}0
/^../}`0?_
1
^.|¶

$
0

Try it online! Takes input in binary, but link includes test suite with decimal to binary conversion for convenience. Explanation:

/^../}`

While the input is greater than 1, ...

^.
$.%'*_¶$&

... prepend a decremented unary copy of the length...

+`(_+)\1
${1}0
0?_
1

... and convert from unary to binary.

^.|¶

$
0

Remove the last result, join the remaining results together and append a trailing 0.

Answer 24

R, 70 64 61 bytes

function(N){while(N>1)F=c(N%/%2^((N=log2(N)%/%1):0)%%2,F);+F}

Try it online!

To my disappointment, a no-frills iterative implementation of the pseudocode comes-out significantly shorter than my initial recursive approach...

Answer 25

PowerShell, 77 bytes

param($n)while($n-1){$s=($l=[Convert]::ToString($n,2))+$s;$n=$l.Length-1}$s+0

Try it online!

Answer 26

05AB1E, 10 bytes

Î[b©#®ì®g<

Try it online or verify all test cases.

Explanation:

Î         # Push 0 and the input-integer
 [        # Start an infinite loop:
  b       #  Convert the current integer to a binary string
   ©      #  Store this binary string in variable `®` (without popping)
          #  If this binary string is equal to 1:
    #     #   Stop the infinite loop
          #   (after which the string at the top is output implicitly as result)
   ®ì     #  Prepend binary string `®` in front of the current result-string
     ®g<  #  Push the length of `®` minus 1 for the next iteration

Answer 27

Perl 5 (-l060p), 51 bytes

$\=($,=sprintf"%b",$_).$\,$_=-1+length$,while$_>1}{

Try it online!

Answer 28

Red, 119 115 bytes

func[n][o: copy"0"until[t: copy[]until[insert t n % 2 n:
to 1 n / 2 1 > n]n:(length? t)- 1 insert o t n < 1]next o]

Try it online!

Answer 29

Charcoal, 16 bytes

←0Ｗ⊖θ«←⮌θ≔⍘⊖Ｌθ²θ

Try it online! Link is to verbose version of code. Takes input in binary. Explanation:

←0

Output the trailing 0.

Ｗ⊖θ«

Repeat until N=1.

←⮌θ

Prepend N to the output.

≔⍘⊖Ｌθ²θ

Replace N with its binary decremented length.

20 bytes for decimal input:

Ｎθ←0Ｗ⊖θ«←⮌⍘θ²≔⊖Ｌ⍘θ²θ

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input N.

←0

Output the trailing 0.

Ｗ⊖θ«

Repeat until N=1.

←⮌⍘θ²

Prepend N's binary representation to the output.

≔⊖Ｌ⍘θ²θ

Replace N with its decremented binary length.