Fibonacci function or sequence

Question 1

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, in accordance to the standard sequence rules:

Generates the Fibonacci sequence without end.
Given n calculates the nth term of the sequence. (Either 1 or zero indexed)
Given n calculates the first n terms of the sequence

You may use standard forms of input and output.

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>

Question 2

I am sort of waiting for a response like "f", 1 byte, in my math based golf language.

Question 3

@ChrisJesterYoung can we use 1.0 are 1 only?

Question 4

@NumberBasher 1.0 is fine.

Question 5

What about 1.3?

Question 6

Am I allowed to start the sequence with 0, 1?

Question 7

Brainfuck, 22 bytes

+>++[-<<[->+>+<<]>>>+]

Generates the Fibonacci sequence gradually moving across the memory tape.

Question 8

Beautiful! Litterally beautiful! Or perhaps not... anyways +1 for this :)

Question 9

This is 3.344 or 4 bytes in compressed brainfuck. (6 ln(22)) / ln(256)

Question 10

16 bytes: +[[<+>->+>+<<]>]

Question 11

14 bytes: +[.[>+>+<<-]>]

Question 12

@Stefnotch of course, the shorter one is destructive. The solution above terminates with the fibonacci sequence on the tape, which is what the 16 byte solution also does.

Question 13

Haskell, (削除) 17 (削除ここまで) (削除) 15 (削除ここまで) 14 bytes

f=1:scanl(+)1f

Try it online!

Question 14

Why not cut two spaces to f=0:scanl(+)1 f?

Question 15

Wow, that's even shorter than the usual f@(_:x)=0:1:zipWith(+)f x! Have to remember it.

Question 16

You may even strip another space: f=0:scanl(+)1f.

Question 17

Perl 6, 10 chars:

Anonymous infinite fibonacci sequence list:

^2,*+*...*

Same as:

0, 1, -> $x, $y { $x + $y } ... Inf;

So, you can assign it to an array:

my @short-fibs = ^2, * + * ... *;

or

my @fibs = 0, 1, -> $x, $y { $x + $y } ... Inf;

And get the first eleven values (from 0 to 10) with:

say @short-fibs[^11];

or with:

say @fibs[^11];

Wait, you can get too the first 50 numbers from anonymous list itself:

say (^2,*+*...*)[^50]

That returns:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169
63245986 102334155 165580141 267914296 433494437 701408733 1134903170 
1836311903 2971215073 4807526976 7778742049

And some simple benchmark:

real 0m0.966s
user 0m0.842s
sys 0m0.080s

With:

$ time perl6 -e 'say (^2, *+* ... *)[^50]'

EOF

Question 18

I wouldn't even think of ^2 as replacement for 0,1. +1

Question 19

This is no longer valid, you will have to write it as |^2,*+*...*, which is the same number of bytes as 0,1,*+*...*.

Question 20

Perl is so weird.

Question 21

What version of Perl 6 was this answer written in?

Question 22

@CalculatorFeline There was a big change known as GLR (Great List Refactor) which happened shortly before the first official release which was on 2015年12月25日. This code would have worked right up until that time.

Question 23

C# 4, 58 bytes

Stream (69; 65 if weakly typed to IEnumerable)

(Assuming a using directive for System.Collections.Generic.)

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

Single value (58)

int F(uint n,int x=0,int y=1){return n<1?x:F(n-1,y,x+y);}

Question 24

Given that n is a uint, n==0 can be shortened to n<1. And the stream can save a few chars by ditching the space after the generic type and declaring x in a wider scope than necessary. In fact, ditch x entirely: n+=c;c=n-c;

Question 25

@Peter: Thanks, will edit when I get some time.

Question 26

Your single value version is as long as my recursive lambda expression answer...nice!

Question 27

@wizzwizz4 if I'm not mistaken, if !n works, then so should just n if you flip the conditional.

Question 28

@JonSkeet Aw. And here I was thinking I'd beaten Jon Skeet at C#... :-)

