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

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

• {⍵{⍺↑⍵/⍺⍴⍳2}⍣⍵⍴⍨⍵} (port of the jelly answer) Jan 14, 2021 at 21:20

# 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! ## axo, 13 bytes [:|[1+{#;1;-_  Try it online! ### Explanation This started out as a port of an alternative solution in my Wumpus answer: 2%)[=]&=[O00.  This resulted in 18 bytes. I ended up golfing it down to the 13 bytes you see above to adjust it more to the way axo works. This 13-byte version then ended up inspiring the improvement down to 11 bytes in Wumpus, so now it's actually closer to that version. As in Wumpus, in iteration i, the bottom of the stack holds a(i)-1 and the top holds the first element of the ith run, but we're working with 0 and 1 throughout, except for printing. [: Store a copy of the top of the stack in register A. | Pull up a(i)-1 from the bottom of the stack. [1+{ Print a(i). #; If a(i)-1 is 1, push the value in register A. 1;- Push another copy of that value and subtract it from 1 to swap 0 and 1 for the next run. _ Jump back to the beginning of the program.  # Ruby, 45 39 bytes a=*i=0;loop{a+=[k=1+i%2]*p(a[i+=1]||k)}  prints indefinitely Try it online! Try it with an overloaded print function that allows you to pick a separator and the number of elements printed # 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"... ? Mar 8, 2018 at 5:56 • @EsolangingFruit It seems to be a variant of one of the name variants of BF Mar 8, 2018 at 18:18 # Ruby, 4443 37 bytes 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). Mar 20, 2018 at 5:27 • Good catch! Answer updated. Mar 20, 2018 at 10:01 • A simple byte save would be ~4+ --> 3^, but you can actually do several bytes better by making use of run-length decoding: l~H3b{ee{(2%)+}%e~}2$*< (I also changed = to < because it's the same byte count but makes it easier to verify the correctness of the solution.) Mar 20, 2018 at 20:18
• I'm quite new to code golfing and I hadn't looked into these compression mechanisms like base conversion and runlength encoding yet. Gotta read up I guess :) Mar 21, 2018 at 14:27
• I managed to golf the anwer without ee down to 24 bytes: l~_H3b\{_X2%)a\X)=*+}fX< Mar 27, 2018 at 16:05

# Perl 6, 53 41 bytes

-12 bytes thanks to nwellnhof!

{1,2,2,{$/=$++%2+1;|($/xx@_[2+$++])}...*}


Try it online!

Anonymous code block that returns a lazy infinite sequence of values.

### Explanation:

{                                       }  # Anonymous code block
1,2,2,     #Hard-code the self-referential elements
{                           }...*   # Get the next element based on the previous elements
$/=$++%2+1;    # Swap the variable keeping track of 1 or 2
$/xx # Repeat that variable @_[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.) Oct 5, 2018 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, 2018 at 9:54
• -1 byte, avoiding $/: Try it online! Dec 17, 2022 at 23:23 # APL (Dyalog Extended), 13 bytes {⍺↑2-2|⍸⍵}⍣≡⍨  Try it online! Basically a port of 13-byte J code at the bottom of algorithmshark's J answer ($1+2|I.)^:_~.

Takes an integer n and gives first n terms.

### How it works

{⍺↑2-2|⍸⍵}⍣≡⍨  ⍝ Input: n
{        }     ⍝ At each step,
⍸⍵      ⍝   For each item a_i at index i, give a_i copies of i
2-2|        ⍝   Modulo 2 then subtract from 2;
⍝   convert 1 2 3 4 5 .. to 1 2 1 2 1 ..
⍺↑            ⍝   Take first n items
⍣≡   ⍝ Repeat until the result does not change
⍨  ⍝   using n as both the fixed ⍺ and the starting ⍵


# Factor, 75 bytes

[ { 1 2 } over [ [ 2 mod 1 + <array> ] map-index concat ] times swap head ]


Try it online!

Somewhat ended up like the J solution, just more bloaty.

Since Factor is stack-based, it is shorter to hardcode the starting array than to copy the input and create an array out of it.

[                      ! anonymous lambda, taking input n from stack
{ 1 2 } over         ! ( n arr n )
[ ... ] times        ! run lambda n times to the array { 1 2 } ...
[ ... ] map-index  !   given an array, map each with index...
2 mod 1 +        !     ( item idx%2+1 )
<array>          !     an array of length item, filled with idx%2+1
concat             !   concat the elements of nested arrays
swap head            ! take first n items from the result
]


# Jelly, 21 bytes

3_ṪẋŒgL‘ịƲ⁸;
2RxÇ⁸¡ḣ


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.

# Momema, 64 bytes

02 1 3-8 1j0+1*0+1-**00+1*0-8+1**1 1+1*1j+-1*+-1*1+1*0**00+1*0j1


## Explanation

The idea is to gradually fill up the tape with the decremented values of the sequence. We use index 0 for the write head and index 1 for the read head.

0  2            #  w = 2
1  3            #  r = 3
-8 1            #  print(1)
j  0            #  do {
+1*0  +1-**0  #    tape[1 + w] = 1 - tape[w]
0     +1*0    #    w = 1 + w
-8    +1**1   #    print(1 + tape[r])
1     +1*1    #    r = 1 + r
j  +-1*+-1*1    #    if (tape[r - 1] - 1) continue
+1*0  **0     #    tape[1 + w] = tape[w]
0     +1*0    #    w = 1 + w
j  1            # } while (1)


Try it online!

# dirt -v, 48 bytes

"122,11"|.*,(1',.*(1'2|2'1)|2',.*(1"22"|2"11"))


Continuously outputs longer and longer Kolakoski sequences, with a , in the middle that moves right as the sequence is generated:

122,11
1221,12
12211,21
122112,122
1221121,221
12211212,2122
122112122,12211
1221121221,22112
12211212212,211211
122112122122,1121122
1221121221221,1211221
12211212212211,2112212
122112122122112,11221211
1221121221221121,12212112
12211212212211211,22121121
122112122122112112,212112122
1221121221221121122,1211212211
12211212212211211221,2112122112


Run as dirt kolakoski.dirt -v -i "", or by feeding it an empty file dirt kolakoski.dirt -v < empty.txt

# Unlambda, 419 bytes

c.1.2ssksskdskksiikssssikkkssssikkiksk.1sskssksiskkssksskkskskkkkiksk.1sskssksiskksksskskkkksikkkssssikkiksk.2sskssksiskkskssksskkskskssksskkskskkkkiksk.2sskssksiskkskskssksksksskskkkksikkskssikkkiskksikkissikkikk


Try it online!

No way this could be a contender for the shortest solution, but oh well. Prints indefinitely.