Code Chess: Fibonacci Sequence

Question

Building upon the proven success of Code Golf, I would like to introduce Code Chess.

Unlike Code Golf, which strives for concision, Code Chess will strive for cleverness.

Can you create a clever or unexpected Fibonacci generator?

Your code must print or return either the n^th Fibonacci number or the first n Fibonacci numbers.

Answer 1

C#

Who said constructors cannot be recursive?

struct FibonacciNumber {
    const int InitialValue = 1;

    public FibonacciNumber(int index) : this(index == 0 ? new FibonacciNumber() : new FibonacciNumber(index - 1)) { }
    public FibonacciNumber(FibonacciNumber previous) : this(previous.Current, previous.previous + previous.Current) { }
    FibonacciNumber(long previous, long current) { this.previous = previous; this.current = current - InitialValue; }

    readonly long previous;
    long current;
    public long Current { get { return current + InitialValue; } }

    public override string ToString() { return Current.ToString(); }
}

Answer 2

int i = 0;
while(true)
{
  Console.WriteLine(i);
  Console.WriteLine(i);
  i = i + 1;
}

It should print the "first n Fibonacci numbers" (and some numbers more :-) ).

Answer 3

I once did this in Word field codes, but I'm not sure how to post it. (Ctrl+C will not copy Word field codes)

EDIT: Here's a screenshot:

Once it gets past 1023341553, Word crashes.

EDIT: I uploaded the original document.

Answer 4

Here's one that uses memoization (a common functional technique) to recursively calculate and cache intermediate values. It uses lambdas and higher order functions to generate the Nth number in the sequence. When you do something like Fib(50) this can make a big difference:

    static long Fib(long number)
    {
        Func<long,long> fib=null;

        fib=Memorize<long,long>(value=>
        {
            if(value==0) return 0;
            if(value==1) return 1;

            return fib(value-1)+fib(value-2);
        });

        return fib(number);
    }

    static Func<T,R> Memorize<T,R>(Func<T,R> lookup)
    {
        Dictionary<T,R> cache=new Dictionary<T,R>();

        Func<T,R> memo=value=>
        {
            R result;
            if(cache.TryGetValue(value,out result)==false)
            {
                result=lookup(value);
                cache.Add(value,result);
            }

            return result;
        };

        return memo;
    }

Answer 5

C#

Just one statement!

Enumerable.Repeat(new List<long>(32){ 1, 1 }, 1)
    .First(fib => Enumerable.Range(0, 32).Aggregate(true, (u1, u2) => { fib.Add(fib.Last() + fib[fib.Count - 2]); return true; }))

Answer 6

As in the fibonacci code golf, i would like to suggest some examples from the haskell webpage.

One from the link above:

f=0:1:zipWith(+)f(tail f)

one with nice code:

fibs = scanl (+) 0 (1:fibs)
fibs = 0 : scanl (+) 1 fibs

and one with good old math:

fib n = round $ phi ** fromIntegral n / sq5
  where
    sq5 = sqrt 5 :: Double
    phi = (1 + sq5) / 2

Answer 7

#!/usr/bin/env python3.1

from urllib.request import urlopen

print ("Please enter which Fibonacci number you wish to compute:", end=" ")
n = int(input())

seq = "A000045"

url = "http://www.research.att.com/~njas/sequences/?q=id%3a" + seq + "&p=1&n=10&fmt=3"
resp = urlopen(url)

values = []

for line in resp:
    if line[:2] in [b'%S', b'%T', b'%U']:
        numbers = line.split(b' ')[-1].split(b',')
        values += [int(val) for val in numbers if val != b'\n']


ordinal = "th"
if (1 <= n%10 <= 3) and not (11 <= n%100 <= 13):
    ordinal = ["st", "nd", "rd"][(n-1)%10]
ordinal = str(n)+ordinal

if n < len(values):
    print ("The", ordinal, "Fibonacci number is", values[n])
else:
    print ("The Internet is incapable of computing the", ordinal, "Fibonacci number yet, please come back later.")       

---

OK, the normal version:

import math

def fib(n):
   sqrt5 = math.sqrt(5)
   return int(round(((sqrt5+1)/2)**n / sqrt5))

Answer 8

Erlang:

Prints n first numbers:

