First-n Fibonacci sequence elements [duplicate]

Question

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)

Answer 1

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.

Answer 2

Haskell (26)

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.

Answer 3

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.

Answer 4

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]

Answer 5

Perl, 50 characters

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

Answer 6

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

Answer 7

Python(55)

a,b=0,1

for i in range(int(input())):a,b=b,a+b;print(b)

Answer 8

Perl, 29 28 bytes

perl -E'say$b+=$;=$b-$;for-pop..--$;' 8
1
1
2
3
5
8
13
21

Explanation

This is based on the classic $b += $a = $b-$a recurrence which works as follows:

• At the start of each loop $a contains F(n-2) and $b contains F(n)
• After $a = $b-$a $a contains F(n-1)
• After $b += $a $b contains F(n+1)

The problem here is the initialization. The classical way is $b += $a = $b-$a || 1 but then the sequence goes 1 2 3 5 ...

By extending the fibonacci sequence to the left:

... 5 -3 2 -1 1 0 1 1 2 3 5 ...

you see that the proper starting point is $a = -1 and $b = 0. Initializing $a can be combined with setting up the loop

Finally replace $a by $; to get rid of the space before the for

Answer 9

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.

Answer 10

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

Answer 11

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))))))

Answer 12

Haskell

fib n = take n f
f = 0:1:zipWith (+) f (tail f)

Proof that it works.

Answer 13

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~ xtakes 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.

Answer 14

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.

Answer 15

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

Answer 16

Python 2, 38 Bytes

An improvement on a previously posted solution:

a=b=1
exec'print a;a,b=b,a+b;'*input()

This uses exec and string multiplication to avoid loops.

Python 3, 46 Bytes

Not quite as efficient in Python 3:

a=b=1
exec('print(a);a,b=b,a+b;'*int(input()))

Answer 17

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);'*$_)}.

Answer 18

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.

Answer 19

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.

Answer 20

FALSE, 28 bytes

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

Answer 21

JavaScript (V8), 37 bytes

f=(n,i=0,j=1)=>--n?i+' '+f(n,j,i+j):i

Try it online!

Answer 22

Python (38 bytes)

a,b=0,1;exec("print(a);a,b=b,a+b;"*31)

the factor of multiplication prints the first N

Edit: First n from stdin (48 bytes)

a,b=0,1;exec("print(a);a,b=b,a+b;"*int(input()))

Answer 23

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]);
}

Answer 24

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)}

Answer 25

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 

Answer 26

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)

Answer 27

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.

Answer 28

Q 24

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

First n fibonacci numbers

Answer 29

Lua, 85 bytes

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

function f(x)
    return (x<3) and 1 or f(x-1)+f(x-2)
end
for i=1,io.read() do
    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.

Answer 30

FALSE, 20 characters

^1@[1-$][@2ø+$.\9,]#

Input should be on the stack before running this.