Fibonacci function or sequence

Question

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>

Answer 1

Desmos, 41 bytes

Code in ticker:

l->join(l,l[L]+l[L-1])

Code not in ticker

l=[1,1]
L=l.length

Try it online

Answer 2

Python

a,b,n=0,1,10
while n:a,b,n=b,a+b,n-1;print b

Answer 3

Python, 34 chars first variant, 31 chars for second variant,

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

Second variant:

f=lambda x:x<2 or f(x-2)+f(x-1)

Answer 4

Python O(1) Nth number, 91 char

48 characters for the import, a newline, 42 for the rest. I know it's longer than most here and that the question is a bit old, but I looked through the answers and I didn't see any that use the constant-time floating-point calculation.

from math import trunc as t,pow as p,sqrt as s
r=s(5);i=(1+r)/2;f=lambda n:t(p(i,n)/r+.5)

From there you call f(n) for the nth number in the sequence. Eventually it loses precision, and is only accurate up through f(70) (190,392,490,709,135). i is the constant Phi.

Answer 5

Perl, 51 (Loopless)

The following code uses Binet's formula to give the Nth Fibonacci number without using any loops.

print((($p=5**.5/2+.5)**($n=<>)-(-1/$p)**$n)/5**.5)

Answer 6

PHP - 109 97 88 49 characters

<?for($a=$b++;;$b+=$a=$b-$a){$s+=$b%2*$b;echo$a;}

Answer 7

Perl - 39 chars

($a,$b)=($b,$a+$b||1),print"$b
"while$=

Answer 8

C#

Generated as a stream (65 chars):

IEnumerable<int>F(){for(int c=1,s=1;;){s+=c=s-c;yield return c;}}

Could be reduced to 61 characters using non-generic IEnumerable. Of course, if you include the required System.Collections.Generic, then it's a few more characters.

Answer 9

APL: 26 characters

This is a function which will print out the n and n-1 Fibonacci numbers:

{({⍵+.×2 2⍴1 1 1 0}⍣⍵)0 1}

For example,

{({⍵+.×2 2⍴1 1 1 0}⍣⍵)0 1}13

yields the vector:

233 144

Answer 10

Mathematica,26 chars

If[#>1,#0[#-1]+#0[#-2],#]&

Answer 11

F# - 42 chars

Seq.unfold(fun(a,b)->Some(a,(b,a+b)))(0,1)

Answer 12

JAGL V1.0 - 13 / 11

1d{cdc+dcPd}u

Infinite Fibonacci sequence. Or, if not required to print:

11 bytes

1d{cdc+cd}u

Answer 13

Octave, 26 chars

f=@(n)([1 0]*[1 1;1 0]^n)(2)

Basically, a copy of my solution from Calculating (3 + sqrt(5))^n exactly.

, so

It's a disaster to do unnecessary* loops in Octave/Matlab. It's neither elegant, nor fast, let alone golfy.

---

*All loops that can be vectorized are unnecessary :).

Answer 14

ArnoldC, 451 bytes

IT'S SHOWTIME
HEY CHRISTMAS TREE a
YOU SET US UP 1
HEY CHRISTMAS TREE b
YOU SET US UP 1
HEY CHRISTMAS TREE c
YOU SET US UP 1
STICK AROUND c
TALK TO THE HAND a
GET TO THE CHOPPER a
HERE IS MY INVITATION a
GET UP b
ENOUGH TALK
TALK TO THE HAND b
GET TO THE CHOPPER b
HERE IS MY INVITATION b
GET UP a
ENOUGH TALK
GET TO THE CHOPPER c
HERE IS MY INVITATION 1e300
LET OFF SOME STEAM BENNET a
ENOUGH TALK
CHILL
YOU HAVE BEEN TERMINATED

This is actually my first ArnoldC program. Horrible for golfing, but great for lolz!

Produces an stream of Fibonacci numbers up to 1.1253474885494065e+274.

Explanation

IT'S SHOWTIME               #start program

