18
\$\begingroup\$

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

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

11 Answers 11

8
\$\begingroup\$

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ This is 1 byte shorter using V instead of .u: J]0VQjk~JsjR2srJ8 \$\endgroup\$
    – isaacg
    Jul 5, 2015 at 5:22
2
\$\begingroup\$

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

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

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

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]

\$\endgroup\$
2
  • \$\begingroup\$ 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)+$&[0]}}} \$\endgroup\$
    – blutorange
    Jul 3, 2015 at 20:31
  • \$\begingroup\$ @blutorange Nice! Totally forgot about upto and ! -- Thanks :) \$\endgroup\$
    – daniero
    Jul 3, 2015 at 21:36
1
\$\begingroup\$

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

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

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ You can convert numbers to strings with , the opposite of V. \$\endgroup\$
    – xigoi
    Apr 1, 2021 at 22:21
0
\$\begingroup\$

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

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

Stax, 12 bytes

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

Run and debug it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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