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. Aug 11 '20 at 11:57

C++, 42 bytes

I haven't read every solution in this challenge, but the leaderboard doesn't have a C++ solution, which is a travesty.

int f(int i){return i-->1?f(i)+f(i-1):!i;}

• You can save 1 byte by getting rid of the --, making it f(i-1)+f(i-2) and then (that's where you save the byte) !i can be just i. Jul 15 '20 at 8:32

bash pur, 49 chars, third solution

r=0;l=1;echo -e {1..45}" $((r+=l))$((l+=r))\n";


bash pur, 52 chars, second solution

r=0;l=1;echo -e {1..40}" "$((r+=l))" "$((l+=r))\\n;


former solution (60 chars):

r=0;l=1;for i in {1..40};do((r+=l));((l+=r));echo $r$l;done

• Could be written: r=1 l=0;echo -e {,,}{,,}{,,}" $[r+=l]$[l+=r]" Feb 27 '19 at 0:08
• ... And former version: for((r=1,l=1;l<9**9;r+=l,l+=r)){ echo $r$l;} Feb 27 '19 at 0:16
• 34 chars: for((a=1;b+=a;a+=b)){ echo $a$b;} Aug 28 '19 at 8:56
• @F.Hauri: My improved solution is only 1 char longer than yours, with preserving the line oriented output, while your solution doesn't reach the max possible value before integer overrun. Aug 28 '19 at 19:27
• @roblogic: In my opinion, negative results are not acceptable, but with a halting condition like for((a=1;b+=a;a+=b)){ echo $a$b;}|head -n46 your code is still 4 characters shorter than mine (improved one) - so why don't you publish your solution as an answer, or did you? Aug 28 '19 at 19:32

Flobnar, 19 bytes

@\
#_+_1
!_:.
:>+_,9
+ <>$.  Try it online! • +1 for 'I should probably check if I've already answered a question' Aug 29 '19 at 9:00 Java, 90 characters and just two variables There was one before with 55 characters, but it used a variable without declaring it and had no output. This one has both and (the actual logic) is shorter. And as a little bonus it looks absolutely horrific code-style-wise and depends on compiler quirks, yay! interface A{static void main(String[]x){for(int a,b=a=1;;System.out.println(b=a+(a=b)));}}  The special features I used are: • Using an interface instead of a class. The program can still be run as normal, but I don't need to write "public" twice. This saves 10 characters • Declaring multiple variables at once: int a,b; • Initializing multiple variables at once and in the declaration, needs a second a: b=a=1; • Everything is done in the for head, the body is empty: for(...); The first and third block of for are intended for variable initialization and variable incrementation, but they can hold any commands. • The whole logic is inside the output: System.out.println(b=a+(a=b)) • Just two variables without recursion! This is done by using the way the compiler works: The assignment to b first reads the value of a, then it evaluates the right side of the +, where it reads the value of b and writes it into a, but the left side of the + still has the old value of a that gets added to the value of b after assigning the value of b to a. Then that sum gets written to b while a already holds the old value of b. I was lucky that the compiler works this way, because it could also have first evaluated the expression in the brackets, like for example C does, then it just lists all powers of 2 instead of the Fibonacci numbers. In a dream programming language this would just be: b=a+(a=b • Dammit, referring to this answer just helped me in actually useful code, but I can't upvote it! :D May 27 '19 at 21:56 Erlang (escript), 36 bytes I'm a total idiot. I didn't even think of this formula! f(X)when X<2->1;f(X)->f(X-1)+f(X-2).  Try it online! Erlang (escript), 50 bytes f(X,Y)->io:write(X),io:nl(),f(Y,X+Y). f()->f(1,1).  Try it online! Erlang (escript), 51 bytes Tail-recursion optimized. f(0,X,_)->X;f(I,X,Y)->f(I-1,Y,X+Y). f(X)->f(X,1,1).  Try it online! 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 Aug 10 '20 at 23:13
• @Bubbler Pretty much. Aug 10 '20 at 23:46
• Given the git description is "Brain-flak, but functional.", I'd say yes
– Jo King
Aug 11 '20 at 0:52
• I just opened a chat room for Flurry. Aug 12 '20 at 23:49

Javascript, 272625 23 characters

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


In an interactive javascript command line (Like google chrome console) it'll print out the nth fibonacci term for n > 1. undefined for n=1, runs forever for n < 1.

Credit to Bojidar Marinov

41 characters

for(x=[1,1],y=1;n-++y;)x[y]=x[y-1]+x[y-2]


Saving the n (>=2) first terms in an array.

• 25: for(b=a=1;n--;)b*=a=1+1/a 23: for(a=b=1;n--;)a+=b=a-b Sep 25 '20 at 17:10

APL (Dyalog Unicode), 7 bytes

This algorithm is based on Pascal's Triangle, and I take no credit for it. Simply submitting it for completeness.

+.!∘⌽⍨⍳


+.! is the summation of binomial coefficients. In this context k!n can be thought of as the kth element in the nth row of Pascal's Triangle (zero indexed).
∘ is the function composition operator called Beside.
⌽ reverses the array.
⍨ is the commute operator, known as Selfie, it's used to copy the array to the left side of the composed function.
⍳ the index generator creates a range, from 0–(n-1) inclusive.

Try it online!

COBOL (GNU), 170 bytes

I am surprised at the lack of COBOL answers on this site. Well, it is ancient after all.

This outputs the fibonacci sequence correctly up to 38 digits.

PROGRAM-ID.H.DATA DIVISION.LOCAL-STORAGE SECTION.
1 a PIC 9(38).
1 b PIC 9(38).
PROCEDURE DIVISION.G.COMPUTE a=0**b+b -a
DISPLAY b(38- FUNCTION LOG10(b):)GO G.


Try it online!

Explanation

We just need two variables, a and b to compute the whole fibonacci sequence. Here is pseudocode of what this would look like:

a = 0
b = 1
loop {
a = b - a
b += a
print(a)
}


Translating the pseudocode above in COBOL is relatively short and simple. But we see that variables in COBOL are set to 0 by default, and having one of them set to a 1 is kind of (8 bytes) long, so we hack it out like so:

a = 0
b = 0
loop {
a = b - a + 0 ** b
b += a
print(b)
}


The 0 ** b ensures that a = 1 on the first iteration. From then on, the logic is the same as in our first pseudocode implementation (since 0 ** (any number greater than 0) = 0). The change from print(a) to print(b) is just to ensure that the numbers are outputted in the correct order.

Ungolfed

PROGRAM-ID. H.

DATA DIVISION.
LOCAL-STORAGE SECTION.
1 a PIC 9(38).                     // Declare a variable named a (a = 0)
1 b PIC 9(38).                     // Declare a variable named b (b = 0)

PROCEDURE DIVISION.
G.                                 // Define a label named G
COMPUTE a=0**b+b -a                // a = b - a + 0 ** b
ADD a TO b                         // b += a
DISPLAY b(38- FUNCTION LOG10(b):)  // Print b without trailing zeros
GO G.                              // Jump to the label named G (4 lines above)


Red, 36 bytes

Infinitely outputs the fibonacci sequence. Also see @Razetime's answer for a recursive version which outputs the nth number.

a: b: 1
forever[print a b: a + a: b]


Try it online!

Red, 36 bytes

An alternative 36.

a: 1 b: 0
forever[print b: a + a: b]


Try it online!

Vyxal, 2 bytes

ÞF


Try it Online!

Before you go saying that the online link doesn't match the submission here, that's because the extra , is needed to actually make the output appear online. If you use the offline version, then you will see that the above works just fine. Also, the 5 flag makes sure that the online interpreter times out after 5 seconds.

Explained

ÞF  # Push every Fibonacci number


And now for the non-trivial version

Vyxal5, 6 bytes

⁽+dk≈Ḟ


Try it Online!

Once again, discrepancies between online link and actual version are for the purposes of making it work online.

Explained

⁽+dk≈Ḟ
⁽+d     # lambda x, y: x + y
k≈   # the list [0, 1]
Ḟ  # Create an infinite sequence based on the function and the initial list.


Fun fact: the infinite sequence function you see was inspired by the sequence blocks of the golfing language Arn by ZippyMagician.

• Fun fact: I was inspired by Raku when I added sequences Apr 11 at 2:36

jq-n, 30 28 bytes

-2 bytes thanks to Michael Chatiskatzi!

Prints the infinite sequence.

[0,1]|while(1;[last,add])[1]


Try it online!

Start with [0,1].
while(1; ... ) infinite loop, 1 is a truthy value.
[last,add] the new pair is the last value of the old pair and the sum of the old pair.
while returns all intermediate pairs, [1] gets the second element of each pair.

jq, 35 33 bytes

A recursive filter written for this tip.

def f:(.<2//[.-1,.-2|f]|add?)//.;


Try it online!

• 28 bytes Sep 10 at 21:45

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 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 :) 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. 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 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... Jul 10 '11 at 2:03
• @JBernado and even bigger since pow for bigint is more complicated story. 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 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? 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! 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.

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

• Surely, with APL's prodigious operator vocabulary, it should be able to compete in size with the GolfScript one? ;-) Apr 8 '13 at 11:32
• @ChrisJester-Young Oh probably, but I only started learning APL today...
– SL2
Apr 8 '13 at 23:41
• Utilizing Pascal's triangle {+.!∘⌽⍨¯1+⍳⍵} Apr 8 at 22:24

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 :) Jan 30 '15 at 21:08
• What does the trailing & do? Oct 14 '16 at 0:55
• @Cyoce making it a function, instead of an expression 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! =) 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. 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). 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.