Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 24 down vote favorite
2

Write the shortest code that either:

  • Generates a Fibonacci sequence (either in standard output, or as a stream)
  • Calculates, given n, the nth Fibonacci number

(I gave both options in case one is easier to do in your chosen language than the other.)

Edit: for the avoidance of doubt, a stream or sequence is infinite in length (I'm sorry that there are a couple of non-functional programmers who answered this question in a cheeky way). 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 minumum) has to be supported.

share|improve this question
Maybe no need of cloning SO questions? stackoverflow.com/questions/232861/fibonacci-code-golf – Nakilon Jan 28 '11 at 2:41
1  
@Nakilon: Well, that question is dead already (I know this, because my answer was the accepted one :-P). I wanted to see if anyone could improve upon the 13-character GolfScript solution. – Chris Jester-Young♦ Jan 28 '11 at 2:45
To make answers comparable, there schould be just one form of the question, IMHO. – user unknown Apr 12 '11 at 1:29

53 Answers

1 2
up vote 19 down vote accepted

GolfScript, 12

Now, just 12 characters!

1.{[email protected]+.}do
share|improve this answer
+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 – Chris Jester-Young♦ Jan 29 '11 at 23:54
1  
I love a challenge. Done! ;-) – jtjacques Jan 30 '11 at 0:10
Nice, you win. At least, until someone makes something even shorter (if that's even possible). :-P – Chris Jester-Young♦ Jan 30 '11 at 0:33
1  
that definition is almost as short as the name 'Fibonacci' itself! +1 – agent-j Jun 18 '12 at 18:21
up vote 3 down vote

GolfScript, 13 chars

2,~{..p@+.}do

(My answer from a previous Stack Overflow question.)

share|improve this answer
up vote 1 down vote

Python, 36

f=lambda x:x>1and f(x-1)+f(x-2)or x
share|improve this answer
up vote 27 down vote

Haskell, 17 15 14 chars

f=0:scanl(+)1f
share|improve this answer
4  
Why not cut two spaces to f=0:scanl(+)1 f? – R. Martinho Fernandes Jan 28 '11 at 2:27
@Martinho: Edited, thanks. – Anon. Jan 28 '11 at 2:54
Wow, that's even shorter than the usual f@(_:x)=0:1:zipWith(+)f x! Have to remember it. – FUZxxl Feb 11 '11 at 21:10
You may even strip another space: f=0:scanl(+)1f. – FUZxxl Feb 12 '11 at 17:38
up vote 2 down vote

Python

a,b,n=0,1,10
while n:a,b,n=b,a+b,n-1;print b
share|improve this answer
1  
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
up vote 26 down vote

BrainFuck, 22 strokes

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

Generates the Fibonacci sequence gradually moving across the memory tape.

share|improve this answer
1  
Beautiful! Litterally beautiful! Or perhaps not... anyways +1 for this :) – Per Hornshøj-Schierbeck Aug 18 '11 at 11:20
up vote 5 down vote

Ruby

29 27 25 Chars

p 1,a=b=1;loop{p b=a+a=b}

Edit: made it an infinite loop. ;)

share|improve this answer
8  
did anyone notice b=a+a=b is a palindrome? :) – st0le Jan 28 '11 at 11:11
yes st0le did :) – gnibbler♦ Feb 1 '11 at 12:24
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. – GigaWatt Feb 7 '12 at 17:58
1  
@GigaWatt, Think of it this way, Instructions are executed left to right...so newb=olda+(a=oldb) – st0le Feb 8 '12 at 5:19
you can save 2 chars by using loop: p 1,a=b=1;loop{p b=a+a=b} – padde Jun 15 '12 at 13:01
show 1 more comment
up vote 5 down vote

Python, 34

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

def f(i,j):print i;f(j,i+j)
f(1,1)
share|improve this answer
up vote 2 down vote

Windows PowerShell – 34

$a=$b=1
for(){$a
$a,$b=$b,($a+$b)}
share|improve this answer
up vote 2 down vote

Bash 100

This is a very slow, but hey no performance penalty. First line needed.

#!/bin/bash
if [ $1 -lt 2 ]; then
echo $1; exit; fi
expr `$0 \`expr $1 - 1\`` + `$0 \`expr $1 - 2\``
share|improve this answer
More a question: You don't need a shebang, do you? See ruby, python and xy-script. – user unknown Apr 12 '11 at 1:39
(($1<2))&& echo $1 && exit;v=$1;p=$0;echo $(($($p $((v-1)))+$($p $((v-2))))) 77 chars with the same approach, just different syntax and a bit faster – user unknown Apr 12 '11 at 1:50
up vote 2 down vote

J - 20

First n terms:

(+/@(2&{.),])^:n i.2
share|improve this answer
up vote 3 down vote

DC (20 bytes)

As a bonus, it's even obfuscated ;)

zzr[dsb+lbrplax]dsax

EDIT: I may point out that it prints all the numbers in the fibonacci sequence, if you wait long enough.

share|improve this answer
5  
I wouldn't call it obfuscated -- obfuscated code is supposed to be difficult to understand, and as far as dc goes the code here is completely straightforward. – Nabb Feb 6 '11 at 8:17
up vote 1 down vote

Python 33

n=1
t=2
while 1:
 y=n+t
 n=t
 t=y
share|improve this answer
up vote 6 down vote

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.@{.@+}*;
share|improve this answer
1  
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. – Peter Taylor Mar 31 '11 at 19:29
up vote 0 down vote

