# Fibonacci function or sequence

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.

/* 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 COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.

/* App */

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

}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(a) {
});
comment_page = 1;
}
});
}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
});
else process();
}
});
}

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

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

function process() {
var valid = [];

var body = a.body;
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],
});
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;

.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)

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)
language = jQuery(language);
jQuery("#languages").append(language);
}

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

width: 290px;
float: left;
}

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

font-weight: bold;
}

table td {
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="language-list">
<h2>Shortest Solution by Language</h2>
<table class="language-list">
<tr><td>Language</td><td>User</td><td>Score</td></tr>
<tbody id="languages">

</tbody>
</table>
</div>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>

</tbody>
</table>
</div>
<table style="display: none">
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
</tbody>
</table>

• I am sort of waiting for a response like "f", 1 byte, in my math based golf language. – Zsolt Szilagy Aug 11 at 11:57

# Flurry, 54 bytes

<>{<>(){}(<>())}{{}[<>{<>(){}{}[<><<>()>]}{({})}]{{}}}


This is an anonymous function that takes a number $$\n\$$ as a Church numeral and pushes $$\F_n\$$ to the stack as a Church numeral.

It can be tested by invoking the interpreter as follows:

$./Flurry -inn -c '<>{<>(){}(<>())}{{}[<>{<>(){}{}[<><<>()>]}{({})}]{{}}}{}' 10 55  Note that this is very slow for large inputs (>30 or so) because Church numeral addition is $$\O(n)\$$. ## Explanation The basic idea is to loop $$\n\$$ times and keep track of the smaller number using the stack and the larger number using function parameters, so the function to iterate looks like this: next = λb. pop() + push(b)  Flurry is mostly combinator-based, and so doesn't really have lambdas. The closest approximation is to write a function that pushes its argument onto the stack (using the {...} monad) and then pops from the stack to read the argument back (using the {} nilad). So the function λx. f x gets represented as: { f {} }  However, this translation doesn't work if f depends on the stack, which is true in this case, so we need to use a combinator-based approach instead. Rather than popping using {} directly, we can write an anonymous function that ignores its argument and returns a value popped from the stack:  λa. pop() { <> () {} {} }  Here, <> and () represent the S and K combinators respectively. Of course, the next thing we do with the popped value is apply it to the successor function <><<>()> to compute addition:  λa. pop()(suc) { <> () {} {} [<><<>()>] }  Now all we need is to write a function that pushes its argument to the stack and returns it unchanged:  λa. push(a) { ({}) }  We can then put these functions together using the S combinator:  λb. pop() + push(b) λb. S (λb. pop()(suc)) (λb. push(b)) b <> {<>(){}{}[<><<>()>]} {({})}  The main function is responsible for setting up the initial values and calling next the appropriate number of times. In other words, it looks like this: main = λn. push(0); n (next) (1)  Since we don't care about the return value, we can just use function application to sequence the two actions: main = λn. push(0) (n (next) (1))  Again, we can't keep lambda variables on the stack because we're already doing stack manipulation, so we'll have to create intermediate functions. First, one that ignores its argument and pushes 0 to the stack:  λa. push(0) { <> () {} (0) }  Second, one that applies its argument to next and 1 (which we can finally use stack lambdas for):  λa. a next 1 { {} next 1 }  Again, we can put these together with S: <> {<>(){}(0)} {{}[next]1}  Substituting the definitions of 0, next, and 1 gives us the final result: <>{<>(){}(<>())}{{}[<>{<>(){}{}[<><<>()>]}{({})}]{{}}}  • Is it some kind of functional brain-flak? :D – Bubbler Aug 10 at 23:13 • @Bubbler Pretty much. – Esolanging Fruit Aug 10 at 23:46 • Given the git description is "Brain-flak, but functional.", I'd say yes – Jo King Aug 11 at 0:52 • I just opened a chat room for Flurry. – Bubbler Aug 12 at 23:49 ## Python, 36 f=lambda x:x>1and f(x-1)+f(x-2)or x  ## Python a,b,n=0,1,10 while n:a,b,n=b,a+b,n-1;print b  • a=b=1<newline>while 1:print a;a,b=b,a+b 30 Characters – st0le Feb 1 '11 at 6:19 • @st0le that's actually 31 characters. I've spent like 5 minutes recounting my solution, which is identical to yours, until I came to the conclusion you are wrong :) – Mikle Nov 24 '11 at 18:02 • The fibonacci sequence starts with 0. So you can't do a=b=1. It should be something like a,b=0,1\nwhile 1:print a;a,b=b,a+b which is 33 characters. – Bakuriu Sep 1 '12 at 9:42 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)  • You can remove the space between 2 and or – Cyoce Oct 14 '16 at 0:52 ## 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. • actually it's O(log n) since pow has that complexity... – JBernardo Jul 10 '11 at 2:03 • @JBernado and even bigger since pow for bigint is more complicated story. – shabunc Aug 19 '11 at 8:49 ## 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)  • The second term starts small and only becomers smaller later on, so it can always be replaced by integer rounding. Golfing that a bit gives 30 byes: say.5+(.5+5**.5/2)**<>/5**.5|0 – Ton Hospel Mar 6 '16 at 13:35 ## PHP - 1099788 49 characters <?for($a=$b++;;$b+=$a=$b-$a){$s+=$b%2*$b;echo$a;}  • I have confirmed this works without using the optional parameters, but what exactly are they for? – Kevin Brown Mar 17 '11 at 1:42 • @Bass5098: So that the function works when called in a unary context, I presume. If PHP uses JS-style argument passing where you can supply fewer arguments than the function declares, and you can perform meaningful computations involving undefined (or the PHP equivalent thereof), then cool! – Chris Jester-Young Mar 17 '11 at 16:35 Perl - 39 chars ($a,$b)=($b,$a+$b||1),print"$b "while$=


# 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.

Mathematica,26 chars

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

• Damn, and I just thought I had come up with a new shortest Fibonacci implementation in Mathematica. +1 :) – Martin Ender Jan 30 '15 at 21:08
• What does the trailing & do? – Cyoce Oct 14 '16 at 0:55
• @Cyoce making it a function, instead of an expression – Keyu Gan Feb 1 '18 at 0:40