HEY CHRISTMAS TREE a        #declare a...
YOU SET US UP 1             #and set it to 1
HEY CHRISTMAS TREE b        #declare b...
YOU SET US UP 1             #and set it to 1
HEY CHRISTMAS TREE c        #declare c...
YOU SET US UP 1             #and set it to 1

STICK AROUND c              #while c is truthy
TALK TO THE HAND a          #output a
GET TO THE CHOPPER a        #assign a to...
HERE IS MY INVITATION a     #a...
GET UP b                    #plus b
ENOUGH TALK                 #end assignment
TALK TO THE HAND b          #output b
GET TO THE CHOPPER b        #assign b to...
HERE IS MY INVITATION b     #b...
GET UP a                    #plus a
ENOUGH TALK                 #end assignment
GET TO THE CHOPPER c        #assign c to...
HERE IS MY INVITATION 1e300 #whether 1e300...
LET OFF SOME STEAM BENNET a #is greater than a (returns 0 or 1)
ENOUGH TALK                 #end assignment
CHILL                       #end while

YOU HAVE BEEN TERMINATED    #end program

Answer 15

Ruby, 28 bytes

->f{loop{f<<p(f[-1]+f[-2])}}

Usage:

->f{loop{f<<p(f[-1]+f[-2])}}[[-1,1]]

Answer 16

𝔼𝕊𝕄𝕚𝕟, 3 chars / 6 bytes (noncompetitive)

Мȫï

Try it here (Firefox only).

More builtins!

math.js + numbers.js = hella functions

Answer 17

PARI/GP, 9 bytes

fibonacci

Alternate solution (21 bytes), for those disliking the built-in:

n->([1,1;1,0]^n)[1,2]

Alternate alternate solution (21 bytes):

n->imag(quadgen(5)^n)

I also posted all three solutions (in ungolfed form) to Rosetta Code's Fibonacci page.

Answer 18

Reng v.2.1, 18 bytes

(Noncompeting, postdates question)

11{:nAo}#xxx:)+x5h

11 initializes the stack with 2 1s. {:nAo}#x sets the command x to mean "duplicate and output as number" (:n) then "output a newline" (Ao, A = 10). Then, xx prints the initial 2 1s. : duplicates the TOS and ) rotates the stack, so it becomes b a b. + adds the two figures, making it b (a+b). x prints and leaves this new result on the stack. 5h jumps back 5 spaces, and the loop continues.

Try it out here! Or check out the github!

Answer 19

Fuzzy Octo Guacamole, 11 bytes

01(!aZrZo;)

This takes the infinite route.

Explanation:

01 pushes 0 and then 1 to the stack.

( starts a infinite loop.

! sets the register, saving the value on the top of the stack and storing it. It doesn't pop though.

a adds the 2 values.

ZrZ reverses the stack, pushes the register contents, and reverses again. This pushes the stored number to the bottom of the stack.

o; peeks and prints.

) ends the infinite loop.

Then the whole things starts again from the (.

---

As a a side note, this is quite fast to hit the max long size possible in Python. The last number it prints is 12200160415121876738, and it repeats that forever.

Answer 20

Python 2, 43 bytes

def f(n):k=9**n;return k**-~-~n/~-(k*~-k)%k

Answer 21

Perl 5, 23 bytes

22 bytes, plus 1 for -nE instead of -e.

say$.-=$b+=$.*=-1;redo

Hat tip.

Answer 22

Cylon (Non-Competing), 12 bytes

The language is in development, Im just putting this up here.

1:øÌ[:ì+Á])r

An explanation:

1    ;pushes a 1 to the stack
:    ;duplicates the top of the stack
ø    ;reads a number from stdin, pushing it to the stack
Ì    ;non-pushing loop, doesn't push counter to the stack, but deletes it
[    ;start of function, to be pushed to the stack
  :  ;duplicate top of stack
  ì  ;rotate the stack, moving the copy to the back
  +  ;replaces top two objects on the stack with their sum
  Á  ;push the result to the shadowing stack (non-consuming)
]    ;end of function
)    ;switch to shadowed stack
r    ;standard library call, reverses a stack
     ;stack implicitly printed

