# code-golf: First-n Fibonacci sequence elements

There is a well known question here that asks for a short (least characters) fibonacci sequence generator.

I would like to know if someone can generate the first N elements only, of the fibonacci sequence, in very short space. I am trying to do it in python, but I'm interested in any short answer, in any language. Function F(N) generates the first N elements of the sequence, either returns them as the return of the function or prints them.

Interestingly it seems that the code-golf answers start with `1 1 2`, instead of `0 1 1 2`. Is that a convention in code-golf or programming-in-general? (Wikipedia says the fibonacci sequence starts with zero.).

Python Sample (First 5 Elements):

``````def f(i,j,n):
if n>0:
print i;
f(j,i+j,n-1)
f(1,1,5)
``````
-
I think this is too similar to the linked question. Most solutions there can easily be modified to handle the first-n case. – hammar Jan 17 '12 at 20:52
In the case of Python, the interesting thing is that I need four lines of code, and two levels of indentation in my sample. I suspect there is a one liner in python, but I can't find it. – Warren P Jan 17 '12 at 20:56
Everywhere I've seen, the base cases are defined as `F_0 = 0, F_1 = 1` or equivalently `F_1 = 1, F_2 = 1`. The difference is whether you want to start the sequence at index 0 (more common in programming) or 1 (more common in math). – hammar Jan 17 '12 at 21:19
And defining `F_0 = 0, F_1 = 1` has a definite benefit in simplicity with the matrix representation `[[1 1][1 0]]^n = [[F_{n+1} F_n][F_n F_{n-1}]]`. – Peter Taylor Jan 17 '12 at 23:36
@Peter: Now that a good reason to prefer one to the other (I'd long preferred 0, 1 on esthetic grounds, but don't believe those to be pressing in and of themselves). – dmckee Jan 18 '12 at 3:33

## C

Didn't bother counting, but here's a fun example:

``````f(n){return n<4?1:f(--n)+f(--n);}
main(a,b){for(scanf("%d",&b);a++<=b;printf("%d ",f(a)));}
``````

Proof it works.

I'm quite proud of this: I got bored, so I rearranged my code (with a few small additions) to make it where each line represents a value in the Fibonacci sequence.

``````                         #                                // 1
f                                // 1
//                               // 2
(n)                               // 3
{/**/                              // 5
return n                            // 8
<2 ? 1:f(--n)                         // 13
+f(--n); } main(a, b)                     // 21
{a = 0, b = 0;scanf("%d",&b); for(              // 34
;a < b; a+=1) { int res = f(a); printf("%d ", res); } }   // 55
``````

Proof it works.

-
Nice. 90 chars (without newline). Save 2 bytes: `a++<=b`-> `a++-b` and `return--n<3?1:f(n)+f(n-1)`. Plus you can avoid `scanf` if you require n to be in `argc`. – ugoren Jan 18 '12 at 8:35
+1 for massive style. It's kind of a code-haiku. – Warren P Jan 18 '12 at 17:54

## GolfScript, 16 characters