Question 29

GolfScript, 12

Now, just 12 characters!

1.{[email protected]+.}do

Question 30

+1 nice work. If you make it shorter than 13 chars, I'll instantly accept your answer (unless someone makes an even shorter answer, of course). :-P

Question 31

I love a challenge. Done! ;-)

Question 32

Nice, you win. At least, until someone makes something even shorter (if that's even possible). :-P

Question 33

that definition is almost as short as the name 'Fibonacci' itself! +1

Question 34

Hexagony, (削除) 18 (削除ここまで) (削除) 14 (削除ここまで) 12

Thanks Martin for 6 bytes!

1="/}.!+/M8;

Expanded:

 1 = "
 / } . !
+ / M 8 ;
 . . . .
 . . .

Try it online

Old, answer. This is being left in because the images and explanation might be helpful to new Hexagony users.

!).={!/"*10;$.[+{]

Expanded:

 ! ) .
 = { ! /
" * 1 0 ;
 $ . [ +
 { ] .

This prints the Fibonacci sequence separated by newlines.

Try it online! Be careful though, the online interpreter doesn't really like infinite output.

Explanation

There are two "subroutines" to this program, each is run by one of the two utilised IPs. The first routine prints newlines, and the second does the Fibonacci calculation and output.

The first subroutine starts on the first line and moves left to right the entire time. It first prints the value at the memory pointer (initialized to zero), and then increments the value at the memory pointer by 1. After the no-op, the IP jumps to the third line which first switches to another memory cell, then prints a newline. Since a newline has a positive value (its value is 10), the code will always jump to the fifth line, next. The fifth line returns the memory pointer to our Fibonacci number and then switches to the other subroutine. When we get back from this subroutine, the IP will jump back to the third line, after executing a no-op.

The second subroutine begins at the top right corner and begins moving Southeast. After a no-op, we are bounced to travel West along the second line. This line prints the current Fibonacci number, before moving the memory pointer to the next location. Then the IP jumps to the fourth line, where it computes the next Fibonacci number using the previous two. It then gives control back to the first subroutine, but when it regains control of the program, it continues until it meets a jump, where it bounces over the mirror that was originally used to point it West, as it returns to the second line.

Preliminary Pretty Pictures!

The left side of the image is the program, the right hand side represents the memory. The blue box is the first IP, and both IPs are pointing at the next instruction to be executed.

enter image description here

Note: Pictures may only appear pretty to people who have similarly limited skill with image editing programs :P I will add at least 2 more iterations so that the use of the * operator becomes more clear.

Note 2: I only saw alephalpha's answer after writing most of this, I figured it was still valuable because of the separation, but the actual Fibonacci parts of our programs are very similar. In addition, this is the smallest Hexagony program that I have seen making use of more than one IP, so I thought it might be good to keep anyway :P

Question 35

You should link to whatever you used to make the pretty pictures, then put the link on esolangs.org/wiki/Hexagony.

Question 36

@mbomb007 I used gimp to manually create each frame, then uploaded the images to some gif making website. Although, several times during this process I considered making a tool to do it, considering how tedious it was.

Question 37

@FryAmTheEggman Impressive! Make it a challenge. I'm sure somebody will post an answer. :D Even better if you could create a website similar to fish's online interpreter.

Question 38

@mbomb007 That might be a tad ambitious for a challenge on this site, not to mention it would probably suffer a lot from being really broad. I don't think I will post that, but feel free to do it yourself if you think you have a good way of presenting it. Also, I believe Timwi created a C# ide for hexagony, although I've never used it because I haven't bothered with mono.

Question 39

@mbomb007 The ide lives here, by the way, forgot to link it last time.

Question 40

Python 2, 34 bytes

Python, using recursion... here comes a StackOverflow!

def f(i,j):print i;f(j,i+j)
f(1,1)

Question 41

><> - 15 characters

0:nao1v
a+@:n:<o

Question 42

Though you can shorten it to 0:nao1v LF a+@:n:<o if you want to. Gives 15 :) In fact, this also makes the output slightly more readable...

Question 43

13 chars: 01r:nao$:@+$r

Question 44

J, 10 chars

Using built-in calculation of Taylor series coefficients so maybe little cheaty. Learned it here.

 (%-.-*:)t.
 (%-.-*:)t. 0 1 2 3 4 5 10 100
0 1 1 2 3 5 55 354224848179261915075

Question 45

@aditsu (q:^-^:p) 6 is 64 729 where p is even. J is probably good for what it does riddles. :)

