3532

46
+71  Q:

## Code Chess: Fibonacci Sequence

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.

+28  A:

## 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(); }
}
``````
+1 Thats silly, but really cool. :P
+1, that is awesome!
+45  A:
``````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 :-) ).

+1 for cheating
This only prints the number 1 one time.
works for me in C#
@mobrule: So, `Console.WriteLine(i); Console.WriteLine(i); i ++;`
What a waste of `WriteLine` calls! What's wrong with `int i = 1; Console.WriteLine(i); while (true) { Console.WriteLine(i); i = i+1; }`?
-1 for cheating
+18  A:

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.

Is there somewhere that I can upload the original document?
@Slaks: Google docs
@Oscar: Does Google Docs support field codes?
I'm scared now. In normal mode, after 1023341553, it cycles 5, 8, 3 ... forever. When I switch to print preview, it gives *incorrect seven-digit numbers*, presumably just truncated for display, after 9227465.
If you select the 5, 8, 3's and click Update Field, Word will crash. I don't know why it would give incorrect numbers; try updating all field codes (afer deleting the 5, 8, 3's).
Once it gets past 1023341553, Word crashes: +1
+2  A:

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;
}
``````
+15  A:

## 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; }))
``````
I actually count 3 statements. Still nice though.
Just for the fun, I rewrote your snippet to haXe: http://actionscript.pastebin.com/zCE8s6ZZ
+4  A:

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
``````
+23  A:
``````#!/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))
``````
Very clever. Very much in the spirit of the notion, I think.
A:

## 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).
``````
+27  A:

## Brainf*ck

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

Hex dump of output:

``````0101020305080d1522375990e97962db3d18556dc22ff12011314273b528dd05e2e7c9b07929a2cb
6d38a5dd825fe140216182e36548adf5a29739d009d9e2bb9d58f54d428fd1603191c25315687de5
6247a9f0998922abcd7845bd02bfc18041c102c3c5884dd522f719102939629bfd98952dc2efb1a0
51f1423375a81dc5e2a78930b9e9a28b2db8e59d821fa1c0612182a325c8edb5a257f9504999e27b
5dd8350d424f91e07151c213d5e8bda562076970d949226b8df8857d027f
``````

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

I like the `>.<` smiley on the center~
YEARGHHH! Actually *solving* any given problem in BF is... awesome. :-D
+16  A:

Using Binet's formula (though not the original version rather a slightly altered one) you can calculate the `n`th 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).

Clever, creative.
I'm not sure using Binet's formula counts as cleverness unless you are in fact Jacques Philippe Marie Binet.
@Robert - I never took credit for this. Neither am I arrogant to think this code chess will help me, or anyone else, devise a better method for finding Fibonacci numbers which mathematicians have somehow overlooked for centuries.
This answer would be clever if you worked out the bounds for how much precision you need to get the Nth Fibonacci number and even moreso if you implemented simplified arbitrary-precision code that's optimized for the task.
+1  A:
``````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.

A:

# 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
``````
+4  A:

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
}
}
``````
Not familiar with x86 assembler, so maybe this is obvious, but how is the return value specified here? Perhaps ebx always has the return value on exiting from a function?
`ebx` is ret value in x86
Actually, DevStudio specifies the return value to be in EAX for integral types. Of course, this is compiler specific, but most IA32 compilers would follow the same convention.
+4  A:

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++;
}
``````
+1  A:

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;
}
``````
A:

# 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)
``````
+36  A:

# 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
``````
+1 because this is totally insane!
+1 for making my head hurt!
The runtime may be horrible, but this is the only bignum implementation I see here… the others all overflow at 32 or 64 bits.
@Potatoswatter, do you really want people to write code which works for large integers? This is just silly. The intent was to see clever code/approaches.
@Moron: those goals are incompatible? Getting anywhere with the fibonacci sequence requires bignums. Need to raise the bar a little to keep this interesting… and there's no point in using native integers when they impose such strict limitations.
I guess this would be a good answer for a code golf... but perhaps not for a code chess !
My eyes ... MY EYES!
@Potato: I disagree. Most algorithms here can _very easily_ be converted to use integers of the right size. Trying to impose the limitation you speak of is pointless.
@Moron: There are no limitations, it's an open ended problem. You can't fault people who *do* gracefully handle the exponential growth. (Erm, in terms of storage anyway ;v) .)
@Potato: Not faulting anyone. In fact, to me it seems you are doing the opposite: faulting people who don't try to handle all. fwiw, this was the first answer I gave a +1 to!
Looks just like all the other perl code I've seen here ;-)
+8  A:
``````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.

It doesn't work; you need to add `else if(n == 45) return 1134903170;`
A:

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
}
}
``````
+1  A:

## 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>
``````
This is equivalent to my C# one-liner. (Which was also my original algorithm)
+18  A:

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;
}
``````
A:

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);
}
``````
+9  A:

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%
``````
+1 Evil........
For the `set /a` variant you don't need delayed expansion. `set /a` automatically expands variable names even without `%` or `!`.
@Johannes - True, I didn't know it at the time. Updated, thanks.
+16  A:

# 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;
}
``````
Nice one. Really like the use of templates. Great fun to compile this changing 10 to 1 000 000:P
I think C++ template has a recursion depth limit, I've tried the factorial metaprogram before.
+32  A:

Maybe I read too literally?

``````std::string Fibonacci(unsigned n)
{
return "either the nth Fibonacci number or the first n Fibonacci numbers.";
}
``````
+1 for sheer cheek
-1 for sheer cheek
I added +1 for mocj's answer and voted for Yuval's comment. Should these votes cancel each other?
A:

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))]
``````
+50  A:
I like this one!!!
I should tell this trick to my grade 10 math teacher, because other students are having trouble with recursive sequences.
Memoization, anyone?
+2  A:
``````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();
}
}
``````
+1  A:

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);
}
``````
A:

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]"""
``````
+3  A:

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

I thought you mean Shakespeare the language http://en.wikipedia.org/wiki/Shakespeare_%28programming_language%29
@KennyTM: oh very droll... :-)
A:

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)
``````
A:

Python generator:

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

Called n times.

A:

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.

A:
``````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
``````
A:

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

+4  A:

# 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
```
A:

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, ...]`

+1  A:

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

A:

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

+1  A:

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
``````
A:

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&amp;safe=off&amp;q=fibonacci%20sequence%20in%20nature&amp;um=1&amp;ie=UTF-8&amp;source=og&amp;sa=N&amp;tab=wi

A:

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.

I like it, but [KennyTM beat you to it](http://stackoverflow.com/questions/2296664/code-chess-fibonacci-sequence/2298995#2298995).
A:

F# Using Seq.unfold

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

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

A:

JavaScript

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