Kolakoski sequence

The Kolakoski sequence is a sequence of 1's and 2's such that if you take the lengths of each run of the sequence, the result is the same as the original sequence. There are actually two sequences that fit this definition with their only difference being a 1 at the beginning. Its first 16 terms are:
 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, ...
There are a few different ways to generate the sequence, such as iteratively making bigger copies of the sequence from smaller ones or using a growing queue.
== Examples ==
=== 1+ ===
 (1|1\":##[#1](2|11+\":##[#11+](1)))
=== ><> ===
 > >1}:n1-?!v1}v
 ^}2^!?-1n:}2< <
=== Binary lambda calculus ===
A 0 bit corresponds to 1, and a 1 bit corresponds to 2.
 0 000 010 1 1 000 0 011 001 0
 11 0 0 00 01 0 01 0 1 01
 0 001 101 0 0 000 0 001 000 0
 0 1 0 1 1 0 1 1 0 0
 101 011 111 101 111 100 001 011 111 100
 
 1 0 1 1 1 1 0 0 0 0 1 0 1 1
 01111 101100001 011011111 00001 01101 111110111 00000 1 0
 
 0 101 111 0 0 000 1
 00 0 0 01 10 0 10
 1 110 001 0 0 000 1
 1 0 0 0 0 0 0
 101 100 000 101 100 000 110
Below is a breakdown of the expression.
 ONE = λfirst. λsecond. first
 TWO = λfirst. λsecond. second
 
 INVERT item = item TWO ONE
 CONS head tail = λf. f head tail
 
 GENERATE = λqueue. λnext. (
 λhead. CONS head (
 GENERATE (
 λenqueue. queue (
 head (CONS next enqueue) (CONS next (CONS next enqueue))
 ) TWO
 ) (INVERT next)
 )
 ) (queue (λx. x) ONE)
 MAIN = λ_. CONS ONE (CONS TWO (GENERATE (λenqueue. CONS TWO enqueue) ONE))
=== Bitdeque ===
In the deque, 1 is represented by a 1 bit, and 2 is represented by a 0 bit.
 INVERT PUSH EJECT GOTO 6 INVERT PUSH INVERT PUSH EJECT GOTO 1 PUSH INVERT GOTO 1
=== Bitwise Cyclic Tag ===
In the data string, 1 is represented as 10 and 2 as 11. The initial data string is a single 2 (11), skipping the first 1, 2 of the sequence.
 11100111001111011110
=== brainfuck ===
Uses two-pointers to work. It initializes the first 5 terms and adds the number that's different from the fast pointer value for slow pointer value times.
+++++++[>+++++++<-]>.+..-..[-] ; Print out "12211"
+>>>>++>>>>++>>>>+>+>>>+>>+<<<<<<<<<<<<<<<<<<< ; Store 1 2 2 1 1
 ; s^ f^
