146
\$\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\$
3
  • 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 at 2:45
  • \$\begingroup\$ @NumberBasher 1.0 is fine. \$\endgroup\$ May 20 at 19:10

308 Answers 308

1
7 8 9 10
11
0
\$\begingroup\$

tq, 6 bytes

Currently this has no separator...

01p+r)

Explanation

0,        # Initialize the number 0
  1,      # (Since a preceding 0 in decimal is disallowed)
    p+r,  # Initialize the third item in the list as the 
          # previous item + the previous-previous item
        ) # Extend this forever
\$\endgroup\$
0
\$\begingroup\$

Python 2, 59 51 55 33 bytes

a=0
b=1
while 1:a,b=b,a+b;print a

Try it online!


Thanks for @pppery for saving a whole 22 bytes!

\$\endgroup\$
3
  • \$\begingroup\$ Do it recursively would golf it a lot. \$\endgroup\$
    – null
    Jul 10, 2020 at 9:01
  • \$\begingroup\$ @HighlyRadioactive Thanks for the idea, but I didn't figure it out how to do it. Do you know how? \$\endgroup\$
    – mathcat
    Jul 10, 2020 at 9:28
  • \$\begingroup\$ If you do the print before the reassignment you can initialise a and b on the same line \$\endgroup\$
    – Jo King
    Jul 11, 2020 at 2:49
0
\$\begingroup\$

Rockstar, 121 110 86 82 bytes

1-indexed

listen to N
X's1
Y's1
while N
let Z be X+Y
let X be Y
let Y be Z
let N be-1

say X

Try it here (Code will need to be pasted in)

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

x86 machine code - 15 bytes

This is the easiest way my answer to generate fibonacci numbers. I don't believe using XADD instruction, I can generate fibonacci numbers. Well, output store in eax, debug it using GDB with peda (GDB plugin) to make debugging easier. Just make a breakpoint at fib_seq label then s (mean single-step).

So this is example :

     1                                  global fib_seq
     2                                  section .text
     3                                  
     4                                  fib_seq:
     5 00000000 31C0                        xor eax, eax ; eax = 0
     6 00000002 6A01                        push 1
     7 00000004 5A                          pop edx      ; edx = 1
     8 00000005 6A0A                        push 10
     9 00000007 59                          pop ecx  ; loop counter
    10                                  .loop:
    11 00000008 E305                        jecxz .exit_loop
    12 0000000A 0FC1D0                      xadd eax, edx
    13 0000000D E2F9                        loop .loop
    14                                  .exit_loop:
\$\endgroup\$
0
\$\begingroup\$

VBScript, 41 bytes

sub f(x,y):msgbox x:f y,x+y:end sub:f 1,1

Very simple self-explanatory recursive function.

It outputs its first parameters and recursively called again with the second parameter and first+second parameter. And first it is called with 1,1.

1,1 -> 1, f(1,2)
1,2 -> 1, f(2,3)
2,3 -> 2, f(3,5)

and so on

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

PHP 4 (58 chars)

The function f will print $n Fibonacci numbers.
If $n = 0 f will take it for Infinity, then reach the PHP floating point limit and print NAN forever.

function f($n){for($i=!$j=0;$n-=print' '.$j=-$j+$i+=$j;);}

PHP with GMP (70 chars)

If GMP is available, it allow for arbitrary-length integers to be worked with.
So we can compute f(1e5), output will be 1,045,063,704 chars long with no precision loss.

function f($n){for($i=!$j=0;$n-=print' '.$i=gmp_add($k=$i,$j);$j=$k);}

Info: f(1e5) = 25974...46875 has 20,899 digits.

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

Nim, 48 bytes

proc f(n:int):int=(if n<=2:1 else:f(n-1)+f(n-2))

Attempt This Online!

Bytes counted using wc -c. This is the standard recursive function approach, as opposed to the iterative full program of my other answer.

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

MathGolf, 1 byte

f

Try it online!

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

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