150
\$\begingroup\$

The Fibonacci sequence is a sequence of numbers, where every number in the sequence is the sum of the two numbers preceding it. The first two numbers in the sequence are both 1. Here are the first few terms:

1 1 2 3 5 8 13 21 34 55 89 ...

Write the shortest code that either:

  • Generates the Fibonacci sequence without end.

  • Given n calculates the nth term of the sequence. (Either 1 or zero indexed)

You may use standard forms of input and output.

(I gave both options in case one is easier to do in your chosen language than the other.)


For the function that takes an n, a reasonably large return value (the largest Fibonacci number that fits your computer's normal word size, at a minimum) has to be supported.


Leaderboard

/* Configuration */

var QUESTION_ID = 85; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();
    
    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body {
  text-align: left !important;
  display: block !important;
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
5
  • 4
    \$\begingroup\$ I am sort of waiting for a response like "f", 1 byte, in my math based golf language. \$\endgroup\$ Aug 11, 2020 at 11:57
  • \$\begingroup\$ @ChrisJesterYoung can we use 1.0 are 1 only? \$\endgroup\$ May 11, 2022 at 2:45
  • \$\begingroup\$ @NumberBasher 1.0 is fine. \$\endgroup\$ May 20, 2022 at 19:10
  • \$\begingroup\$ What about 1.3? \$\endgroup\$ Aug 28, 2022 at 15:10
  • 2
    \$\begingroup\$ Am I allowed to start the sequence with 0, 1? \$\endgroup\$
    – hakr14
    Oct 11, 2022 at 3:41

334 Answers 334

1
8 9
10
11 12
1
\$\begingroup\$

ShapeScript, 16 14 bytes

_1@0@'@1?+'*!#

This reads an integer n (in unary) from STDIN and prints the nth Fibonacci number.

Try it online!

How it works

        Input: a string of n 1's 
_       Get the length of the input to push n.
1@      Swap it with 1 (F[-1]).
0@      Swap it with 0 (F[0]).
        STACK: F[-1]   F[0]   n
'       Push a string that, when evaluated for the i-th time,
        does the following:
  @       Swap F[i-2] on top of F[i-1].
  1?      Push a copy of F[i-1].
  +       Add the copy of F[i+1] to F[i].
'       STACK: F[i-1]   F[i]
*!      Repeat the string n times and evaluate it.
#       Discard F[n] from the stack.
\$\endgroup\$
1
\$\begingroup\$

HOPS, 10 bytes

seq(x+x^2)

Attempt This Online!


HOPS, 11 bytes

1/(1-x-x^2)

Attempt This Online!

The generating function of the Fibonacci sequence is \$1/(1-x-x^2)\$. In HOPS, seq(f) means 1/(1-f).

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

Go, 55 bytes

func f(n int)int{if n<2{return n}
return f(n-1)+f(n-2)}

Attempt This Online!

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

Nibbles, 4.5 bytes (9 nibbles)

.~~1+<2
.~~         # append until null (here this means forever)
   1        # starting with 1
    +       #   sum of
     <2     #   take 2 elements (or 1 if there's only 1)

enter image description here


Nibbles also supports a recursive approach to calculate the n-th element:
``; $ -$2 1 + @-$2 @-$~ (10 bytes = 20 nibbles)

``;                      # define a recursive function:
    $                    # initial input is arg1;
      -$2                # when input minus 2 is zero or negative:
          1              # return 1;
                         # otherwise:
            +            # add together
              @-$2       # recursive call with input minus 2
                   @-$~  # and recursive call with input minus 1

...although simply indexing into the infinite sequence is shorter: =$.~~1+<2 (5 bytes = 10 nibbles).

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

Excel, 52 50 bytes

=INDEX(ROUND((.5+SQRT(5)/2)^ROW(A:A)/SQRT(5),),A1)

Note: Excel will automatically add a leading zero to .5 after you input the formula.

If you put a value in A1, you get that term (1-indexed) from the sequence. If you leave it blank, you get the first 1,474 terms which is when it gets too large for Excel to handle. As you can see below, it also loses accuracy at some point because Excel only keeps the first 15 digits of a number.

Screenshot

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

Haskell + hgl, 11 bytes

yy$K1<.<scp

Uses a new version that doesn't work on ATO yet :(

Explanation

The basic idea is to use the fact that each element of the sequence is one more than the sum of all elements 2 or more steps before it.

For example, by the time we have

1,1,2,3,5,8

To get the next element we sum everything but the last element (8)

1+1+2+3+5 = 12

and add 1

1,1,2,3,5,8,13

If we set up the first two elements we can use this property to generate the entire sequence.


yy is the fixed point combinator, it can be very hard to understand if you aren't used to wacky recursive schemes, so we will just rewrite things without it:

f=K1<.<scp$f

<.< is a fancy compose which composes its first argument on both sides of the second, so once again we can rewrite this longer as:

f=K1<scp<K1$f

K1 is a shortcut for (1:) which adds 1 to the front of a list.

f=1:(scp$1:f)

scp gives the cumulative sums of a list. This is the part that establishes the property which builds the next element.

11 bytes

f=1:lS(+)1f

Attempt This Online!

Explanation

This pretty straight-fowardly ports the Haskell answer. Same score as the other one but less interesting.

Reflections

There are some nice things here, I feel the first answer works well and I'm happy with the functions it is using. But I can still see somethings that could probably be improved.

  • There should be builtins for dealing with Fibonacci numbers eventually. They are a common subject of code-golf challenges
  • lS mp is probably useful. scp and scs are very similar, however they are required to not alter the length of the structure involved, while lS mp always makes the structure one longer. This is essential for the second answer to work, so we can't use scs as a replacement.
\$\endgroup\$
1
\$\begingroup\$

Thunno Y, \$7 \log_{256}(96) \approx\$ 6 bytes

(actually 5.76 bytes but that doesn't show up on the leaderboard)

{xyAx+Y

Attempt This Online!

Returns the 0-indexed \$n\$th Fibonacci number.

Explanation:

{xyAx+Y   # Implicit input
{         # Loop that many times:
 xy  +    #  Add x and y together
  yAx     #  While storing y in x
      Y   #  And storing the result in y
          # After the loop, the Y flag pushes y
          # Which is output implicitly afterwards

Note that x defaults to 0 and y defaults to 1.

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

Thunno 2, 2 bytes

ÆF

Given n, outputs the nth Fibonacci number (1-indexed).

Built-in solution. In Thunno 2.1.5, a non-built-in alternative will be 4 bytes:

1µµ+

Starting from 1, generates an infinite sequence (µµ), where the next term is found by adding (+) the previous two terms together.

Screenshot

Screenshot

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Almost a polyglot with Jelly… \$\endgroup\$
    – xigoi
    May 3, 2023 at 17:07
  • 1
    \$\begingroup\$ So close... But I'm not surprised: Thunno 2 and Jelly both use the same starting character for "math digraphs" \$\endgroup\$
    – The Thonnu
    May 3, 2023 at 17:16
1
\$\begingroup\$

Desmos, 11 bytes

a->a+b,b->a

Add sliders, then click arrow repeatedly

\$\endgroup\$
1
  • \$\begingroup\$ \to can be shortened to ->. \$\endgroup\$
    – Aiden Chow
    May 10, 2023 at 16:50
1
\$\begingroup\$

Itr, 6 bytes

1#Måâ+

takes n as input, computes the n-th Fibonacci number (0-indexed)

online interpreter

Explanation

1      ; push 1
 #M    ; for every number in the 1-based range to the input
   å   ; ignore that number
    â  ; push the top value below the 2nd value
     + ; add the top two values
       ; implicit output

Itr , 10 bytes

Directly computes the n-th Fibonacci number using Matrix powers, sadly a bit longer than the other solution

1ä,1)#^M¡M

takes n as input, computes the n-th Fibonacci number (1-indexed)

online interpreter

Explanation

(1ä,1)        ; the matrix [[1,1],[1,0]] (the opening bracket at the start can be left out)
       ^      ; to the power of
      #       ; the input
        M¡M   ; get the lower left element
        M¡    ; push the rows of the matrix reversed
          M   ; push all elements of the reversed lower row
\$\endgroup\$
1
\$\begingroup\$

Python 3.8, 36 bytes

I did not come up with this solution, so I'm making it Community wiki. However, it's beautiful, and you should read the blog post about it, from which I got the program.

lambda n:(b:=2<<n)**n*b//(b*b-b-1)%b

Attempt This Online

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

TypeScript’s type system, 97 bytes

//@ts-ignore
type F<N,L=[],A=[1],B=A>=L extends{length:N}?A["length"]:F<N,[...L,1],B,[...A,...B]>

Try it at the TS playground

This is a generic type F taking a number type N and outputting the Nth Fibonacci number, 0-indexed.

This solution won’t work past the first 20 Fibonacci numbers because of the max int (technically, max tuple size) limit.

Explanation: We start with the input number N, and L=[],A=[1],B=A. L keeps track of which Fibonacci number we’re on, and A and B are unary numbers (tuple-types of 1s) that track \$ f(n) \$ and \$ f(n + 1) \$ respectively.

First, check if L extends{length:N} (the length of L is N). If it is (?), return A["length"] (A as a decimal number).

Otherwise (:), recurse (F<…>), keeping N the same, increasing L’s length by 1 ([...L,1]), setting A to B, and setting B to A + B ([...A,...B]).

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

Labyrinth, 13 bytes

1
:!\
{ :
=+}

Try it online!

Infinitely prints fibonacci numbers separated by newlines.

1    Set up the stack to [(implicit 0) 1]

     Loop with stack content [x y]:
:!\  :!\   print y and a newline
{ :  :}    [x y | y]
=+}  +     [x+y | y]
     =     [y | x+y]
     {     [y x+y]
\$\endgroup\$
0
\$\begingroup\$

C / Objective-c, 62

c;f(a,b){printf("%d ",a+b);if(c++<40)f(a+b,a);}main(){f(0,1);}

This will print the first 40 fibonacci numbers. I assume the compiler will set c=0. If it is trash, than it will not work;

This version is smaller, but it infite show all sequence number

C / Objective-c, 50 (infinite)

f(a,b){printf("%d ",a+b);f(a+b,a);}main(){f(0,1);}
\$\endgroup\$
1
  • \$\begingroup\$ Variables with static duration are zero-initialized if not explicitly initialized. This behavior is required by the standard. \$\endgroup\$ Jul 30, 2021 at 17:48
0
\$\begingroup\$

PHP, Finite - 46 chars

<?for($b=1;$i++<$n;)echo$b-$a=($b+=$a)-$a,"
";

where $n is the length of the sequence

PHP, Infinite - 39 chars

<?for($b=1;;)echo$b-$a=($b+=$a)-$a,"
";
\$\endgroup\$
0
\$\begingroup\$

MATLAB/Octave, n first numbers, 41 39 chars

a=0:1;for(i=3:n);a(i)=a(i-2)+a(i-1);end
\$\endgroup\$
0
\$\begingroup\$

Python 3 (53)

def f(n):
 l,p=0,1
 while n:n,l,p=n-1,p,l+p
 return l
\$\endgroup\$
1
0
\$\begingroup\$

Clojure, 46

(defn f[x y z](if(= 0 z)x(recur y(+ y x)(- z 1))))

Although, technically 50 since Clojure requires the recur for pseudo tail call:

(defn f[x y z](if(= 0 z)x(recur y(+ y x)(- z 1))))

Non compressed:

(defn fib [left right iteration]   
  (if (= 0  iteration)
    left
    (fib right (+ right left)  (- iteration 1))))
\$\endgroup\$
0
\$\begingroup\$

Haskell: 27 (21) characters

It almost feels like cheating to use Haskell for something like this. It just prints Fibonacci numbers ad infinitum.

f=1:scanl(+)1f
main=print f

And if using GHCi only 21 characters, including two newlines, are necessary:

Prelude>let f=1:scanl(+)1f
Prelude>f
[1,1,2,3,5,8,13,21...
\$\endgroup\$
1
0
\$\begingroup\$

JAVA - 108 characters:

int[]f={0,1};System.out.println(0);for(int i=0;i<9;i+=2)System.out.printf("%d\n%d\n",f[0]+=f[1],f[1]+=f[0]);
\$\endgroup\$
5
  • \$\begingroup\$ If a space is required in the code, it should be included in the character count. \$\endgroup\$
    – Iszi
    Nov 27, 2013 at 21:53
  • \$\begingroup\$ Alright, I will update it. \$\endgroup\$
    – user10766
    Nov 27, 2013 at 21:57
  • \$\begingroup\$ Already fixed it for you - looks like someone approved my edit suggestion. \$\endgroup\$
    – Iszi
    Nov 27, 2013 at 22:05
  • \$\begingroup\$ That was me - I went to fix it, and found you had already. \$\endgroup\$
    – user10766
    Nov 27, 2013 at 22:06
  • \$\begingroup\$ Ah. All good, then. Welcome to Code Golf! \$\endgroup\$
    – Iszi
    Nov 27, 2013 at 22:10
0
\$\begingroup\$

C 64 Characters

a;main(f,n){scanf("%d",&n);while(--n)f+=a=f-a;printf("%d",f-a);}

This will print the nth Fibonacci number.

A more readable format :

a;
main(f,n){
scanf("%d",&n);
while(--n)
   f+=a=f-a;
printf("%d",f-a);
}
\$\endgroup\$
0
\$\begingroup\$

F#, 63 chars:

let rec g x y n=if n=x then x else f (n-1) y (x+y)
let f=g 0 1
\$\endgroup\$
0
\$\begingroup\$

~-~! (No Comment) - 27

'=|*>~[<'&*-~>+<'&*-~~>]*|:

Didn't think it'd be this short.

\$\endgroup\$
0
\$\begingroup\$

Ruby - 49 characters

Nobody has done a Ruby solution for the second problem so I thought I'd give that a go:

p Hash.new{|h,k|k<2?k:(h[k-2]+h[k-1])}[gets.to_i]
\$\endgroup\$
0
\$\begingroup\$

Javascript, 53 bytes

a=[1,1];setInterval('a.push(a[b=a.length-1]+a[b-1])')

I decided to use a new approach to create an infinite stream. Works anywhere else but Firefox.

To get the array of integers, simply do a from the console.

\$\endgroup\$
0
\$\begingroup\$

CoffeeScript, 63 bytes

j=0;k=1;a=[];a=((i=j+k;k=j;j=i) for i in [0..prompt()]);alert a
\$\endgroup\$
0
\$\begingroup\$

C, 45 bytes

Simple, iterative approach. Exits when signed integer overflows.

a;main(b){for(;b>0;printf("%d ",a=b-a))b+=a;}

Try it here.

\$\endgroup\$
1
  • \$\begingroup\$ I seems to me you can remove b>0 condition. \$\endgroup\$
    – sergiol
    Jul 8, 2017 at 22:32
0
\$\begingroup\$

C, 33 bytes

Recursively calculates the nth fibbonacci number.

f(n){return n>1?f(n-1)+f(n-2):n;}
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 32 26 bytes

-6 bytes thanks to @MartinEnder!

±1=±2=1;±n_:=±(n-1)+±(n-2)

Recursive function, returns nth value in sequence.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can golf this with prefix notation: f@1=f@2=1;f@n_:=f[n-1]+f[n-2]. And even further by defining an operator instead: ±1=±2=1;±n_:=±(n-1)+±(n-2). \$\endgroup\$ Mar 24, 2017 at 9:57
  • \$\begingroup\$ Oh yeah, forgot about prefix notation here. Didn't know about the operator, thanks! \$\endgroup\$ Mar 24, 2017 at 11:06
0
\$\begingroup\$

JavaScript (ES6)

A couple of different ES6 implementations. The first two return the nth Fibonacci number and the third returns an array of the first n Fibonacci numbers. Non-competing, obviously.

30 bytes

f=

(n,x=1,y=0)=>!n?y:f(n-1,x+y,x)

console.log(f(10))

46 bytes

f=

n=>(x=1,y=0,eval("while(n--)[x,y]=[x+y,x]"),y)

console.log(f(10))

46 bytes

f=

n=>(a=[],(f=x=>a[x]=x<2?x:f(--x)+f(--x))(n),a)

console.log(f(10))

\$\endgroup\$
1
8 9
10
11 12

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.