129
\$\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\$
1
  • 2
    \$\begingroup\$ I am sort of waiting for a response like "f", 1 byte, in my math based golf language. \$\endgroup\$ – Zsolt Szilagy Aug 11 '20 at 11:57

278 Answers 278

1
6 7 8 9
10
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\$

BRASCA, 13 bytes

After being inactive here for god knows how long, I built a little esolang and decided to put it to the test.

Outputs each number seperated by newline.

nlo1[:n:R+lo]

Explanation

n                   - Output 0 as number (an empty stack always pops zero)
 lo                 - Push 10 (line feed) to the stack and print it
   1                - Push 1 to the stack
    [       ]       - While not zero:
     :n             -   Output the number
       :R+          -   Add it with the previous number
          lo        -   And print another line feed

Language Link

Github Repo

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

Pxem, Filename: 29 bytes + Content: 0 bytes = 29 bytes.

Outputs fibonacci sequence, separated with space.

  • Filename (escaped): \001.rX\001.w.c.n.c.t.v.m.v.+ .oX.a
    • Actual: .rX.w.c.n.c.t.v.m.v.+ .oX.a
  • Content: empty.

Try it online!

With comments

XX.z
# push 1; push $(($(pop)*$(rand)))
# NOTE rand pushes 0<=x<1
# NOTE null character cannot be used for filename
.a\001.rXX.z
# push 1; push 88; while [ $(pop) -ne 0 ]; do
.aX\001.wXX.z
  # Do I really need to explain more?
  # Just read the specification; I am going to bed
  # also a sequence .t.v.m.v is an idiom
  # to move top item to bottom
  .a.c.n.c.t.v.m.v.+ .oX.a
\$\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\$

Duocentehexaquinquagesimal, 5 bytes

±∊YO$

Try it online! Link is to a version with output; this one just writes the sequence to memory. Outputs codepoints of the entire sequence. Stops eventually because of memory limitations.

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

Python 3.8 (pre-release), 126 bytes

Neither short nor pretty, but possibly a new method!

from decimal import*
def f(n):l=n//4+1;p=10**l;getcontext().prec=n*l-l+1;return int(str(Decimal(p**2)/Decimal(p**2-p-1))[-l:])

Uses, for example:

1/(1000000-1000-1) = 0.000 001 001 002 003 005 008 013 021 034 055 089 ...

l can be any upper bound for the number of digits of the Fibonacci number after the one we want.

Try it online!

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

Grok, 16 bytes

1z1j
wYZlYp2yp+9

Try it Online!

Prints an infinite, tab-separated sequence. (Tabs instead of spaces/newlines since they are golfier.) The 5 flag is just so it times out faster.

Explanation:

1z           # Print the initial 1
  1          # Push 1 to the stack
   j         # Start the IP moving down
   l         # Start the IP moving right
    Yp       # Get the last number on the stack
      2yp    # Get the number before that (initially 0)
         +   # Add them together
w         9  # Print a Tab
 YZ          # Print the next number without popping it
\$\endgroup\$
1
6 7 8 9
10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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