# Elias omega coding: encoding

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

# 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


# Dodos, 9691 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.

• I was worried that I got outgolfed, thankfully it was a different language :P – Razetime Feb 17 at 8:24
• Can't beat your Husk answer... Now try to outgolf me in Dodos @Razetime! :D – Leo Feb 17 at 8:26

# 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]        
L         -     length               4            2       1       1
’        -     decrement            3            1       0       0   <- 0=0: stop
}                     -> [12,3,1,0]
ṣ1    - split at ones            [[12,3],]
U   - upend                    [[3,12],]
B    - to binary                [[[1,1],[1,1,0,0]],]
F - flatten                  [1,1,1,1,0,0,0]


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

• Beat me to it! Although mine was 65 bytes... – A username Feb 16 at 9:07

# J, 29 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.

• Apparently the second code works in one line for 29. – Bubbler Feb 16 at 4:48
• -1 byte for the top one. – Bubbler Feb 16 at 14:14

# 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

# Vyxal, d, 15131110 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(^)


# Perl 5-n, 58 bytes

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


Try it online!

# 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
• A closure is a valid function submission. Also golfed the body to get 88 bytes. – Bubbler Feb 17 at 6:52
• – Bubbler Feb 17 at 6:57

# K (ngn/k), 2520 18 bytes

-2 bytes thanks to coltim

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


Try it online!

• Somehow I think the 2/ in the scan is unnecessary, e.g. (#1_2) returns the same results. – coltim Feb 18 at 22:29

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


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

• 54 bytes by getting rid of s and len(bin())-3 – ovs Feb 16 at 11:52
• @ovs Nice one - thanks! :D – Noodle9 Feb 16 at 11:59

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

# 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


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

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

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

• A little bit shorter with strings: Try it online! – chunes Apr 8 at 11:10

# Stax, 13 bytes

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


Run and debug it

A generator with a filter.

# Wolfram Language (Mathematica), 54 bytes

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


Try it online!

Returns a StringJoin of digits.

# 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={0};d++;n>1&&f(strlen(s)-1,itoa(n,s,2));printf(--d?s:"%s0",s);}


Try it online!

# 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


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

# R, 7064 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...

param($n)while($n-1){$s=($l=[Convert]::ToString($n,2))+$s;$n=$l.Length-1}$s+0  Try it online! # 05AB1E, 10 bytes Î[b©#®ì®g<  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  # Perl 5 (-l060p), 51 bytes $\=($,=sprintf"%b",$_).$\,$_=-1+length$,while$_>1}{


Try it online!

• Use -~ instead of -1+. – Neil Feb 16 at 10:52
• @Neil, unfortunatelly it doesn't work, maybe -2-~,Try it online! but it's longer – Nahuel Fouilleul Feb 16 at 11:17
• Sorry, I hadn't realised it parses as $_ =~ - length$,... – Neil Feb 16 at 13:11

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

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