## F# - 42 chars

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

• Nice, I didn't know about Seq.unfold! =) – Roujo Feb 8 '16 at 20:32

# JAGL V1.0 - 13 / 11

1d{cdc+dcPd}u


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

11 bytes

1d{cdc+cd}u


# 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 :).

• I don't think you need the [1 0]. Picking the second item out of the matrix will give you the right number anyway. – Andrew Apr 16 '15 at 21:37
• Thank you for notice, f=@(n)([1 1;1 0]^n)(3) is six characters shorter indeed (Octave enumerates items in matrix top-down and then left-right when indexing with a single number, so the value at first row, second index is at index 3). – pawel.boczarski Apr 16 '15 at 22:22

# 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


# Ruby, 28 bytes

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


Usage:

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


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

Мȫï


Try it here (Firefox only).

More builtins!

math.js + numbers.js = hella functions

# 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.

# 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.

# 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.

# Python 2, 43 bytes

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


# Python 33 characters

x,y=0,1
while 1:print x;x,y=y,x+y


This will be an infinite loop!

# Python 31 characters

def f(a=[1,0]):a[:]=a[1],sum(a)


demonstration

for _ in range(10):
f(); print f.func_defaults[0][0]

0
1
1
2
3
5
8
13
21
34

• The loop for your "31 char" program would need to be included in the score. – mbomb007 Nov 4 '16 at 15:00
• ^^ also, we usually give the count in bytes, not characters. – FlipTack Dec 28 '16 at 12:25

# 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
r    ;standard library call, reverses a stack
;stack implicitly printed


# 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.

# 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
17
17
14
swap
17
17
4
17

11
6
0
0
1

• Welcome to the site! This is a cool answer, I've never heard of the language before. :) – James May 4 '17 at 17:29

# 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.

# 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.


# 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.

• If I'm not mistaken, you don't need to the () around exec in Python 2. – Stephen Jul 21 '17 at 14:07
• @StepHen That seems to be true, thanks, down by 2 chars – SydB Jul 21 '17 at 14:11
• Oh, I almost forgot: this would be considered a snippet because it preassumes the value of n. Generally you must write either a full program that gets input, or a function. So, you would have to replace n with input(). See this meta post for more information. – Stephen Jul 21 '17 at 14:15

# 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, ' '; }  • This can be 31 bytes since you don't need PHP's opening tag (you can run with php -r "code here" without opening tag) and you can use _ as separator instead of space: Try it online! – Night2 Sep 25 '19 at 9:42 # Klein, 2322 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.

# C, 64 bytes

a,x,y,z=1;main(){for(;;){a=y;y=z;z=a;x+=y;y=x;printf("%d ",x);}}


Try it online! Uses the same method as my Implicit answer.

• – Jonathan Frech Aug 19 '18 at 4:01