The infinite Fibonacci word is a specific, infinite sequence of binary digits, which are calculated by repeated concatenation of finite binary words.

Let us define that a Fibonacci-type word sequence (or FTW sequence) is any sequence ⟨Wn that is formed as follows.

  • Commence with two arbitrary arrays of binary digits. Let us call these arrays W-1 and W0.

  • For each n > 0, let Wn ≔ Wn-1 ∥ Wn-2, where denotes concatenation.

A consequence of the recursive definition is that Wn is always a prefix of Wn+1 and, therefore, of all Wk such that k > n. In a sense, this means the sequence ⟨Wn converges to an infinite word.

Formally, let W be the only infinite array such that Wn is a prefix of W for all n ≥ 0.

We'll call any infinite word formed by the above process an infinite FTW.


Write a program or function that accepts two binary words W-1 and W0 as input and prints W, abiding by the following, additional, rules:

  • You may accept the words in any order; as two arrays, an array of arrays, two strings, an array of strings, or a single string with a delimiter of your choice.

  • You may print the digits of the infinite word either without a delimiter or with a consistent delimiter between each pair of adjacent digits.

  • For all purposes, assume that your code will never run out of memory, and that its data types do not overflow.

    In particular, this means that any output to STDOUT or STDERR that is the result of a crash will be ignored.

  • If I run your code on my machine (Intel i7-3770, 16 GiB RAM, Fedora 21) for one minute and pipe its output to wc -c, it must print at least one million digits of W for (W-1, W0) = (1, 0).

  • Standard rules apply.


Let W-1 = 1 and W0 = 0.

Then W1 = 01, W2 = 010, W3 = 01001, W4 = 01001010 … and W = 010010100100101001010….

This is the infinite Fibonacci word.

Test cases

All test cases contain the first 1,000 digits of the infinite FTW.

Input:  1 0
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001

Input:  0 01
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001

Input:  11 000
Output: 0001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011

Input:  10 010
Output: 0101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010

Input:  101 110
Output: 1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101
  • 10
    \$\begingroup\$ Fibonacci-type words FTW! \$\endgroup\$
    – Seadrus
    Commented Nov 7, 2015 at 3:47

20 Answers 20


Haskell, 15 bytes


The infix function % produces an infinite string, which Haskell prints forever because Haskell is cool like that.

>> "1"%"0"

The recursive idea is similar to Zgarb's solution. Writing f for the function %, and + for string concatenation, it implements:

f(v,w) = w + f(w,v+w)

The infinite output string starts with w, and the remainder of it is the result for the Fibonacci-shifted strings w and v+w.

This has no problem generating a million characters in a minute.


Pyth, 8 bytes


Input in the form "W-1", "W0".

Proof of completion:

$ time pyth -cd 'u,peGsGQ' <<< '"1", "0"' 2>/dev/null | head -c1000000 > /dev/null

real    0m0.177s
user    0m0.140s
sys 0m0.038s

Proof of correctness:

Here is the series as internally generated. It is printed in concatenation by the program.

[0, 10, 010, 10010, 01010010, 1001001010010,...]

Compare to the following, printed in concatenation, which is simply the string added to the previous string on each step:

[0, 1, 0, 01, 010, 01001, 01001010, 0100101001001, ...]

We want to prove these are equivalent.

Clearly, they are the same through the first few steps. Let's compare them after a bit:





We see that the pairs of strings are alternately of the forms:

01a 10b
a10 b01

Where a and b are arbitrary sequences on 0s and 1s. Let's continue the sequence for a bit, to prove is continues forever by induction:

01a   10b   10b01a   10b01a10b
  a10   b01   a10b01   b01a10b01

2 steps later, it is of the correct form.

10b   01a   01a10b   01a10b01a
  b01   a10   b01a10   a10b01a10

2 steps later, it is of the correct form.

