# Compute the Kolakoski sequence

This is a repost of an old challenge, in order to adjust the I/O requirements to our recent standards. This is done in an effort to allow more languages to participate in a challenge about this popular sequence. See this meta post for a discussion of the repost.

The Kolakoski sequence is a fun self-referential sequence, which has the honour of being OEIS sequence A000002 (and it's much easier to understand and implement than A000001). The sequence starts with 1, consists only of 1s and 2s and the sequence element a(n) describes the length of the nth run of 1s or 2s in the sequence. This uniquely defines the sequence to be (with a visualisation of the runs underneath):

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,...
= === === = = === = === === = === === = = === = = === === = === =
1, 2,  2, 1,1, 2, 1, 2,  2, 1, 2,  2, 1,1, 2, 1,1, 2,  2, 1, 2, 1,...


Your task is, of course, to implement this sequence. You may choose one of three formats to do so:

1. Take an input n and output the nth term of the sequence, where n starts either from 0 or 1.
2. Take an input n and output the terms up to and including the nth term of the sequence, where n starts either from 0 or 1 (i.e. either print the first n or the first n+1 terms).
3. Output values from the sequence indefinitely.

In the second and third case, you may choose any reasonable, unambiguous list format. It's fine if there is no separator between the elements, since they're always a single digit by definition.

In the third case, if your submission is a function, you can also return an infinite list or a generator in languages that support them.

You may write a program or a function and use any of our standard methods of receiving input and providing output. Note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in bytes – wins.

# Br**nfuck, 96 bytes

+.+..<<+.[.[[>>]<+<[<<]>>-]>>[>>]<[>[>>]+++<<[<]>>-]<[<+>>+<-]>[>->>[-<]<<[<]>-]<<[>+<-]>[<<]>>]


Try it online!

This prints terms indefinitely.

### Explanation

+.+..<<+.[                       Initialize the tape with {1, 0, 2} (printing the first four terms). Start an infinite loop.
.[ [>>] <+< [<<] >>- ]           Print the first value and move it to the end. Let's call it n.
>> [>>]                          Move to the end of the filled part of the tape.
<[                               n times:
> [>>] +++<< [<] >>-             Make a three on the end.
]
< [<+>>+<-]                      Copy the last sequence value calculated, k.
>[>->>[-<]<<[<]>-]               Subtract k from all the 3s made earlier.
<<[>+<-]>                        Move the copied k back into place.
[<<]>>                           Return to the start of the tape.
]                                End loop.


I've been trying to save some bytes by including no empty cells between terms. No luck so far, but maybe someday soon...

Pastebin of the (naïvely) transpiled .java file. Outputs as base-10 numbers, each on a line. Come to think of it, unary is probably the way to go for this challenge...

• Why would you censor "brain" but not "fuck"... ? – Esolanging Fruit Mar 8 '18 at 5:56
• @EsolangingFruit It seems to be a variant of one of the name variants of BF – Conor O'Brien Mar 8 '18 at 18:18

b=*a=2;loop{b+=[a^=3]*p(b[$.+=1]||a)}  Try it online! Prints an infinite sequence of numbers separated by newlines. -1 byte thanks to Martin Ender. # CJam, 3127 23 bytes Prints the first n entries. l~H3b{ee{(2%)+}%e~}2$*<


Try online

• You can replace [1 2 2] with H3b (convert 17 to base 3). – Esolanging Fruit Mar 20 '18 at 5:27
• Good catch! Answer updated. – Chiel ten Brinke Mar 20 '18 at 10:01
@_[2+$++] # From the next element in the sequence |( ) # And add those elements to the sequence  • 41 bytes (I think it's OK to simply return an infinite sequence. 47 bytes, otherwise.) – nwellnhof Oct 5 '18 at 9:42 • @nwellnhof Neat. I didn't know you could add more than one element to the list at a time, thanks! – Jo King Oct 5 '18 at 9:54 # APL (Dyalog Unicode), 34 bytes 1{⎕←⍺⌷⍵⋄(1+⍺)∇⍵,⍵[2+⍺]⍴2-2|⍺}1 2 2  Try it online! I'm flabbergasted that there was no APL answer to this challenge yet. This is a full program that outputs the sequence indefinitely. Thanks to @dzaima for -3 bytes. ### How 1{⎕←⍺⌷⍵⋄(1+⍺)∇⍵,⍵[2+⍺]⍴2-2|⍺}1 2 2 ⍝ Full program. Inputs ⍺=1, ⍵=1 2 2 ⎕← ⍝ Print ⍺⌷⍵ ⍝ the ⍺th element of ⍵ ⋄ ⍝ Then (1+⍺)∇ ⍝ Recurse with ⍺=⍺+1 and ⍵= ⍵, ⍝ append to ⍵ 2-2|⍺ ⍝ 2 minus ⍺ modulo 2 ⍴ ⍝ reshape (repeats right arg, left arg times) ⍵[2+⍺] ⍝ using the (2+⍺)th element of ⍵  # Jelly, 21 bytes 3_ṪẋŒgL‘ịƲ⁸; 2RxÇ⁸¡ḣ  Try it online! # Jelly, 15 bytes R€a"JḂ$Fo2
2Ç¡ḣ


A monadic link accepting an integer n which yields the first n terms.

Try it online!

# Wolfram Language (Mathematica), 59 bytes

Nest[Flatten@*MapIndexed[Mod[#2,2,1]~Table~#&],{2},#][[#]]&


Try it online!

# MIPS, 128124108 88 bytes

Changelog:

• Mar 24: Fix mod
• Mar 25: Simplify algorithm (no need to push n)
• Mar 26: Simpler algorithm using stack

 Address    Code        Basic                     Source

0x00400000  0x24020001  addiu $2,$0,0x00000001    8         li      $v0, 1 # print first 3 vals 0x00400004 0x2404007a addiu$4,$0,0x0000007a 9 li$a0, 122
0x00400008  0x0000000c  syscall                   10        syscall
0x0040000c  0x24180002  addiu $24,$0,0x0000000    12        li      $t8, 2 # const 2 0x00400010 0xafb8fff4 sw$24,0xfffffff4($29) 13 sw$t8, -12($sp) # l[3] = 2 0x00400014 0x24080003 addiu$8,$0,0x00000003 14 li$t0, 3          # n = 3
0x00400018  0x23a9fff4  addi $9,$29,0xfffffff4    15        addi    $t1,$sp, -12   # i = l + 3
0x0040001c  0x23abfff4  addi $11,$29,0xfffffff    16        addi    $t3,$sp, -12   # ln = l + 3
0x00400020  0x31040001  andi $4,$8,0x00000001     19        andi    $a0,$t0, 1     # n%2
0x00400024  0x03042022  sub $4,$24,$4 20 sub$a0, $t8,$a0   # x = 2 - n%2
0x00400028  0xad24fffc  sw $4,0xfffffffc($9)      21        sw      $a0, -4($t1)    # *(i+1) = x
0x0040002c  0x0000000c  syscall                   24        syscall                 # print x
0x00400030  0x8d6c0000  lw $12,0x00000000($11)    26        lw      $t4, ($t3)      # temp = *ln
0x00400034  0x20010002  addi $1,$0,0x00000002     27        bne     $t4, 2, kol2 # if temp == 2 0x00400038 0x142c0003 bne$1,$12,0x00000003 0x0040003c 0xad24fff8 sw$4,0xfffffff8($9) 29 sw$a0, -8($t1) # *(i+2) = x 0x00400040 0x0000000c syscall 32 syscall # print x 0x00400044 0x2129fffc addi$9,$9,0xfffffffc 34 addi$t1, $t1, -4 # i += 1 0x00400048 0x2129fffc addi$9,$9,0xfffffffc 37 addi$t1, $t1, -4 # i += 1 0x0040004c 0x21080001 addi$8,$8,0x00000001 38 addi$t0, $t0, 1 # n += 1 0x00400050 0x216bfffc addi$11,$11,0xfffffff 39 addi$t3, $t3, -4 # ln += 1 0x00400054 0x08100008 j 0x00400020 40 j koll  ## Old solution  Address Code Basic Source 0x00400040 0x23bdfff4 addi$29,$29,0xfffffff 32 addi$sp, $sp, -12 # allocate 3 ints 0x00400044 0xafbf0000 sw$31,0x00000000($29) 33 sw$ra, ($sp) # push$ra
0x00400048  0x20010001  addi $1,$0,0x00000001     34        bne     $a0, 1, kol1 # if n == 1 0x0040004c 0x14240002 bne$1,$4,0x00000002 0x00400050 0x00041021 addu$2,$0,$4             35        move    $v0,$a0                # return n
0x00400054  0x08100026  j 0x00400098              36        j       kolret
0x00400058  0x24100001  addiu $16,$0,0x0000000    39        li      $s0, 1 # k = 1 0x0040005c 0x00048821 addu$17,$0,$4            40        move    $s1,$a0                # x = n
0x00400060  0xafb00004  sw $16,0x00000004($29)    43        sw      $s0, 4($sp)             # push k
0x00400064  0xafb10008  sw $17,0x00000008($29)    44        sw      $s1, 8($sp)             # push x
0x00400068  0x00102021  addu $4,$0,$16 45 move$a0, $s0 # arg1 = k 0x0040006c 0x0c100010 jal 0x00400040 46 jal kol # f(k) 0x00400070 0x8fb00004 lw$16,0x00000004($29) 48 lw$s0, 4($sp) # pop k 0x00400074 0x8fb10008 lw$17,0x00000008($29) 49 lw$s1, 8($sp) # pop x 0x00400078 0x02228822 sub$17,$17,$2            51        sub     $s1,$s1, $v0 # x -= f(k) 0x0040007c 0x20010001 addi$1,$0,0x00000001 52 bgt$s1, 1, kol4            # if x <= 1
0x00400080  0x0031082a  slt $1,$1,$17 0x00400084 0x14200007 bne$1,$0,0x00000007 0x00400088 0x02301020 add$2,$17,$16            53        add     $v0,$s1, $s0 # r = x + k 0x0040008c 0x20420001 addi$2,$2,0x00000001 54 addi$v0, $v0, 1 # r = x + i + 1 0x00400090 0x30420001 andi$2,$2,0x00000001 55 andi$v0, $v0, 1 # r = (x + k + 1) % 2 0x00400094 0x20420001 addi$2,$2,0x00000001 56 addi$v0, $v0, 1 # ret (x+k+1)%2 + 1 0x00400098 0x8fbf0000 lw$31,0x00000000($29) 59 lw$ra, ($sp) # pop$ra
0x0040009c  0x23bd000c  addi $29,$29,0x0000000    60        addi    $sp,$sp, 12            # free stack memory
0x004000a0  0x03e00008  jr $31 61 jr$ra
0x004000a4  0x22100001  addi $16,$16,0x0000000    64        addi    $s0,$s0, 1             # k += 1
0x004000a8  0x08100018  j 0x00400060              65        j       kolw


Assembly-friendly algorithm I came up with, based on Benoit Cloitre's OEIS formula:

def f(n):
if n == 1: return n
k = 1
x = n
while True:
x -= f(k)

if x <= 1:
return (x + k + 1)%2 + 1

k += 1

for n in range(1, 10):
print(f(n), end=',')


# PHP, 61 bytes

for($v=2;$n<$argn;$s.=$v^=3,$x>1&&$s.=$v)echo$x=$s[$n++]?:$n;


prints the first $$\n\$$ elements without a separator. Run as pipe with -nr` or try it online.