111
\$\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\$

224 Answers 224

0
\$\begingroup\$

Reflections, 93 bytes

     \
/*\/#  (0:0\
* 0\_*;(0\/ :(0\
  \     v/#@/_ /
\  (1/ 1)0)*
        : \\/
        \(1/

Test it!

Explanation:

Initialisation

Executing \*/(1\*/*\0\.

  • * at (5|2) pushes 5×2=10 (\n)
  • (1 moves the newline to stack 1
  • * at (0|2) pushes 0×2=0 (F(-1))
  • * at (1|1) pushes 1×1=1 (F(0))
  • 0 moves these two values to stack 0

Loop

Executing v1):\(1/\\0)#/:(0\/_//\*@\0:(0#/\_*;(0\/.

  • 1) pulls the newline from stack 1
  • : duplicates it
  • (1 moves the duplicate to stack 1
  • 0) pulls the last result from stack 0
  • # redefines (0|0)
  • : duplicates the last result
  • (0 moves the duplicate back to stack 0
  • _ at (3|0) converts the last result to a list of digits
  • * at (1|1) pushes 1×1=1
  • @ prints the last result and a newline
  • 0 pulls both values from stack 0
  • : duplicates the top one (newer one)
  • (0 pushes the duplicate back to stack 0
  • # redefines (0|0)
  • _ at (0|1) adds the two values together
  • * at (1|1) pushes 1×1=1
  • ; pops that again
  • (0 pushes the new result to stack 0
\$\endgroup\$
0
\$\begingroup\$

Stax, 2 bytes

|5

Run and debug online!

Added for completeness. An internal that returns 0-indexed Fibonacci number.

Infinite sequence generator without using the internal:

ò¶AÄ∟

The ASCII equivalent is

01WQb+
\$\endgroup\$
0
\$\begingroup\$

SmileBASIC, 28 bytes

F.,1DEF F X,Y?Y
F Y,X+Y
END

Ungolfed:

F 0,1
DEF F X,Y
 PRINT Y
 F Y,X+Y
END
\$\endgroup\$
0
\$\begingroup\$

Elixir, 49 bytes

Defines a function to get the nth fibonacci number. 1-indexed (starts at 0).

Simple recursive formula. Slow.

def f(n)when n<2,do: n
def f(n),do: f(n-1)+f(n-2)

Try it online!

Elixir, 50 bytes

Returns an infinite stream of fibonacci numbers. 1-indexed (starts at 0).

Fast, carries over an accumulator with the sum of the previous two numbers.

fn->Stream.unfold{0,1},fn{a,b}->{a,{b,a+b}}end end

Try it online!

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

Javascript, 57 bytes

_=1;i=0;for(z=10;z--;)alert((a=>!(o=_+i)+(i=_)+!(_=o))())

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

Python 2, 33 31 bytes

i=j=1
while 1:print j;i,j=j+i,i

Try it online!

Uses a loop to infinitely print the sequence. Will eventually error out due to integer overflow. It has been pointed out to me that Python uses arbitrary precision integers. Learn something new every day!

\$\endgroup\$
  • 1
    \$\begingroup\$ Python uses arbitrary precision integers so an integer overflow will not occur. \$\endgroup\$ – Jonathan Frech Aug 3 '18 at 14:48
  • \$\begingroup\$ i,j=1,1 can be i=j=1. \$\endgroup\$ – Jonathan Frech Aug 3 '18 at 14:48
0
\$\begingroup\$

µ6, 16 bytes

[>#[,.[+.]][[,>[#/0[+/1]<>]]/1]]

Try it online!

Explanation

[>                               -- right element of the tuple generated by
  #                              -- | primitive recursive function
                                 -- | base case:
   [,                            -- | | pair of
     .                           -- | | | constant zero
     [+.]                        -- | | | successor of constant zero
   ]                             -- | | : (0,1)
                                 -- | recursive case:
   [                             -- | | compose the two
    [,                           -- | | | pair of
     >                           -- | | | | the right element
     [#/0[+/1]<>]                -- | | | | add left & right element
    ]                            -- | | | (snd, fst + snd)
    /1                           -- | | | second argument (we only need the tuple)
   ]                             -- | : (f (n-1), f (n-2) + f (n-1))
]                                -- : f n
\$\endgroup\$
0
\$\begingroup\$

Julia 0.6, 19 bytes

!a=round(φ^a/√5)

Try it online!

This is 16 chars and 19 bytes, a goof way to abuse Julia beats the existing Julia answers which were 20 bytes. by 1 bytes and 3 chars

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

Little Man Computer, 45 bytes, 8 instructions

Note: both answers only work up to \$ f(15) = 987 \$, as the maximum value for an integer in LMC is \$ 999 \$.

The first solution generates Fibonacci numbers 'indefinitely':

LDA 7
ADD 8
STA 7
SUB 8
STA 8
OUT
BRA 0
DAT 1

and is assembled into RAM as

507 108 307 208 308 902 600 001

86 bytes, 14 instructions

The second solution returns the Fibonacci number at the index given (0-based indexing):

INP
STA 0
LDA 12
ADD 14
STA 12
SUB 14
STA 14
LDA 0
SUB 13
BRP 1
LDA 14
OUT
DAT 1
DAT 1

...which is assembled into RAM as:

901 300 512 114 312 214 314 500 213 801 514 902 001 001

You can test these on the online simulator here.

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

Tcl, 71 bytes (function implementation=43, Enter=1, call=27)

proc F x {expr $x>1?\[F $x-1]+\[F $x-2]:$x}
while 1 {puts [F [incr i]]}

Try it online!

Serves both purposes: Has a function F that allows calculate the x'th Fibonacci number. then it is called to show on stdout F applied to the whole range of positive integers.

\$\endgroup\$
  • \$\begingroup\$ tcl,89: Different approach — iterative. demo — but it does not have a function and fails to represent the first one. \$\endgroup\$ – sergiol Jul 8 '17 at 22:17
  • \$\begingroup\$ Failed outgolf; tcl,91 (function implementation=56, Enter=1, call=34): tio.run/##K0nO@f@/oCg/WaEkOcfKKjexJCOtNC/… \$\endgroup\$ – sergiol Nov 5 '17 at 17:08
  • \$\begingroup\$ You can use less expr as there's a leading one, in escaping evaluation of each 1st brackets code 45B \$\endgroup\$ – david Dec 16 '18 at 20:00
  • \$\begingroup\$ Thanks @david . I did not know I could do it by escaping [ with `\`. I bet I have some more answers I can golf them the way you described. \$\endgroup\$ – sergiol Dec 16 '18 at 20:52
0
\$\begingroup\$

Pure, 66 bytes

using system;do(printf"%Zd\n")(f 1L 1L with f a b=a:f b(a+b)&end);

Try it online!

First answer in Pure \o/

Prints until TIO stops it or the heat death of the universe, whatever comes first.

How:

using system;do(printf"%Zd\n")(f 1L 1L with f a b=a:f b(a+b)&end); // Anonymous lambda;
using system;                                                      // Import system functions
             do                                                    // Infinite loop
               (printf"%Zd\n")                                     // Print bigints + linefeed
                              (f 1L 1L                             // Declare f with 2 bigint args
                                                                   // starting with 1
                                       with f a b=                 // with f(a,b) being
                                                  a:f b(a+b)       // a list from a until f(b,(a+b));
                                                            &      // transformed into a stream
                                                                   // to prevent overflowing
                                                             end);
\$\endgroup\$
0
\$\begingroup\$

R, 37 bytes

Prints the n'th term using the closed form.

https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

function(n,s=5^.5)round((s/2+.5)^n/s)

Try it online!

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

C# (.NET Core), 68, 56 bytes

Lambda using decimal size for single n.

EDIT: Ty Jo King for pointing out better ways to assign the maths to the vars!

p=>{decimal a=0,b=1,j=0;for(;j++<p;b=a-b)a+=b;return a;}

Try it online!

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

Awk, 35 bytes

BEGIN{for(y=1;z=x+y;y=z)print(x=y)}

Try it online

\$\endgroup\$

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.