23
\$\begingroup\$

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.

\$\endgroup\$
2

29 Answers 29

7
\$\begingroup\$

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.

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

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
\$\endgroup\$
5
\$\begingroup\$

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]
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ Beat me to it! Although mine was 65 bytes... \$\endgroup\$
    – emanresu A
    Feb 16, 2021 at 9:07
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Apparently the second code works in one line for 29. \$\endgroup\$
    – Bubbler
    Feb 16, 2021 at 4:48
  • 1
    \$\begingroup\$ -1 byte for the top one. \$\endgroup\$
    – Bubbler
    Feb 16, 2021 at 14:14
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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(^)
\$\endgroup\$
3
\$\begingroup\$

Perl 5 -n, 58 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ A closure is a valid function submission. Also golfed the body to get 88 bytes. \$\endgroup\$
    – Bubbler
    Feb 17, 2021 at 6:52
  • \$\begingroup\$ 87 bytes. \$\endgroup\$
    – Bubbler
    Feb 17, 2021 at 6:57
3
\$\begingroup\$

K (ngn/k), 25 20 18 bytes

-2 bytes thanks to coltim

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

Try it online!

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

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

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

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

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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'
\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 11 bytes \$\endgroup\$
    – Shaggy
    Apr 19, 2021 at 9:13
2
\$\begingroup\$

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
]
\$\endgroup\$
1
  • \$\begingroup\$ A little bit shorter with strings: Try it online! \$\endgroup\$
    – chunes
    Apr 8, 2021 at 11:10
1
\$\begingroup\$

Stax, 13 bytes

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

Run and debug it

A generator with a filter.

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 54 bytes

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

Try it online!

Returns a StringJoin of digits.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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`
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

PowerShell, 77 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

Perl 5 (-l060p), 51 bytes

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

Try it online!

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

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!

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 16 bytes

←0W⊖θ«←⮌θ≔⍘⊖Lθ²θ

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

←0

Output the trailing 0.

W⊖θ«

Repeat until N=1.

←⮌θ

Prepend N to the output.

≔⍘⊖Lθ²θ

Replace N with its binary decremented length.

20 bytes for decimal input:

Nθ←0W⊖θ«←⮌⍘θ²≔⊖L⍘θ²θ

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

Nθ

Input N.

←0

Output the trailing 0.

W⊖θ«

Repeat until N=1.

←⮌⍘θ²

Prepend N's binary representation to the output.

≔⊖L⍘θ²θ

Replace N with its decremented binary length.

\$\endgroup\$

Your Answer

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

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