So by induction, the strings always match once concatenated.

  • 14
    \$\begingroup\$ +1 for writing working code that you don't understand. \$\endgroup\$
    – Celeo
    Commented Nov 6, 2015 at 16:20
  • 2
    \$\begingroup\$ I believe your 8 byte solution works because it prints starting at W0 but instead of printing W1 it prints W-1 || W0, which is the "wrong" concatenation order. I think this works out to be equivalent, but I haven't come up with a proof... \$\endgroup\$ Commented Nov 6, 2015 at 16:25

Haskell, 31 bytes

w#v=v++drop(length v)(v#(v++w))

This defines an infix function # that takes two strings and returns an infinite string. Usage:

> let w#v=v++drop(length v)(v#(v++w)) in "11"#"000"

If I query the millionth element of the sequence defined by "1" and "0", even the online interpreter prints the result in less than a second:

> let w#v=v++drop(length v)(v#(v++w)) in ("1"#"0") !! 1000000


w#v=                             -- The result of w#v is
    v++                          -- v concatenated to
                      v#(v++w)   -- the infinite word v#(v++w),
       drop(length v)            -- with the first v characters dropped.

Basically, we know that w#v == v#(v++w) and w#v begins with v, and use these facts to define the result. Since Haskell is lazy, this "magically" just works.


CJam, 12 11 bytes


This takes the two words on separate lines, in the opposite order, e.g.





The idea is to build up the word naively (by remembering the current word and appending the previous one to it) and while we're doing that, we print whatever we just appended (in order not to repeat the prefix that was already printed). To avoid having to handle the starting point separately, we start from an empty word, such that W0 is the first thing we append (and print).