``````~0 1@{.2\$+}*;;]`
``````

Example output:

``````\$ ruby golfscript.rb ~/Code/golf/fib.gs <<< "12"
[0 1 1 2 3 5 8 13 21 34 55 89]
``````
-

Here's a one-liner Python. It uses floating-point, so there may be some `n` for which it is no longer accurate.

``````F=lambda n:' '.join('%d'%(((1+5**.5)/2)**i/5**.5+.5)for i in range(n))
``````

`F(n)` returns a string containing the first `n` Fibonacci numbers separated by spaces.

-
 I was thinking of doing this, but thought it would be too long. I didn't think about using flooring. Very nice. – Kris Harper Jan 18 '12 at 0:04 Ah, Binet's formula. I also used it & it's accurate, at least till the 59th fibonacci number if you count 0 as the first. After that the numbers become too big & it starts using exponents. – elssar Jan 18 '12 at 7:38 70 chars, 1 line, to define function. + 4 +crlf to invoke. Pretty good! – Warren P Jan 18 '12 at 17:53

## Perl, 50 characters

``````sub f{(\$a,\$b,\$c)=@_;\$c--&&say(\$a)&&f(\$b,\$a+\$b,\$c)}
``````
-

### Scala 71:

``````def f(c:Int,a:Int=0,b:Int=1):Unit={println(a);if(c>0)f(c-1,b,a+b)};f(9)
``````

prints

``````0
1
1
2
3
5
8
13
21
34
``````
-
 Cool. I haven't even played with Scala yet. I will try it tonight at home. – Warren P Jan 18 '12 at 17:54

I can give you a two line Python solution. This will return them as a list.

``````f = lambda n: 1 if n < 2 else f(n-1) + f(n-2)
g = lambda m: map(f, range(0,m))

print g(5)
``````

You could have it print them out by adding another map to make them strings and then adding a join, but that just seems unnecessary to me.

Unfortunately I don't know how to put a recursive lambda into `map`, so I'm stuck at two lines.

-
 What's it return for `g(100)`? ;) – GigaWatt Jan 17 '12 at 22:13 @GigaWatt Heh, OP never said it had to be reasonable. Is the asymptotic running time something like O(n(1.62)^n)? – Kris Harper Jan 18 '12 at 0:11 Here's one way you can (kind of) do this. Note that `f(n)` with `n<=0` returns integers, and `n>0` returns lists, so.. maybe it isn't ideal: `f = lambda n: map(f, (-x for x in range(0, n))) if n > 0 else -n if n > -2 else f(n+1) + f(n+2)` – Dillon Cower Jan 19 '12 at 2:48 By the way, you missed the first `0` in your answer. Changing `f` to return `n if n < 2` is one workaround. :) – Dillon Cower Jan 19 '12 at 2:51 @DC I like your solution. Pretty creative. Yeah, I made mine start with 1, 1 because that's how I always learned it. I figured changing it was easy enough. – Kris Harper Jan 19 '12 at 12:07

## Python (78 chars)

I used Binet's formula to calculate the fibonacci numbers -

[(1+sqrt(5))^n-(1-sqrt(5)^n]/[(2^n)sqrt(5)]

It's not as small some of the other answers here, but boy it's fast

``````n=input()
i=1
x=5**0.5
while i<=n:
print ((1+x)**i-(1-x)**i)/((2**i)*x)
i+=1
``````
-
 Python (12 chars): `print"11235"` :) – Joel Cornett May 13 '12 at 16:53 You can shave 2 chars off by getting rid of the parentheses around `2**i`. `**` have higher precedence than `*` – Joel Cornett May 13 '12 at 17:05

# Scheme

This is optimized using tail-recursion:

``````(define (fib n)
(let fib ([n n] [a 0] [b 1])
(if (zero? n) (list a)
(cons a (fib (- n 1) b (+ a b))))))
``````
-

``````fib n = take n f
f = 0:1:zipWith (+) f (tail f)
``````
-
 You can make it one function using where – Łukasz Niemier May 2 '12 at 8:30

## J, 25 characters

I realise that J solutions are probably not what you're after, but here's one anyway. :-)

``````0 1(],+/&(_2&{.))@[&0~2-~
``````

Usage:

``````    0 1(],+/&(_2&{.))@[&0~2-~ 6
0 1 1 2 3 5
0 1(],+/&(_2&{.))@[&0~2-~ 10
0 1 1 2 3 5 8 13 21 34
``````

How it works:

Starting from the right (because J programs are read from right to left),

`2-~ 6` The `~` operator reverses the argument to the verb so this is the same as `6-2`

Ignoring the section in brackets for now, `0 1(...)@[&0~ x`takes the verb in the brackets and executes it `x` times using the list `0 1` as its input - `~` again reverses the arguments here, giving `x (...)@[&0 ] 0 1`, meaning I can keep the input at the end of the function.

Within the brackets is a fork `],+/&(_2&{.)` which is made up of three verbs - `]`, `,` and `+/&(_2&{.)`.

A fork takes three verbs `a b c` and uses them like this: `(x a y) b (x c y)` where `x` and `y` are the arguments to the fork. The `,` is the centre verb in this fork and joins the results of `x ] y` and `x +/&(_2&{.) y` together.

`]` returns the left argument unaltered so `x ] y` evaluates to `x`.

`+/&(_2&{.)` takes the last two items from the given list `(_2&{.)` - in this case `0 1` - and then adds them together `+/` (the `&`s just act as glue).

Once the verb has operated once the result is fed back in for the next run, generating the sequence.

-

# Powershell - 35 characters

Powershell accepts pipeline input, so I'm of the belief that the `n |` in `n | <mycode>` shouldn't be against my count, but instead is just a part of initiating a "function" in the language.

The first solution assumes we start at 0:

``````%{for(\$2=1;\$_--){(\$2=(\$1+=\$2)-\$2)}}
``````

The second solution assumes we can start at 1:

``````%{for(\$2=1;\$_--){(\$1=(\$2+=\$1)-\$1)}}
``````

Example invocation: `5 | %{for(\$2=1;\$_--){(\$1=(\$2+=\$1)-\$1)}}`

Yields:

``````1
1
2
3
5
``````

Interestingly, attempts to avoid the overhead of the `for()` loop resulted in the same character count: `%{\$2=1;iex('(\$1=(\$2+=\$1)-\$1);'*\$_)}`.

-

## Python, 43 chars

Here are three fundamentally different one-liners that don't use Binet's formula.

``````f=lambda n:reduce(lambda(r,a,b),c:(r+[b],a+b,a),'.'*n,([],1,0))[0]
f=lambda n:map(lambda x:x.append(x[-1]+x[-2])or x,[[0,1]]*n)[0]
def f(n):a=0;b=1;exec'print a;a,b=b,a+b;'*n
``````

I've never abused `reduce` so badly.

-
 +1 for `reduce` abuse – Warren P Jun 1 '12 at 21:34

# C99, 58 characters

The following function fills an array of integers with the first `n` values from the Fibonacci sequence starting with 0.

``````void f(int*a,int n){for(int p=0,q=1;n--;q+=*a++)*a=p,p=q;}
``````

Test harness, taking `n` as a command line argument:

``````#include <stdlib.h>
#include <stdio.h>
int main(int argc, char *argv[]) {
int n = (argc > 1) ? atoi(argv[1]) : 1;
int a[n];
f(a, n);
for (int i = 0; i < n; ++i)
printf("%d\n", a[i]);
}
``````
-

FALSE

``````0 1- 1 10[\$][@@\$@+\$." "@1-]#
``````
-

I am learning Lua so I would like to add this language to the pool.

Lua

``````function f(x)
return (x<3) and 1 or f(x-1)+f(x-2)
end
print(f(i))
end
``````

and the whole thing took 85 characters, with the parameter as a command line argument. Another good point is that is easy to read.

-

## CoffeeScript, 48

``````f=(n,i=1,j=1)->(console.log i;f n-1,j,i+j)if n>0
``````

65 in js:

``````function f(n,i,j){if(n>0)console.log(i),f(n-1,(j=j||1),(i||1)+j)}
``````
-

## PHP, 87

``````function f(\$n,\$a=array(0,1)){echo' '.\$a[0];\$n>0?f(--\$n,array(\$a[1],array_sum(\$a))):'';}
``````

Uses `array_sum` and recursive function to generate series.

Eg:

`````` \$ php5 fibo.php 9
0 1 1 2 3 5 8 13 21 34
``````
-

## TI-Basic, 43 characters

``````:1→Y:0→X
:For(N,1,N
:Disp X
:Y→Z
:X+Y→Y
:Z→X
:End
``````

This code can be directly inserted into the main program, or made into a separate program that is referenced by the first.

-

### APL (33)

``````{⍎'⎕','←0,1',⍨'←A,+/¯2↑A'⍴⍨9×⍵-2}
``````

Usage:

``````   {⍎'⎕','←0,1',⍨'←A,+/¯2↑A'⍴⍨9×⍵-2}7
0 1 1 2 3 5 8
``````
-

F#, 123

``````let f n = Seq.unfold(fun (i,j)->Some(i,(j,i+j)))(0,1)|>Seq.take n
f 5|>Seq.iter(fun x->printfn "%i" x)
``````
-

Scala, 65 characters

``````(Seq(1,0)/:(3 to 9)){(s,_)=>s.take(2).sum+:s}.sorted map println
``````

This prints, for example, the first 9 Fibonacci numbers. For a more useable version taking the sequence length from console input, 70 characters are required:

``````(Seq(1,0)/:(3 to readInt)){(s,_)=>s.take(2).sum+:s}.sorted map println
``````

Beware the use of a Range limits this to Int values.

-

## Q 24

``````f:{{x,sum -2#x}/[x;0 1]}
``````

First n fibonacci numbers

-

Surprisingly, this is only one character longer than the J solution.

```f=(`take`s)
s=0:scanl(+)1s
```

I shave off a few characters by:

1. Using `take` as a binary operator;
2. Using `scanl` instead of the verbose `zipWith`.
-

# dc, 32 characters:

This will actually always show the two first 1's, so the function only work as expected for N >= 2.

``````?2-sn1df[dsa+plarln1-dsn0<q]dsqx
``````

# C, 75 characters:

Not as cool as the accepted answer, but shorter and way faster:

``````main(n,t,j,i){j=0,i=scanf("%d",&n);while(n--)t=i,i=j,printf("%d\n",j+=t);}
``````
Extra:

# CL, 64 characters:

One of my most used bookmarks this semester has an interesting example which is shorter than many some of the other ones here, and it's just a straight-forward invocation of the `loop` macro -- basically just one statement! Stripped it for all the whitespace I could:

``````(loop repeat n for x = 0 then y and y = 1 then(+ x y)collect y)
``````

Quite short, and nice and readable! To read input, `n` (including surrounding whitespaces) can be replaced with `(read)`, adding 3 characters.

-