-module(fib).
-export([fib/1]).

fib(C) -> fib(1, 1, C).  
fib(_, _, 0) -> ok;
fib(N, M, C) -> io:fwrite("~p~n", [N]), fib(M, N+M, C-1).

Returns n first numbers

-module(fib).
-export([fib/1]).

fib(C) -> fib(1, 1, [], C).
fib(_, _, A, 0) -> lists:reverse(A);
fib(N, M, A, C) -> fib(M, N+M, [N|A], C-1).

Answer 9

Brainf*ck

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

Hex dump of output:

0101020305080d1522375990e97962db3d18556dc22ff12011314273b528dd05e2e7c9b07929a2cb
6d38a5dd825fe140216182e36548adf5a29739d009d9e2bb9d58f54d428fd1603191c25315687de5
6247a9f0998922abcd7845bd02bfc18041c102c3c5884dd522f719102939629bfd98952dc2efb1a0
51f1423375a81dc5e2a78930b9e9a28b2db8e59d821fa1c0612182a325c8edb5a257f9504999e27b
5dd8350d424f91e07151c213d5e8bda562076970d949226b8df8857d027f

The first n fibonacci numbers modulo 256, where n = 190.

Answer 10

Using Binet's formula (though not the original version rather a slightly altered one) you can calculate the nth fibonacci number directly - no recursion, no iteration:

PHI = (1 + 5**0.5) / 2 # golden ratio

def F(n):
    return int(PHI**n / 5**0.5)

Important to note that due to Loss of Significance you can't calculate really large numbers (dependent on floating point implementation).

Answer 11

void print_fib(int n) {
    int fibs[2];
    fibs[0] = fibs[1] = 1;

    for (int i = 0; i < n; i++) {
        printf("%d\n", fibs[i % 2]);
        fibs[i % 2] += fibs[(i - 1) % 2];
    }
}

Currently does one more calculation than necessary.

Answer 12

MATLAB

function f = fib(n);
if n > 2
    z = [0 1; 1 1]^(n-1)*ones(2, 1);
    f = z(1);
else
    f = 1;
end

Answer 13

In assembler, wrapped into a C/C++ function (compiled with DevStudio 2005):

int Fibonacci (int i)
{
  __asm
  {
    mov eax,0
    mov ebx,1
    mov ecx,i
l1: add eax,ebx
    xchg eax,ebx
    loop l1
  }
}

Answer 14

Here is one in C# which uses the fact that 5f^2 +- 4 is a perfect square if and only if f is a fibonacci number. This one prints a list of fibonacci numbers in sequence.