ll    e# Read the two lines separately.
L     e# Push an empty string.
{     e# Infinite loop...
  @   e#   Pull up the previous FTW.
  _o  e#   Print it.
  +_  e#   Append it to the current FTW and duplicate it.

Pip, 8 bytes

Hey, tied with Pyth!


Straightforward recursive definition borrowed from xnor's Haskell answer. With spaces added for clarity:

(f Ob a.b)

Every program in Pip is an implicit function that takes the command-line args as its arguments (assigned to variables a through e) and prints its return value. O is an operator that outputs and then returns its operand, so the first thing that happens here is the second argument is displayed (sans trailing newline).

Now, the Lisp-inspired syntax (f x y) in Pip is a function call, equivalent to f(x,y) in C-like languages. The f variable refers to the current function--in this case, the top-level program. Thus, the program recursively calls itself with b and a.b as the new arguments.

I was pleasantly surprised to find that this approach is plenty fast:

dlosc@dlosc:~$ time pip -e '(fOba.b)' 1 0 2>/dev/null | head -c1000000 > /dev/null

real    0m0.217s
user    0m0.189s
sys     0m0.028s

It takes about 30 seconds on my Ubuntu machine for the program to hit the max recursion depth, at which point it has printed out somewhere over a billion digits.

This iterative solution is slightly faster and hogs less memory, at the cost of one byte:


APL, 24 18


Using xnor's formulation allowed to shave off few characters.

                 ⍞  ⍝ Read W₋₁ as a character string.
                ⍞   ⍝ Read W₀.
{            }⍣≡    ⍝ Apply the following function repeatedly until fixpoint:
                    ⍝ It takes a pair of strings (A B),
         ⍞←↑⍵       ⍝ prints A
 (,/⌽⍵),⊂  ↑⍵       ⍝ and returns (BA A).

On an infinite machine in infinite time it would actually print W thrice—first incrementally while running the loop, and then twice as a result of the whole expression when the ⍣≡ fixpoint operator finally returns.

It's not very fast but fast enough. In GNU APL:

$ printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 100
$ time printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 1000000 >/dev/null
    0m3.37s real     0m2.29s user     0m1.98s system
  • \$\begingroup\$ Two infinite numbers. O.O +1 \$\endgroup\$ Commented Nov 7, 2015 at 19:34
  • \$\begingroup\$ I didn't know about ⍣≡; it sounds very useful. \$\endgroup\$
    – lirtosiast
    Commented Nov 8, 2015 at 2:05

PowerShell, 97 76 Bytes

param($a,$b)write-host -n $b;while(1){write-host -n $a;$e=$b+$a;$a=$b;$b=$e}

Edit - Umm, writing out $e.substring($b.length) after we just concatenated $a and $b together is equivalent to writing out just $a ... derp.

Wow, verbose. PowerShell will, by default, spit out a newline every time you output something. Really the only way to get around that is with write-host -n (short for -NoNewLine), and that absolutely kills the length here.

Essentially, this iterates through the sequence, building $e as the "current" Wn as we go. However, since we're wanting to build the infinite word instead of the sequence, we leverage our previous variables to print out the suffix $a that was populated in our previous loop. Then we setup our variables for the next go-round and repeat the loop. Do note that this expects the input to be explicitly delimited as strings, else the + operator gets used for arithmetic instead of concatenation.


PS C:\Tools\Scripts\golfing> .\infinite-ftw.ps1 "111" "000"
0001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000 ...

Pure bash, 58

printf $b
printf $a

I run out of memory before 1 minute, but have plenty of digits by then - after 10 seconds I have 100 million digits:

$ ./ftw.sh 1 0 | head -c100
$ { ./ftw.sh 1 0 & sleep 10 ; kill $! ; } | wc -c

Mathematica, 56 bytes


Dyalog APL, 9


This one uses to define a recursive function. It's a direct translation of this xnor's Python 3 answer. It takes W0 as right, and W−1 as its left argument, both should be character vectors.


C, 76 (gcc)

main(c,v)char**v;{int p(n){n>2?p(n-1),p(n-2):puts(v[n]);}for(p(4);;p(c++));}

This is a fairly straightforward recursive printer, implemented as a nested function (a GNU C extension not supported by clang) to avoid having to pass v around. p(n) prints Wn-2, where W-1 and W0 must be provided in v[1] and v[2]. This initially calls p(4) to print W2. It then loops: it calls p(3) to print W1, making the complete output W2W1, which is W3. It then calls p(4) to print W2, making the complete output W4, etc. Performance is slightly better than my earlier answer: I'm seeing 1875034112 values in a minute.

C, 81 (clang)

This is a completely different approach from the above that I feel is worth keeping up, even though it scores worse.


This has all kinds of undefined behaviour, mainly for fun. It works with clang 3.6.2 on Linux and with clang 3.5.2 on Cygwin for the test cases in the question, with or without special command-line options. It doesn't break when optimisations are enabled.

It doesn't work with other compilers.

You may accept the words in any order; as two arrays, an array of arrays, two strings, an array of strings, or a single string with a delimiter of your choice.

I accept the words as command-line arguments in string format.

You may print the digits of the infinite word either without a delimiter or with a consistent delimiter between each pair of adjacent digits.

I use newline as the consistent delimiter.

For all purposes, assume that your code will never run out of memory, and that its data types do not overflow.

In particular, this means that any output to STDOUT or STDERR that is the result of a crash will be ignored.

I access s out of bounds. This must surely end with a segfault or an access violation at some point. s happens to get placed at the end of the data segment, so it shouldn't clobber other variables and give wrong output before that segfault. Hopefully.

If I run your code on my machine (Intel i7-3770, 16 GiB RAM, Fedora 21) for one minute and pipe its output to wc -c, it must print at least one million digits of W for (W-1, W0) = (1, 0).

Testing using { ./program 1 0 | tr -d '\n' & sleep 60; kill $!; } | wc -c, I get 1816784896 digits in one minute on my machine when the program was compiled with -O3, and 1596678144 when it was compiled with optimisations diabled.

Ungolfed, no UB, with explanation:

#include <stdio.h>

// Instead of starting with -1 and 0, start with 0 and 1. I will use lowercase w for that,
// so that wx = W(x-1).

// Declare a variable length array of numbers indicating what has been printed.
// The length is indicated through a pointer just past the end of the values.
// The first element of the array is a special marker.
// [0 3 1] means that w3 w1 has been printed.
// The array is initialised to [0] meaning nothing has been printed yet.
int stack[99999];
int *ptr = stack + 1;

int main(int argc, char *argv[]) {
  ++argv; // Let argv[0] and argv[1] refer to w0 and w1.
  for(;;) {
    // Determine the word to print next, either 0 or 1.
    // If we just printed 1 that wasn't the end of a different word, we need to print 0 now.
    // Otherwise, we need to print 1.
    int word = ptr[-1] != 1;

    // Print the word, and mark the word as printed.
    *ptr++ = word;

    // If we just printed w(x) w(x-1) for any x, we've printed w(x+1).
    while (ptr[-1] + 1 == ptr[-2]) {
  • \$\begingroup\$ Your evil s[] trick works well with clang (just installed it). I'm quite surprised this actually works. For all purposes, assume that your code will never run out of memory, and that its data types do not overflow. Unfortunately, that means simply printing W97 is not considered valid. Could you call p recursively? That would eliminate the need for a main. \$\endgroup\$
    – Dennis
    Commented Nov 7, 2015 at 16:43
  • \$\begingroup\$ @Dennis To be fair, at the current rate, the version that cheats by printing W97 would do the right thing in printing W∞ for >3000 years. I'll see if I can improve on that. :) \$\endgroup\$
    – hvd
    Commented Nov 7, 2015 at 20:52
  • \$\begingroup\$ @Dennis I managed to get it working with the same number of bytes for the program, but making it specific to GCC, and no longer having a clean function. I don't see how to put the logic of repeatedly calling p into p itself without adding more code, but if I do find a way I'll edit again. \$\endgroup\$
    – hvd
    Commented Nov 7, 2015 at 21:18

Javascript (53 bytes)


Input should be string and not number ('0' and not just 0).

  • 2
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! Our rules for code golf challenges state that, by default, submissions must be full programs or functions. As such, they have to accept some sort of user input; hardcoding the input is not allowed. Furthermore, your code prints the sequence Wn, not its limit. \$\endgroup\$
    – Dennis
    Commented Nov 6, 2015 at 18:40

Perl 5, 45 55 49 bytes

44 bytes, plus 1 for -E instead of -e


Use as e.g.

perl -E'sub{$i=1;{say$_[++$i]=$_[$i].$_[$i-1];redo}}->(1,0)'

This prints successive approximations to W and thus, if you wait long enough, prints, on its last line of output, W to any desired length, as required. The digits of the word are concatenated without a delimiter.

Since I'm on Windows, I tested it for the "at least one million digits of W" requirement by running it with output redirected to a file and killing it after about 59 seconds, then running GnuWin32's wc -L, which printed 701408733.


The OP clarified in a comment on this answer (and probably I should have realized anyway) that the extra output preceding W disqualifies the above. So instead here's a 55-byte solution that prints only W:


Used the same way, but with the arguments in reverse order, and doesn't require -E:

perl -e'sub{print$_[0];{print$_[1];unshift@_,$_[0].$_[1];redo}}->(0,1)'

Doubtless it can be golfed further, but I don't see how to do so right now.

Further update:

Dennis shaved five bytes by using -a (thus reading <> to remove sub) and reassigning the parameter passed to print at the end of the redo block:

With -ane and reading from <> (both inputs on one line, space-separated, in reverse order); 48 + 2 bytes:


And, based on that, I shaved one more byte (same as above, but now the inputs are in the correct order); 47+2 bytes:


REXX, 48

arg a b
do forever
say b
say a

exec ftw.rex 0 1

Currently can't test performance because I used an online compiler to write it. The "forever" can be replaced with any number where as the printed ftw numbers are (number + 2).

I also wrote a small (messy) solution in Prolog. Didn't figure how to test performance with this one but its probably atrocious anyway.


:- C='0';C='1';(f(1,0,C)).

Python 2, 67 bytes

while 1:a,b=b,b+a;print'\n'.join(a)

Accepts input as a comma-separated pair of strings: "1","0", for the example in the question.

No online interpreter because infinite loops are bad. Buffered output made me gain a lot of bytes. :( Thanks Dennis for pointing out that 1 digit per line is valid.

Timing on my (significantly-weaker) machine:

$ time python golf.py <<< '"1","0"' 2>/dev/null | head -c2000000 > /dev/null

real    0m1.348s
user    0m0.031s
sys     0m0.108s
  • 1
    \$\begingroup\$ The question allows a consistent delimiter between digits. You can save at least 28 bytes by printing each digit on a separate line. \$\endgroup\$
    – Dennis
    Commented Nov 6, 2015 at 18:16

Minkolang 0.11, 62 bytes

(od" "=,6&xI0G2@dO$I)I1-0G($d2[I2:g]Xx0c2*1c-0g0g-d[icO]0G0G1)

Try it here. Expects input in the order W0, W-1 with a space in between.


(                             Open while loop (for input-reading)
 od                           Read in character from input and duplicate
   " "=,                      0 if equal to " ", 1 otherwise
        6&                    Jump 6 characters if this is non-zero
          xI0G2@              Dump, push length of stack, move to front, and jump next two
                dO            Duplicate and output as character if 1
                  $I)         Close while loop when input is empty
                     I1-0G    Push length of stack - 1 and move it to the front

Meta-explanation for the following is that at this point in time, we have two numbers followed by a string of "0"s and "1"s with no separation. If the lengths of W0 and W-1 are a and b, respectively, then the two numbers at the front of the stack are <a+b> and <a>, in that order. The word formed by concatenating Wi+1 and Wi, i.e. Wi+1 + Wi, is equal to 2 * Wi+1 - Wi. So the following code duplicates the stack (2 * Wi+1), pops off the top <a> elements (- Wi), and then replaces <a+b> and <a> with their successors, <a+2b> and <b>.

(                                       Open while loop (for calculation and output)
 $d                                     Duplicate the whole stack
   2[I2:g]                              Pull <a+b> and <a> from the middle of the stack
          Xx                            Dump the top <a> elements (and <a+b>)
            0c2*1c-                     Get <a+b> and <a>, then calculate
                                        2*<a+b> - <a> = <a+2b> = <a+b> + <b>
                   0g0g-                Get <a+b> and <a>, then subtract
                        d[icO]          Output as character the first <b> elements
                              0G0G      Move both to front
                                  1)    Infinite loop (basically, "while 1:")
  • \$\begingroup\$ (Note: this doesn't produce 1 million digits in a minute...only 0.5 million. Given that this is naturally a relatively slow language, I think I can be cut a little slack. :P) \$\endgroup\$ Commented Nov 10, 2015 at 7:23

Python 3, 32

def f(a,b):print(end=b);f(b,a+b)

The same recursive idea as my Haskell answer, except the prefix is printed because Python can't handle infinite strings.

Used a trick from Sp3000 to print without spaces by putting the string as the end argument in Python 3


Perl, 32 bytes

#!perl -pa

Counting the shebang as two, input is taken from stdin, space separated as W0, W-1. Output for 1MB times at ~15ms, most of which can be attributed to interpreter launch.

Sample Usage

$ echo 0 1 | perl inf-ftw.pl

$ echo 110 101 | perl inf-ftw.pl

Prolog, 69 bytes


Example input: p('1','0')

Haven't found a way to remove the extra write.
Should be able to improve on this if I figure out how to do that.


J, 22 bytes including 6 for input chars

similar to Dyalog APL solution


Try it online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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