Since I see no perl responses I throw my answer out:
($i, $a, $b, $s) = ((0) x 2, 1, $ARGV[0]); while($s >= $i){( $a, $b ) = ( $b, $a+$b ); $i++; print $b . "\n";}

share|improve this answer
1. When participating in a [code-golf] thread, please golf your solution! At a minimum, that means squeezing out all the unnecessary spaces, using single-character variable names, etc. 2. Why "0" rather than 0? – Chris Jester-Young♦ Mar 17 '11 at 16:26
How about something like these 47 characters: $b=1; for(;;) {($_,$b)=($_+$b,$_);print "$_ ";} – piCookie May 28 '11 at 21:14
up vote 2 down vote

PHP - 109 97 88 49 characters

<?for($a=$b++;;$b+=$a=$b-$a){$s+=$b%2*$b;echo$a;}
share|improve this answer
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
up vote 8 down vote

<>< - 15 characters

0:nao1v LF a+@:n:<o
share|improve this answer
Yay for ><>! I always give ><> answers +1, so no exception :) – tomsmeding Mar 18 at 6: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... – tomsmeding Mar 18 at 7:28
up vote 1 down vote

Javascript (41 39)

function f(a,b){alert(a);f(b,a+b)}(0,1)
share|improve this answer
I don't think the function without the parenthesis is still valid. – dystroy Apr 8 at 16:22
up vote 5 down vote

Ruby, 25 chars

st0le's answer shortened.

p 1,a=b=1;loop{p b=a+a=b}
share|improve this answer
4  
Actually you can shorten it even further using a=b=1;loop{p a;b=a+a=b} – Ventero Apr 4 '11 at 12:20
up vote 2 down vote

bc, 36 chars

r=0;l=1;while(i++<99){r+=l;l+=r;r;l}
share|improve this answer
up vote 3 down vote

bash pur, 60 chars

r=0;l=1;for i in {1..40};do((r+=l));((l+=r));echo $r $l;done
share|improve this answer
up vote 4 down vote

K - 12

Calculates the n and n-1 Fibonacci number.

{x(|+\)/0 1}

Just the nth Fibonacci number.

{*x(|+\)/0 1}
share|improve this answer
+1 Not bad! If you could shrink it just one character (and provide me a way to test it), I'll accept your answer. :-) – Chris Jester-Young♦ Apr 4 '11 at 15:47
The only way to shrink it would be to replace the function with a call to a known number: n(|+\)/0 1 Test it using this interpreter. – isawdrones Apr 4 '11 at 16:04
up vote 2 down vote

Common Lisp, 48 Chars

(defun f(n)(if(< n 2) n(+(f(decf n))(f(1- n)))))
share|improve this answer
Is left-to-right evaluation order guaranteed in CL? If not, your solution won't work. (There is no such guarantee in Scheme, and many implementations are right-to-left.) – Chris Jester-Young♦ Apr 5 '11 at 2:12
Left-to-right is in the standard so since these are all built-in functions it is reliable. (Macros can of course do stupid things :-) – Dr. Pain Apr 29 '11 at 18:00
1  
+1 for clisp use – rmckenzie Jun 3 '11 at 15:37
up vote 1 down vote

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)
share|improve this answer
up vote 1 down vote

Scala, 52 chars:

def f(a:Int,b:Int):Int={println(a);f(b,a+b)};f(0,1)
share|improve this answer
up vote 1 down vote

CHIP 8

Not so short but displays the fibonacci sequence on screen:

00E06600690060006101221E3900120E8200801081206F00810489F0120A6500830064F083428336833683368336F32900E0D56575088300640F8342F329D56500EE

without displaying on screen:

00E06000610182008010812081041206
share|improve this answer
up vote 1 down vote

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.

share|improve this answer
1  
actually it's O(log n) since pow has that complexity... – JBernardo Jul 10 '11 at 2:03
1  
@JBernado and even bigger since pow for bigint is more complicated story. – shabunc Aug 19 '11 at 8:49
up vote 0 down vote

Python --

c,f,l=70,0,1;
s='1 ';
for z in range(c):
    n=f+l; f=l; l=n;
    s+=str(n)+' ';
print s;
share|improve this answer
1  
Welcome to CodeGolf.SE! It is customary to put your implementation language and (for code golf, the character count) at the top of you answer, and to use the Markdown facilities to properly format your answer. I'll take care of the code block for you and label this as python. BTW, George's UserScript claims your solution is 89 characters. – dmckee♦ Jun 4 '11 at 17:29
1  
Four suggestions from another python golfer - you don't need the ";" character, the newline serves the same purpose. you can get away with one space not four when you indent your loop. you don't need the spaces or multiple newlines in your loop, n=f+l;f=l;l=n;s+=str(n)+' ' as one line would work just as well. Good luck, I hope to see you around CG.SE! – rmckenzie Jun 4 '11 at 17:35
up vote 10 down vote

C# 4:

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);}
share|improve this answer
2  
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; – Peter Taylor Aug 18 '11 at 11:39
@Peter: Thanks, will edit when I get some time. – Jon Skeet Aug 18 '11 at 12:01
Your single value version is as long as my recursive lambda expression answer...nice! – Andrew Gray Apr 9 at 17:29
up vote 0 down vote

Java, 55

I can't compete with the conciseness of most languages here, but I can offer a substantially different way to calculate the n-th number:

Math.round(Math.pow((Math.sqrt(5)+1)/2,n)/Math.sqrt(5))

n is the input (int or long).

share|improve this answer
1 2

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.