+[ ; Infinite loop
 >>-[+>>>>-]+ ; Go to the slow pointer
 <[
 >>-[+>>>>-]+ ; Go to the fast pointer
 >>[>>>>]+++ ; Set top value to 3
 <<-[+<<<<-]+ ; Go back to the fast pointer
 <<[>>>+>[>>>>]<<<<-<<-[+<<<<-]+<<-] ; Set top value to 3 minus fast pointer value
 >>>[<<<+>>>-] ; Restore fast pointer value
 <<<[>>>>]<<<++++++[<++++++++>-]<. ; Output top value as character
 >++++++[<-------->-] ; Restore to number
 -[+<<<<-]+<- ; Decrement slow pointer value
 ]
 >>>[<<<+>>>-] ; Restore slow pointer value
 <-[+>>>>-]+ ; Go to the fast pointer
 [>>[>>>>]<<+<<<<-[+<<<<-]] ; Move fast pointer to top
 <-[+<<<<-]+[>>>>+<<<<-] ; Move slow pointer to the next
 >>-[+<<<<-]+ ; Move back to infinite loop flag
]
Another by User:Jan jelo:
cells:tmp|flag|tmp|tmp|tmp|term|preflag|lastflag|tmp|tmp|term|preflag|lastflag|tmp|tmp…
>+>>>>
+>+>+>>>
++>+>+>>>
++
[
 >
 [<<<<<]
 <<<<<<<<
 ++++++[->++++++++<]
 <<<[->>>>+<<<<]
 >>>>.
 <++++++[->--------<]
 >[-<<<<+>>>>]
 >>>>>>
 [->>>+>+<<<<]
 >>>>[-<<<<+>>>>]
 <[-<<<[<<<<<]>>+>>>>[>>>>>]>>]
 <<<[<<<<<]
 >>[
 -
 <[->>+>+<<<]
 >>[-<<+>>]
 >[->>>[>>>>>]>>>+[<<<<<]>>>>]
 >>>[>>>>>]+>>>>+<[<<<<<]
 >>
 ]
 +++<[->-<]
 >[-<+>]
 >>>>[>>>>>]+>>>>>-
 >>>>
]
And another 176-bytes one by User:Blashyrkh, with o(log n) memory consumption. Generation of first 26 million terms of the sequence uses only 132 memory cells and 6.12 billion operations. Here's the stripped version. Version with comments is available at User:Blashyrkh/Kolakoski-brainfuck.
>+++++++[->+++++++<]>.->++>++>>++>++[<<<]>[>[-<+<+>>]<.<[->->+<<]>>>-[>]+>>>[<<+++<-<[->>-<<]>>[-<<+>>]>>-[>]+>>>]>++>[<--<]++>[<-->>>]<<<<<<-<<<<<[>>>[-<+<+>>]<[->+<]<<<<<]>>]
=== FALSE ===
This stores the queue as a pair of integers, one containing the actual data in bits, and the other being used as the "enqueue pointer".
 [@$2*\@*@+]n: {enqueue}
 [\2/\$2/\1&]d: {dequeue}
 1 0 {initialize queue}
 [0~][0n;!d;!$1+._[0n;!]?1n;!d;!$1+._[1n;!]?]#
This program instead stores the queue elements in the stack and uses ø to dequeue.
 {queue is stored as <discarded elements>, <queue elements>, <queue length>}
 [\1+]n: {enqueue}
 [1-$1+ø]d: {dequeue}
 0 {initialize queue}
 [0 0=][1n;!d;!$.2=[1n;!]?2n;!d;!$.2=[2n;!]?]#
This interpreter has a handful more commands, but the roll n command "®" is quite helpful here.
 1q:{current}
 0h:{height}
 [0 0=][
 q;{push}
 h;1+®{pop bottom}
 $.", "{output}
 2={popped == 2?}
 [
 q;{push another}
 h;1+h:{increment h}
 ]?
 3q;-q:{3 - q -> q}
 ]#{do forever!}