Question 46

Even better: (<:^-^:>) 4 is 81 and <:^-^:> 4 is 53.5982.

Question 47

The emoji demonstrated here is what all J code should strive towards. On a side note, another alternative is +/@:!&i.- using 9 bytes.

Question 48

@miles Very nice! You should post it as it is entirely different from mine.

Question 49

COW, 108

 MoO moO MoO mOo MOO OOM MMM moO moO
 MMM mOo mOo moO MMM mOo MMM moO moO
 MOO MOo mOo MoO moO moo mOo mOo moo

Question 50

Jelly, 3 bytes

+¡1

Try it online!

How it works

+¡1 Niladic link. No implicit input.
 Since the link doesn't start with a nilad, the argument 0 is used.
 1 Yield 1.
+ Add the left and right argument.
 ¡ For reasons‡, read a number n from STDIN.
 Repeatedly call the dyadic link +, updating the right argument with
 the value of the left one, and the left one with the return value.

^‡ ¡ peeks at the two links to the left. Since there is only one, it has to be the body of the loop. Therefore, a number is read from input. Since there are no command-line arguments, that number is read from STDIN.

Question 51

Hexagony, 6 bytes

1.}=+!

Ungolfed:

 1 .
 } = +
 ! .

It prints the Fibonacci sequence without any separator.

Question 52

This has the minor problem that it doesn't print any separator between the numbers. This isn't entirely well specified in the challenge though. (And I'm really happy someone is using Hexagony. :))

Question 53

Golfscript - single number - 12/11/10

12 chars for taking input from stdin:

~0 1@{.@+}*;

11 chars for input already on the stack:

0 1@{.@+}*;

10 chars for further defining 1 as the 0th Fibonacci number:

1.@{.@+}*;

Question 54

The option is "Calculates, given n, the nth Fibonacci number". So ditch the ~ and you have 11 chars which take n on the stack and leave F_n on the stack.

Question 55

Prelude, 12 bytes

One of the few challenges where Prelude is actually fairly competitive:

1(v!v)
 ^+^

This requires the Python interpreter which prints values as decimal numbers instead of characters.

Explanation

In Prelude, all lines are executed in parallel, with the instruction pointer traversing columns of the program. Each line has its own stack which is initialised to zero.

1(v!v)
 ^+^
| Push a 1 onto the first stack.
 | Start a loop from here to the closing ).
 | Copy the top value from the first stack to the second and vice-versa.
 | Print the value on the first stack, add the top two numbers on the second stack.
 | Copy the top value from the first stack to the second and vice-versa.

The loop repeats forever, because the first stack will never have a 0 on top.

Note that this starts the Fibonacci sequence from 0.

Question 56

Ruby, (削除) 29 27 25 (削除ここまで) 24 bytes

p a=b=1;loop{b=a+a=p(b)}

Edit: made it an infinite loop. ;)

Question 57

did anyone notice b=a+a=b is a palindrome? :)

Question 58

yes st0le did :)

Question 59

I know I'm late to the party, but can someone explain how the b=a+a=b part works? Can't seem to wrap my head around it.

Question 60

@GigaWatt, Think of it this way, Instructions are executed left to right...so newb=olda+(a=oldb)

Question 61

On second thought: 22 bytes

Question 62

Mathematica, 9 chars

Fibonacci

If built-in functions are not allowed, here's an explicit solution:

Mathematica, ~~(削除) 33 (削除ここまで)~~ ~~(削除) 32 (削除ここまで)~~31 chars