Answer 23

bc, 21

for(b=1;b=a+(a=b);)a

The trailing newline is significant.

Outputs the entire sequence. bc has arbitrary precision arithmetic, so this continues forever.

Answer 24

OIL, 46 bytes

This program writes an infinite unstoppable stream of fibonacci numbers. It is mostly copied from the standard library but fit to the requirements and golfed.

14
add
17
17
14
swap
17
17
4
17




11
6
0
0
1

Answer 25

Python 2, 30 bytes

f=lambda n:n<3or f(n-2)+f(n-1)

Try it online!

One catch: this outputs True instead of 1. This is allowed by this meta consensus.

Answer 26

Gaia, 6 bytes

0₁@+₌ₓ

I might make a built-in for this in the future, but built-ins are boring anyway.

Explanation

0₁      Push 0 and 1
  @     Push an input
   +₌ₓ  Add the top two stack elements, without popping them, (input) times
        Implicitly print the top stack element.

Answer 27

Python 2, 49 40 chars

a,b=0,1
exec"a,b=b,b+a;"*input()
print b

Function form, 44 chars

def f(n):a,b=0,1;exec"a,b=b,b+a;"*n;return b

My take on this challenge. Didn't find this kind of an answer yet. I hope it's a valid one.

Print's n:th Fibonacci number. Functions by multiplying the string inside exec n times and then executing it as Python.

Edit: input() instead of int(raw_input())

Answer 28

PHP, 39 bytes

<?php for($b=1;;)echo$a=-$a+$b+=$a,' ';

Try it online!

Explanation

<?php

An infinite loop is started. The zero-th term in the series, initially $a, is 0, so needn't be assigned. $b is initially the second term and so is set to 1.

for ($b = 1;;) 

The part which does all the work is echo $a = -$a + $b += $a, ' ';. Here it is expanded.

{

Calculate the new value for $b: the next term is the sum of the previous two.

    $b = $b + $a;

$a needs to be moved on one term as well. It is calculated by subtracting itself from the new value of $b.

    $a = $b - $a;

For byte-saving convenience, it is $a that is echoed each time—followed by a space!

    echo $a, ' ';
}

Answer 29

Klein, 23 22 21 + 3 = 24 bytes (non-competing)

Run with the 000 topology

(1)\((@
):?\1-+(:(+)$

Explanation

When the program starts it executes (1) which will put a 1 under the input. It then deflects into the main loop.

The main loop is on the second line. It starts with the \ character. Unwrapped it looks like:

\1-+(:(+)$):?

This will redirect our pointer if the counter is zero or perform one iteration of the fibonacci sequence otherwise.

Once the counter reaches zero we are deflected to the code ((@, this will hide the top two values (the counter and one of the fibonacci numbers) and terminate the program.

Answer 30

Chip-8, 36 bytes

6301 'LD v3,1
6D05 'LD vD,5
6E0A 'LD vE,A
8344 'ADD v3,v4
A200 'LD I,200
F333 'LDD [I],v3
8343 'XOR v3,v4
8433 'XOR v4,v3
8343 'XOR v3,v4
F265 'LD v2,[I]
F029 'LDF I,v0
00E0 'CLS
DFF5 'DRW vF,vF,5
F129 'LDF I,v1
DDF5 'DRW vD,vF,5
F229 'LDF I,v2
DEF5 'DRW vE,vF,5
1206 'JMP 206

Displays Fibonacci numbers (up to 233) in decimal. (It might be shorter to use hexadecimal, but I think that's cheating)

This one writes the numbers into memory:

6001
A300
8014
F055
8013
8103
8013
1204

... but it's actually longer than valid numbers it writes:

01 01
02 03
05 08
0D 15
22 37
59 90
E9 79 (overflow)