=== Kawa ===
Raw text version at Kawa/Raw programs#Kolakoski sequence
=== Lazy K ===
`k```s`s````ssi`s`k`s``s`ks``s``s`ks``s`k`s`k``s``s`ks``s`k`si``s`s`kk`k`sk``s`si`kk````ssi`s`k`s``s`ks``s``s``s`s`k`s`s`ks`k`k`k`k`sk`kk`k``s`k`s``ss`k`k`skk``s`k`s``s`ks``s`s`k``s```sik```ss`ss`kk``s`ks``s`k`sik`kk``s``s`ks``s`s`kki`k``si`k`sk`k``s`k`s`k``s```sss`ks`kk``s``s`ks``s`k`s`k``s`ks`s`k``s`ks``s`k`sik``s``s`ks``s`k`s`k``s`ks``s`k`sik``s`k`s````ssi`s`k`s``s`ks``s``s``s`s`k`s`s`ks`k`k`k`k`sk`kk`k``s`k`s``ss`k`k`skk``s`k`s``s`ks``s`s`k``s```sik```ss`ss`kk``s`ks``s`k`sik`kk``s``s`ks``s`s`kki`k``si`k`skk`kk```ss``ss``ss`s``si`k`sk`kk``s`kk``s`kk``s`s`k`s`k`s`k``s`k``s`k`s``s`k``s`ks``s`k`sik``s``si`k```si``si``s`s``s`k``s`ksk``s``sski```sski`s``s`ksk`k```si``s`s``s`k``s`ksk``s``sski```sski`s``s`kskkkiki
This is the result of "compilation" of the following lambda calculus code (preamble with definition of car/cdr/nil/etc... is omitted):
pushpop = lambda q p . (lambda q f . f (cdr q) (car q)) (append q p)
onestep = lambda q p . pushpop q p (lambda q x f . f (x (append q p) q) (not p) x)
kolakoski = (lambda f input . f f nil false) lambda self q p . onestep q p (lambda q p x . cons (x 50 49) (self self q p))
One can see that it's just the python example (see below) rewritten in functional paradigm.
===MoreMathRPN===
 "p
 1
 "do
 "q.append(p)
 >> 0
 "x = q.pop(0)
 #
 -> ]0
 del 1
 "yield x
 >> 0
 outputV
 outputS ", "
 "if x == 2
 -3
 *
 7
 +
 jmp ]0
 del 0
 "q.append(p)
 >> 0
 jmp 2
 del 0
 "p = 3 - p
 3
 -> 1
 -
 "while true
 jmp -19
===Muriel===
S:"@\"S:\\\"\"+|S+\"\\\";\\nK:\\\"\"+K+$f+(%$f,0,(2=#(%K,i+2,i+3)))+\"\\\";\\nf:\"+$(3-f)+\";i:\"+$(i+1)+\";\\n.%K,i,i+1;\\n\"+S";
K:"122";
f:1;i:0;
.%K,i,i+1;
@"S:\""+|S+"\";\nK:\""+K+$f+(%$f,0,(2=#(%K,i+2,i+3)))+"\";\nf:"+$(3-f)+";i:"+$(i+1)+";\n.%K,i,i+1;\n"+S
===Post correspondence problem===
These two are listed in the OEIS entry (they're mentioned as fixed points of substitutions, which are equivalent):
 11 12
 12 122
 21 112
 22 1122
This one skips the first 1:
 11 21
 12 211
 21 221
 22 2211
=== Python 3 ===
 def kolakoski():
 q, p = [], 1
 while True:
 q.append(p)
 yield (x := q.pop(0))
 if x == 2:
 q.append(p)
 p = 3 - p
Another one:
 k=[1,2,2]
 i=2
 while True:
 print(k[i-2])
 k+=[3-k[-1]]*k[i]
 i+=1
===Tag system===
Here, 1 is encoded as abc and 2 is encoded as ababc. The initial word is a single 2, skipping the first 1, 2 of the sequence.
Tag system 
 m: 2
 A: {a,b,c} 
 P:
 a --> abc
 b --> ababc
 c --> 
Computation
 Initial word: ababc
 abcabc
 cabcabc
 bcabc
 abcababc
 cababcabc
 ...
===Thue===
[1>]1::=1[1>]
[1>]2::=2[1>]
[1>]*1::=[<1]1*[a1>]
[1>]*2::=[<1]2*[a1>][a1>]
(1)::=~1
(2)::=~2
1[<1]::=[<1]1
2[<1]::=[<1]2
>[<1]1::=1>[2>](1)
>[<1]2::=2>[2>](2)
[a1>]1::=1[a1>]
[a1>]2::=2[a1>]
[a1>]|::=1|
[2>]1::=1[2>]
[2>]2::=2[2>]
[2>]*1::=[<2]1*[a2>]
[2>]*2::=[<2]2*[a2>][a2>]
1[<2]::=[<2]1
2[<2]::=[<2]2
>[<2]1::=1>[1>](1)
>[<2]2::=2>[1>](2)
[a2>]1::=1[a2>]
[a2>]2::=2[a2>]
[a2>]|::=2|
::=
|>[1>]12*2|
===Uiua===
 ⍢(↘1⊂:↙:⊂.⊂[]-:3⊣,⊡2.&pf⊢.|1)[1 2 2]
== External resources ==
* https://oeis.org/A000002
Category:Program forms