# First-n Fibonacci sequence elements [duplicate]

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. Commented Jan 17, 2012 at 20:52
• 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). Commented Jan 17, 2012 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}]]. Commented Jan 17, 2012 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). Commented Jan 18, 2012 at 3:33
• I realize this is quite an old challenge at this point, but note that you've accepted an answer which is not the shortest. Since this is a code golf competition, the shortest answer should be the one that's marked accepted. Commented Feb 12, 2016 at 0:21

## 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. Commented Jan 18, 2012 at 8:35
• Love it! This is a great example of where the undefined behavior of the ordering of the two instances of --n in the same expression is irrelevant. Brilliant! Commented Sep 9, 2019 at 21:15
• By the way, I think your 4 there should actually be a 3. As currently written with the <4, the sequence produced is 1, 1, 1, 2, 3, 5, 8... That's one too many 1's. Commented Sep 9, 2019 at 21:25
• Additionally, if you want to handle the zeroth element of the sequence correctly, you could add 2 characters and change the code to return n<3?n>0:f(--n)+f(--n); Commented Sep 9, 2019 at 21:29

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

f=(takes)
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.
• It literally took me about half an hour to understand what is going on here, and the s is so elegant, I don't know how anyone would think of a solution like that! What I did not know is that you can use s again while defining s. (I'm still a beginner=) Commented Mar 6, 2016 at 9:53

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. Commented Jan 18, 2012 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. Commented Jan 18, 2012 at 7:38
• 70 chars, 1 line, to define function. + 4 +crlf to invoke. Pretty good! Commented Jan 18, 2012 at 17:53

## 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]


## 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. Commented Jan 18, 2012 at 17:54 # Python(55) a,b=0,1 for i in range(int(input())):a,b=b,a+b;print(b)  # 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

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)? ;) Commented Jan 17, 2012 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)? Commented Jan 18, 2012 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) Commented Jan 19, 2012 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. :) Commented Jan 19, 2012 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. Commented Jan 19, 2012 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" :) Commented May 13, 2012 at 16:53
• You can shave 2 chars off by getting rid of the parentheses around 2**i. ** have higher precedence than * Commented May 13, 2012 at 17:05
• The second term in binet's formula starts small and only gets smaller. You can leave it out completely and just round the result of the first term to the nearest integer instead (or add 0.5 and round down) Commented Mar 6, 2016 at 19:18

# 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 Commented May 2, 2012 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~ 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.

## 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.

• This is the first TI-BASIC solution I've ever seen here that wasn't by me :) +1 Commented Jan 10, 2014 at 0:06
• Also, note for other people that newlines are not counted here because they can be removed. Commented Jan 10, 2014 at 0:13
• I just got a TI-92 big-giant-qwerty-keyboard calculator. Thanks for this one. Commented Sep 2, 2014 at 13:49

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

• Is the box character ⎕ part of APL or a missing-glyph? Commented Sep 2, 2014 at 13:48
• @WarrenP: If you mean the 4th character from the left, that's called a 'quad' and it's supposed to look like that. There should be only one box. Commented Sep 3, 2014 at 7:23

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

• By switching to Python 2 you can save 9 bytes: Try It Online! You probably can add the Python 2 version to your answer. Commented Feb 6, 2020 at 0:23
• @Stephen Good point! Updated. Commented Feb 7, 2020 at 1: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);'*$_)}.

## 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 Commented Jun 1, 2012 at 21:34

# 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.

• Does... does main take four arguments?
– cat
Commented Mar 6, 2016 at 20:20
• It takes as many as you give it. In this case it's just (ab)used to define a few variables that are used later :) Commented Mar 7, 2016 at 12:31

# FALSE, 28 bytes

0 1- 1 10[$][@@$@+$." "@1-]#  • You can generate -1 using 1_ rather than 0 1 - Commented Jan 31, 2018 at 14:12 # JavaScript (V8), 37 bytes f=(n,i=0,j=1)=>--n?i+' '+f(n,j,i+j):i  Try it online! # 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()))  • Welcome to Code-Golf! and nice first answer! It seems like your answer prints the first 31 elements of the Fibonacci Sequence, instead of the first n. Check out this Python answer and see if you can shorten your answer any more! Again, welcome! Commented May 28 at 19:08 • thanks for the improvement ! – stwq Commented May 30 at 3:53 # 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]); }  ## 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  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 # 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. # FALSE, 20 characters ^1@[1-$][@2ø+\$.\9,]#
`

Input should be on the stack before running this.