void PrintFib(int n) {
    if (n < 1) return;

    Dictionary<int, int> squares = new Dictionary<int, int>();

    int count = 1;
    Console.WriteLine("1");

    int i = 1;
    while (count < n) {
        int sqr = i * i;

        int x = -1;

        if ((sqr - 4) % 5 == 0) {
            x = (sqr - 4) / 5;
        }

        if ((sqr + 4) % 5 == 0) {
            x = (sqr + 4) / 5;
        }

        if (squares.ContainsKey(x)) {
            Console.WriteLine(squares[x]);
            count++;
        }

        squares[sqr] = i;
        i++;
    }

Answer 15

Here is another one in C# using the fact that

f(2n) = (2f(n-1) + f(n))* f(n)

f(2n-1) = f(n)^2 + f(n-1)^2.

Gives an O(logn) time algo to find just the nth fibonacci number (and some extra as a side effect), just like the matrix version.

// Computes fib(n) and fib(n-1).
void FibPair(int n, out int Fn, out int Fn_minus_1) {
    Fn = 1;
    Fn_minus_1 = 1;
    if (n <= 2) return;

    int f_n, f_n1;

    if ((n % 2) == 0) {

        FibPair(n / 2, out f_n, out f_n1);
        Fn = (2 * f_n1 + f_n) * f_n;
        Fn_minus_1 = f_n * f_n + f_n1 * f_n1;
        return;
    }

    FibPair((n + 1) / 2, out f_n, out f_n1);

    Fn = f_n * f_n + f_n1 * f_n1;
    Fn_minus_1 = (2 * f_n - f_n1)*f_n1;
}

Answer 16

Scala:

Thanks to scalaz

val fibs = (0,1).iterate[Stream]( i => i._2 -> (i._1 + i._2)).map(_._1) //infinite stream

And so:

fibs.take(10).foreach(println(_))

Or from scratch without the higher-kinded type cleverness:

case class Streamable[A](val start: A) {
  def stream(f : A => A) : Stream[A] = Stream.cons(start, Streamable(f(start)).stream(f))
}
implicit def any2streamable[A](a: A) = new Streamable(a)

val fibs = (0,1).stream( i => i._2 -> (i._1 + i._2)).map(_._1)

Answer 17

Regular expression

(I can't take credit for this thing of beauty - see source: perlmonks)

perl -le'$n=shift;$==0,(1x$_)=~/^(1|11(??{}))*$(?{$=++})^/,print$=for 0..$n-1' 7

Output:

1
1
2
3
5
8
13

Answer 18

int Fib(int n)
{
   if(n > 46)
      throw new ArgumentOutOfRangeException("n");
   if(n == 46)
      return 1836311903;
   else if(n == 45) 
      return 1134903170;
   else
      return Fib(n + 2) - Fib(n + 1);
}

This will probably blow your stack.

Fibonacci numbers n > 46 will overflow a 32 bit int.

Answer 19

go:

package main

import fmt "fmt"

func halfFib(co, out chan int) {
    a := 0
    for {
        a += <-co
        out <- a
        co <- a
    }
}

func main() {
    co := make(chan int)
    out := make(chan int)
    go halfFib(co, out)
    go halfFib(co, out)
    co <- 1
    n := <-out
    for n > 0 {
        fmt.Println(n)
        n = <-out
    }
}

Answer 20

Javascript:

Sent this in for a Javascript position with a game software company recently. I'd never implemented Fibonacci numbers but immediately recognized them. My implmentation is non-recursive and completely of my own devising though I'm presuming its a known solution. They actually flew me up for an in person interview so I'm guessing the following isn't too awful:

(2) In JavaScript, write a recursive function that will print out the following output:

0 1 1 2 3 5 8 13 etc.

I know enough about what recursion is to know that it can be problematic from a resource (memory) consumption perspective particularly in a language that does not implement proper tail recursion, and I don't think Javascript does (but I do know that Lua does!). I also recognize this as a Fibonacci sequence, but I can't remember the recursive solution, but can certainly provide a non-recursive solution, replete with input validation using a regular expression. If the implementation seems odd, please bear in mind that I've never implemented this algorithm before so this solution is completely of my own devising.

<script> 
function fibseq(iter) { 
  if (!/^\d+$/.test(iter)) { 
      alert("Please retry generating Fibonacci numbers with input of 0 or a positive integer"); 
      return; 
    } 

    var fibseq = []; 

    for (var i=0; i<=iter; i++) { 
        if (i<=1) { 
          fibseq.push(i); 
        } 
        else { 
          fibseq.push(fibseq[i-1] + fibseq[i-2]); 
        } 
    } 

    alert('fibseq(' + iter + '): ' + fibseq.join(' ')); 
} 

fibseq(7); 
</script>

Answer 21

Not clever, just have some fun :).

To run:

gcc the_file.c -DN=7
./a.out

Requires gcc and support for POSIX's printf positional specifier support.

---

#include<stdio.h>
int main() {
    int n = N;
    if (n >= 2) {
        int r, t;
        char x[34],*s =
        "#include<stdio.h>%2$c"
        "int main() {"
            "int n = N;"
            "if (n >= 2) {"
                "int r, t;"
                "char x[34],*s = %3$c%1$s%3$c;"
                "sprintf(x, %3$cgcc -DN=%%d -x c -%3$c, n-1);"
                "FILE* f = popen(x, %3$cw%3$c);fprintf(f,s,s,10,34);pclose(f);"
                "f = popen(%3$c./a.out%3$c, %3$cr%3$c);fscanf(f,%3$c%%d%3$c, &r);pclose(f);"
                "sprintf(x, %3$cgcc -DN=%%d -x c -%3$c, n-2);"
                "f = popen(x, %3$cw%3$c);fprintf(f,s,s,10,34);pclose(f);"
                "f = popen(%3$c./a.out%3$c, %3$cr%3$c);fscanf(f,%3$c%%d%3$c, &t);pclose(f);"
                "n = r+t;"
            "}"
            "printf(%3$c%%d%3$c, n);puts(%3$c%3$c);"
            "return 0;"
        "}";
        sprintf(x, "gcc -DN=%d -x c -", n-1);
        FILE* f = popen(x, "w");fprintf(f,s,s,10,34);pclose(f);
        f = popen("./a.out", "r");fscanf(f,"%d", &r);pclose(f);
        sprintf(x, "gcc -DN=%d -x c -", n-2);
        f = popen(x, "w");fprintf(f,s,s,10,34);pclose(f);
        f = popen("./a.out", "r");fscanf(f,"%d", &t);pclose(f);
        n = r+t;
    }
    printf("%d", n);puts("");
    return 0;
}

Answer 22

A little bit of Linq cheekiness anyone?

// Edit: Forgot these three lines
var sqrt5 = Math.Sqrt(5);
var a = (1 + sqrt5)/2;
var b = (1 - sqrt5)/2;

foreach (var d in new object[n].Select((o, i) => (int)((Math.Pow(a, i + 1) - Math.Pow(b, i + 1)) / (a - b))))
{
    Console.WriteLine(d);
}

Answer 23

AntiChess: Windows cmd

This is probably the slowest, least elegant, most resource intensive of the answers. It works for 0 to full disk.

type fibo.cmd

@echo off
type nul>a
if "%1"=="0" goto :done
type nul>b
<nul (set/p z=1) >a
<nul (set/p z=1) >i
:loop
copy /b a c >nul
copy /b b+c a >nul
copy /b c b >nul
<nul (set/p z=1) >>i
call :size i
if /i %s% LSS %1 goto loop
:done
call :size a
echo The %1th Fibonacci number is %s%
del a
if exist b del b
if exist c del c
if exist i del i
:size
set s=%~z1

C:\fibo>fibo 20
The 20th Fibonacci number is 6765

Yes, I know SET /A:

@set a=1&set b=0&for /l %%i in (2,1,%1)do @set/ac=a&set/aa=b+c&set/ab=c
@echo %a%

Answer 24

C++ Template Language

Nth Fibonacci number calculated at compilation time:

template<int N> struct Fib {
  static const int result = Fib<N-1>::result + Fib<N-2>::result;
};

template<> struct Fib<0> {
  static const int result = 0;
};

template<> struct Fib<1> {
  static const int result = 1;
};

#include <iostream>
int main(void){
  std::cout << "Fib(10) = " << Fib<10>::result << std::endl;
  return 0;
}

Answer 25

Maybe I read too literally?

std::string Fibonacci(unsigned n)
{
   return "either the nth Fibonacci number or the first n Fibonacci numbers.";
}

Answer 26

IPython, O(log n) with exact bigint results (by matrix powers), lambda-style. Who said python ought to be readable?

In [1]: mult = lambda ((a,b),(c,d)),((e,f),(g,h)):((a*e+b*g, a*f+b*h), (c*e+d*g, c*f+d*h))

In [2]: power = lambda m,n:(m) if (n==1) else (power(mult(m,m), n/2) if (n%2==0) else mult(power(mult(m,m), n/2), m))

In [3]: map(lambda n:power(((0,1),(1,1)), n), xrange(1,10))
Out[3]: 
[((0, 1), (1, 1)),
 ((1, 1), (1, 2)),
 ((1, 2), (2, 3)),
 ((2, 3), (3, 5)),
 ((3, 5), (5, 8)),
 ((5, 8), (8, 13)),
 ((8, 13), (13, 21)),
 ((13, 21), (21, 34)),
 ((21, 34), (34, 55))]

Answer 27

public class FibonacciSequence : IEnumerable<ulong>
{

    public IEnumerator<ulong> GetEnumerator()
    {
        yield return 0;
        yield return 1;
        ulong a = 0;
        ulong b = 0;
        ulong c = 1;
        checked
        {
            while (true)
            {
                a = b;
                b = c;
                try
                {
                    c = a + b;
                }
                catch (OverflowException)
                {
                    yield break;
                }
                yield return c;
            }
        }
    }

    System.Collections.IEnumerator 
         System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Answer 28

This my favorite solution:

private readonly static double rootOfFive = Math.Sqrt(5); 
private readonly static double goldenRatio = (1 + rootOfFive) / 2; 

internal static int GetFinbonacciValue(int number) 
{ 
    return Convert.ToInt32((Math.Pow(goldenRatio, number) - Math.Pow(-goldenRatio, -number)) / rootOfFive); 
}

Answer 29

A Python solution. Uses a time-memory tradeoff to achieve efficency!

print """import sys

fib = ["""

a, b = 0L, 1L
for i in range(1000):
    print "    %d," % a
    a, b = b, a + b

print """]

n = int(sys.argv[1])
print fib[n]"""

Answer 30

Now you procedural code monkeys have finished at your typewriters... time for some Shakespeare (no, not the language based on keywords like "codpiece")

It's a recursive set based operation

DECLARE @Limit int

SELECT @Limit = 10

;WITH cFoo AS
(
    SELECT 0 as n, CAST(0 as bigint) AS x, CAST(1 as bigint) AS y
    UNION ALL
    SELECT n+1, y, x + y FROM cFoo WHERE n+1 < @Limit
)
SELECT
    cFoo.x
FROM
    cFoo
OPTION (MAXRECURSION 0)

Edit: SQL Server 2005+. It can be done in other dialects too

Answer 31

A less common way to calculate Fibonacci numbers:

def fib(n):
   i = j = 1.0
   for _ in range(n):
      j *= i
      i = 1 / i + 1
   return int(j)

Answer 32

Python generator:

def fibonacci():
    n, m = 0, 1
    while True:
        yield n
        n, m = m, n + m

Called n times.

Answer 33

Python

a,b = 0,1
while b:
    print a,
    a,b = b,a+b

Nice and short. Prints as many fib numbers as your computer has ram to store... I guess.

Answer 34

begin

declare @cnt int; set @cnt = 2;
declare @fibs table(fib bigint, sequence int); insert into @fibs select 0,1 union select 1,2;  

while(@cnt<93) begin
    set @cnt = @cnt + 1
    insert into @fibs
    select sum(fib), @cnt from @fibs where sequence > @cnt-3
end

select * from @fibs

end

Answer 35

J has of course a whole lot of smart ways to tackle this (see http://www.jsoftware.com/jwiki/Essays/Fibonacci%20Sequence)

However, I came upon this almost by accident and I enter it as an "anti-code-chess" answer. Meaning that it's really dumb:

fib =: 3 : 0
    if. y <: 1 do.
        y
    else.
        (fib y-1)+(fib y-2)
    end.
)

While potentially dangerous in many languages, in J it's system halting dumb. Do not try this with 100 unless you are ready to kill a very voracious process

Answer 36

dc in stack

?k1d[sBdlBrlB+zK>L]dsLxf

Instead of printing the numbers as they are calculated, it adds them in order to the stack and dumps the whole stack at the end.

dc uses bignum arithmetic. I tested with 10,000 numbers. The 10,000th number is 2,090 digits long.

Works for n > 2.

And it's only 24 chars long.

dc -f fibo.dc
15
610
377
233
144
89
55
34
21
13
8
5
3
2
1
1

Answer 37

Another recursive one in Scala:

def fib: Stream[Int] =
  Stream.cons(0, Stream.cons(1, (fib zip fib.tail) map { case (p, q) => p + q }))

Defines an infinite sequence of Fibonacci numbers. Try printing the first few elements with:

fib take 20 print

It creates a stream by starting with 0 and 1. Then the tail is made in two steps:

1. (fib zip fib.tail) uses the zip operation, which creates a sequence of pairs from corresponding elements from fib and fib.tail. That sequence will look like: [(0, 1), (1, 2), (2, 3), (3, 5), ...]
2. That sequence is mapped using the inline function { case (p, q) => p + q } to add the two numbers in each pair, forming the tail of the sequence: [1, 3, 5, 8, ...]

The result is a stream producing the Fibonacci sequence [0, 1, 1, 3, 5, 8, ...]

Answer 38

PHP

<?php
$cache = array(0, 1, 1);
function fib($n) {
    global $cache;

    return (isset($cache[$n])) ? $cache[$n] : ($cache[$n] = fib($n - 2) + fib($n - 1));
}
?>

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765

Answer 39

SWI-prolog. It works with arbitrary precision integers.

fibolist(N, R) :- fibohelper(N, 1, 1, [1, 1], R).
fibohelper(0, _, _, R, R).
fibohelper(N, F2, F1, PR, R) :- N > 0, F is F2 + F1, N1 is N - 1, append(PR, [F], RR), fibohelper(N1, F1, F, RR, R).

And the call:

2 ?- fibo2list(100, R).
R = [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, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026, 354224848179261915075, 573147844013817084101, 927372692193078999176] .

prolog is great, isn't it? :D

Answer 40

In F#, using an infinite tail-recursive sequence.

let fibseq =    
    let rec fibseq n1 n2 = 
        seq { let n0 = n1 + n2 
              yield n0
              yield! fibseq n0 n1 }
    seq { yield 1I ; yield 1I ; yield! (fibseq 1I 1I) }

let fibTake n = fibseq |> Seq.take n //the first n Fibonacci numbers
let fib n = fibseq |> Seq.nth (n-1) //the nth Fibonacci number

Answer 41

Python: print("1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...") Also, a clever way would be to perform image processing on these images: http://www.google.com/images?hl=en&safe=off&q=fibonacci%20sequence%20in%20nature&um=1&ie=UTF-8&source=og&sa=N&tab=wi

Answer 42

Here's a program in C:

#include<stdio.h>
#define N 0
#define FNMINUSONE 1
#define FNMINUSTWO 0
char*c="#include<stdio.h>%c#define N 0%c#define FNMINUSONE %d%c#define FNMINUSTWO %d%cchar*c=%c%s%c;%cint main(int argc, char*argv[]){%c  int n=atoi(argv[1]);FILE*f=fopen(%cfibo.c%c,%cw%c);%c  printf(c,10,10,FNMINUSONE+FNMINUSTWO,10,FNMINUSONE,10,34,c,34,10,10,34,34,34,34,10,10,34,34,34,34,10,10);fprintf(f,c,10,10,FNMINUSONE+FNMINUSTWO,10,FNMINUSONE,10,34,c,34,10,10,34,34,34,34,10,10,34,34,34,34,10,10);%c  fclose(f);if(n>1){system(%cgcc -o fibo fibo.c%c); char s[80];sprintf(s,%c./fibo %%d%c,n-1);system(s);}%c}%c";
int main(int argc, char*argv[]){
  int n=atoi(argv[1]);FILE*f=fopen("fibo.c","w");
  printf(c,10,10,FNMINUSONE+FNMINUSTWO,10,FNMINUSONE,10,34,c,34,10,10,34,34,34,34,10,10,34,34,34,34,10,10);fprintf(f,c,10,10,FNMINUSONE+FNMINUSTWO,10,FNMINUSONE,10,34,c,34,10,10,34,34,34,34,10,10,34,34,34,34,10,10);
  fclose(f);if(n>1){system("gcc -o fibo fibo.c"); char s[80];sprintf(s,"./fibo %d",n-1);system(s);}
}

Compile: gcc -o fibquine fibquine.c

Start: ./fibquine 10 (for the 10th fibonacci number)

The program computes the fibonacci number the following way: It reproduces its own source code, but with other constants (needed for the fibonacci calculation), then compiles the newly generated source code and reruns the program recursively (i.e. it gets compiled again, run again, compiled again, run again, and so on). Note that I run it under Ubuntu 10.04 and did not test it with other operating systems.

Cleverness of the program is disputable, but I think it's definitely unexpected.

Answer 43

F# Using Seq.unfold

let fib n =
  Seq.nth n (Seq.unfold 
    (fun (c, n) -> Some(c, (n, c + n)))
    (0L, 1L))

Answer 44

Shortest C# solution so far

Enumerable.Range(0, n).Aggregate(new { a = 1, b = 0 },
    (a, b) => new { a = a.b, b = a.a + a.b }).b;

I know this is not code golf. I thought it was clever nonetheless :)

Answer 45

JavaScript

var x = 6;
document.write((function(n){
    return n <= 1 ? n : arguments.callee(n-1)+arguments.callee(n-2);
})(x)); // outputs 8