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

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

• Output as list allowed? Like \n[1, 0]\n[1, 1, 1, 0]\n... Jul 3, 2015 at 17:07
• @Jakube No, you'll need to do a string join on it.
Jul 3, 2015 at 17:16
• Congrats on making a contribution to OEIS! Jul 3, 2015 at 20:24

# CJam, 18 17 bytes

0{sN1$e2af.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] [ '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 .
f.b     e#   For each pair [x 'y], execute: [x 'y].b
e#   This pushes [x2b 'y], where b is base conversion.


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

• This is 1 byte shorter using V instead of .u: J]0VQjk~JsjR2srJ8 Jul 5, 2015 at 5:22

# Python 2, 125116 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))


# 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

# Ruby, 8072 69 bytes

As a function:

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


Call it for example with: f

• You could save a few bytes if you take input as a function argument: ->m{l=?0;0.upto(m){puts l;l.gsub!(/1+|0+/){$&.size.to_s(2)+$&}}} Jul 3, 2015 at 20:31
• @blutorange Nice! Totally forgot about upto and ! -- Thanks :) Jul 3, 2015 at 21:36

# Python 2, 102 bytes

import re
o='0'
exec"print o;o=''.join(bin(len(x))[2:]+xfor 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...

# Jelly, 9 bytes

ŒrUBFƲÐ¡Y


Try it online!

Takes input from STDIN.

## Explanation

ŒrUBFƲÐ¡Y   Main niladic link
Ð¡    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


# Jelly, 16 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.

• You can convert numbers to strings with Ṿ, the opposite of V. Apr 1, 2021 at 22:21

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


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

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