#&@@Nest[{+##,#}&@@#&,{0,1},#]&

Question 63

#&@@Nest[{#+#2,#}&@@#&,{0,1},#]& 32 chars.

Question 64

@chyanog 31: #&@@Nest[{+##,#}&@@#&,{0,1},#]&

score 95 · Accepted Answer · 2011-01-28 02:26:26Z

95

\$\begingroup\$

Brainfuck, 22 bytes

+>++[-<<[->+>+<<]>>>+]

Generates the Fibonacci sequence gradually moving across the memory tape.

Share

Improve this answer

edited Apr 25, 2021 at 1:24

hyperneutrino's user avatar

hyperneutrino ♦

42.7k5 gold badges72 silver badges226 bronze badges

answered Jan 28, 2011 at 2:26

R. Martinho Fernandes's user avatar

R. Martinho Fernandes R. Martinho Fernandes

2,4151 gold badge18 silver badges17 bronze badges

\$\endgroup\$

8

6

\$\begingroup\$ Beautiful! Litterally beautiful! Or perhaps not... anyways +1 for this :) \$\endgroup\$

Per Hornshøj-Schierbeck
– Per Hornshøj-Schierbeck

2011年08月18日 11:20:51 +00:00
Commented Aug 18, 2011 at 11:20
3

\$\begingroup\$ This is 3.344 or 4 bytes in compressed brainfuck. (6 ln(22)) / ln(256) \$\endgroup\$

Will Sherwood
– Will Sherwood

2016年02月02日 05:12:10 +00:00
Commented Feb 2, 2016 at 5:12
36

\$\begingroup\$ 16 bytes: +[[<+>->+>+<<]>] \$\endgroup\$

primo
– primo

2016年09月12日 05:19:16 +00:00
Commented Sep 12, 2016 at 5:19
13

\$\begingroup\$ 14 bytes: +[.[>+>+<<-]>] \$\endgroup\$

Charlim
– Charlim

2019年02月10日 20:38:41 +00:00
Commented Feb 10, 2019 at 20:38
4

\$\begingroup\$ @Stefnotch of course, the shorter one is destructive. The solution above terminates with the fibonacci sequence on the tape, which is what the 16 byte solution also does. \$\endgroup\$

primo
– primo

2019年02月13日 01:30:16 +00:00
Commented Feb 13, 2019 at 1:30

| Show 3 more comments

Fibonacci function or sequence

Leaderboard

354 Answers 354

Brainfuck, 22 bytes

Haskell, (削除) 17 (削除ここまで) (削除) 15 (削除ここまで) 14 bytes

Perl 6, 10 chars:

C# 4, 58 bytes

GolfScript, 12

Hexagony, (削除) 18 (削除ここまで) (削除) 14 (削除ここまで) 12

Explanation

Python 2, 34 bytes

><> - 15 characters

J, 10 chars

COW, 108

Jelly, 3 bytes

How it works

Hexagony, 6 bytes

Golfscript - single number - 12/11/10

Prelude, 12 bytes

Explanation

Ruby, (削除) 29 27 25 (削除ここまで) 24 bytes

DC (20 bytes)

TI-BASIC, 11

K - 12

Julia, 18 bytes

Java, 55

05AB1E, 7 bytes

Dodos, 26 bytes

How it works

Whispers v3, 35 bytes

TypeScript's type system, (削除) 193 (削除ここまで) (削除) 188 (削除ここまで) 186 bytes

Trianguish, (削除) 152 (削除ここまで) 135 bytes

Perl 5, (削除) 36 (削除ここまで) (削除) 35 (削除ここまで) (削除) 33 (削除ここまで) 32 bytes

Perl 5 -p, 28 bytes

K - 8 bytes

Explanation

How to use

Ruby, 25 chars

FAC: Functional APL, 4 characters (!!)

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Linked

Related

Hot Network Questions

Perl 5 `-p`, 28 bytes