Recursive Binary Description

Question

Recursive Binary Description

Recently, I made my very first contribution to OEIS by extending and adding a b-file to sequence A049064. The sequence starts with 0, and then the next values are derived from giving a "binary description" of the last item.

For example, the second term would be 10, because there was one 0 in the first element. The third term would be 1110, because there was one 1 and one 0. The fourth would be 11110. because there are three (11 in binary!) 1s and one 0. Below is a breakdown of the fifth term to make this process clear:

> 11110
> 1111 0    (split into groups of each number)
> 4*1 1*0   (get count of each number in each group)
> 100*1 1*0 (convert counts to binary)
> 100110    (join each group back together)

And here's an example for going from the 6th to the 7th term:

> 1110010110
> 111 00 1 0 11 0
> 3*1 2*0 1*1 1*0 2*1 1*0
> 11*1 10*0 1*1 1*0 10*1 1*0
> 111100111010110

You can check out a reference program^φ I made to calculate the terms.

Your Job

You need to create a program or function which takes in a number n via standard input or function arguments, and prints out the sequence from the 1st term to the (n+1)th term, separated by a newline. If you would like a look at the lower numbers, you may refer to the b-file from the OEIS page. However, your program/function should support 0 <= n <= 30, i.e. up to the 31st term. This is no small feat, as A049064(30) is over 140,000 digits long^δ. If you would like to see what the 31st term should be, I've put it on Pastebin.

Example I/O

func(10)
0
10
1110
11110
100110
1110010110
111100111010110
100110011110111010110
1110010110010011011110111010110
1111001110101100111001011010011011110111010110
1001100111101110101100111100111010110111001011010011011110111010110

func(0)
0

func(3)
0
10
1110
11110

There is only one rule: No standard loopholes!

This is code-golf, so the lowest byte count wins.

---

^{φ - Gist can be found here, and an ideone demo is here.}

^{δ - Just in case you were wondering, my estimates at the length of the 100th term put it at approximately 3.28x10250 characters long, which would be quite a lot for anyone to calculate.}

Answer 1

CJam, 18 17 bytes

0{sN1$e`2af.b}ri*

Thanks to @MartinBüttner for golfing off one byte!

Try it online in the CJam interpreter.

How it works

0                 e# Push 0.
 {           }ri* e# Repeat int(input)) times:
  s               e#   Stringify the element on top of the stack.
                       EXAMPLE: [[[1 1] '1] [[1] '0]] -> "11110"
   N              e#   Push a linefeed.
    1$            e#   Copy the last stack.
      e`          e#   Perform run-length encoding.
                  e#   EXAMPLE: "100110" -> [[1 '1] [2 '0] [2 '1] [1 '0]]
        2a        e#   Push [2].
          f.b     e#   For each pair [x 'y], execute: [x 'y][2].b
                  e#   This pushes [x2b 'y], where b is base conversion.

Answer 2

Pyth, 18 17 bytes

J]0VQjk~JsjR2srJ8

Try it online: Demonstration

Thanks to @isaacg for saving one byte.

Explanation:

                     implicit: Q = input number
 ]0                  create an initial list [0]
J                    and store in J
   VQ                for loop, repeat Q times:
              rJ8       run-length-encoding of J
             s          sum, unfolds lists
          jR2           convert each value to base 2
         s              sum, unfolds lists
       ~J               store the result in J

                        but return the old list,
     jk                 join it and print it

This uses the fact, that 0 and 1 in binary are also 0 and 1.

Answer 3

Python 2, 125 116 110 bytes

from itertools import*
v='0'
exec"print v;v=''.join(bin(len(list(g)))[2:]+k for k,g in groupby(v));"*-~input()

Saved 1 byte thanks to @Sp3000 and 5 bytes by removing a redundant int call.

Older version:

import itertools as t
v='0'
exec"print v;v=''.join(bin(int(len(list(g))))[2:]+k for k,g in t.groupby(v));"*-~input()

Saved many, many bytes thanks to @Vioz-!

Original version:

import itertools as t
v='0'
for n in range(input()+1):print v;v=''.join(bin(int(len(list(g))))[2:]+k for k,g in t.groupby(v))

Answer 4

K (ngn/k), 37 bytes

{,/{(,/$2\#x),*x}'(&~~':x)_x}\[;,"0"]

Try it online!

• {...}\[;,"0"] set up a scan, seeded with ,"0" and run for a number of times equal to the (implicit) input

• (&~~':x)_x split into groups of the same characters

• {...}' for each group...

  • (,/$2\#x) get the binary representation of the count of each group
  • (...),*x append the first character of each group (i.e. whether it is a group of 0s or of 1s)

• ,/ flatten the results and feed to the next iteration of the scan

Answer 5

Ruby, 80 72 69 bytes

As a function:

f=->m{l=?0;0.upto(m){puts l;l.gsub!(/1+|0+/){$&.size.to_s(2)+$&[0]}}}

Call it for example with: f[6]

Answer 6

Python 2, 102 bytes

import re
o='0'
exec"print o;o=''.join(bin(len(x))[2:]+x[0]for x in re.findall('0+|1+',o));"*-~input()

Somehow the combination of itertools being longer than re and groupby returning grouper objects means that using regex is a bit shorter...

Answer 7

Jelly, 9 bytes

ŒrUBFƲСY

Try it online!

Takes input from STDIN.

Explanation

ŒrUBFƲСY   Main niladic link
            Implicitly start with 0
      С    Repeat [number from STDIN] times and collect all values
     Ʋ      (
Œr            Run-length encode -> [[digit, repetitions], ...]
  U           Reverse each sublist -> [[repetitions, digit], ...]
   B          Convert all numbers to binary
    F         Flatten
     Ʋ      )
        Y   Join by newlines
            The numbers are automatically concatenated

Answer 8

Jelly, ¹⁶ 14 bytes

µṄŒrUFV€BFṾ€ø¡

Try it online!

I still feel like there's some better way to do the string printing.

-2 bytes from xigoi.

Answer 9

Cobra - 128

do(i)=if(i-=1,(r=RegularExpressions).Regex.replace(f(i),'1+|0+',do(m=r.Match())=Convert.toString('[m]'.length,2)+'[m]'[:1]),'0')

Answer 10

Haskell, 136 130 Bytes

import Text.Printf
import Data.List
f n=putStr.unlines.take(n+1).iterate(concatMap(\n->(printf"%b"$length n)++[head n]).group)$"0"

Answer 11

Stax, 12 bytes

î╩∩▬╒«ç╚¢↓}~

Run and debug it