Building upon the proven success of Code Golf ^{[1]}, I would like to introduce Code Chess ^{[2]}.
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.
OpenOffice Calc / MS Excel
A1: 1 A2: 1 A3: =A1 + A2:
Grab handle of A3
And fill down
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 :-) ).
Console.WriteLine(i); Console.WriteLine(i); i ++;
- KennyTM
WriteLine
calls! What's wrong with int i = 1; Console.WriteLine(i); while (true) { Console.WriteLine(i); i = i+1; }
? - Matt Ball
Console.WriteLine(i++)
? what a waste of lines - Nico
(I can't take credit for this thing of beauty - see source: perlmonks ^{[1]})
perl -le'$n=shift;$==0,(1x$_)=~/^(1|11(??{}))*$(?{$=++})^/,print$=for 0..$n-1' 7
Output:
1
1
2
3
5
8
13
[1] http://www.perlmonks.org/?node_id=813858Maybe I read too literally?
std::string Fibonacci(unsigned n)
{
return "either the nth Fibonacci number or the first n Fibonacci numbers.";
}
+>+< [ >.< [>+>+<<-]> ]
Hex dump of output:
0101020305080d1522375990e97962db3d18556dc22ff12011314273b528dd05e2e7c9b07929a2cb
6d38a5dd825fe140216182e36548adf5a29739d009d9e2bb9d58f54d428fd1603191c25315687de5
6247a9f0998922abcd7845bd02bfc18041c102c3c5884dd522f719102939629bfd98952dc2efb1a0
51f1423375a81dc5e2a78930b9e9a28b2db8e59d821fa1c0612182a325c8edb5a257f9504999e27b
5dd8350d424f91e07151c213d5e8bda562076970d949226b8df8857d027f
The first n fibonacci numbers modulo 256, where n = 190.
>.<
smiley on the center~ - GaiusSensei
Who said constructors cannot be recursive? ^{[1]}
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] http://msdn.microsoft.com/en-us/library/1w8stdbt.aspx#!/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))
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 ^{[1]}.
[1] https://docs.google.com/uc?export=download&id=0B188SCxZIw27ODYzNGRkODYtMmE3NC00ZjdkLTliZDUtZmZjYWY1ZGNiNmVkNth 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;
}
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;
}
Using
Binet's formula
^{[1]} (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 ^{[2]} you can't calculate really large numbers (dependent on floating point implementation).
[1] http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.htmlJust 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; }))
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.
else if(n == 45) return 1134903170;
- SLaks
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%
set /a
variant you don't need delayed expansion. set /a
automatically expands variable names even without %
or !
. - Joey
?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[1] http://linux.die.net/man/1/dc
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++;
}
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
}
}
ebx
is ret value in x86 - Yuval Adam
As in the fibonacci code golf ^{[1]}, i would like to suggest some examples from the haskell webpage ^{[2]}.
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
[1] http://stackoverflow.com/questions/232861/fibonacci-code-golfNow you procedural code monkeys have finished at your typewriters... time for some Shakespeare ^{[1]} (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
[1] http://en.wikipedia.org/wiki/Infinite_monkey_theoremEnumerable.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 :)
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();
}
}
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);
}
Python generator:
def fibonacci():
n, m = 0, 1
while True:
yield n
n, m = m, n + m
Called n times.
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;
}
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;
}
<?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
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 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)
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.
F# Using Seq.unfold
let fib n =
Seq.nth n (Seq.unfold
(fun (c, n) -> Some(c, (n, c + n)))
(0L, 1L))
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.
function f = fib(n);
if n > 2
z = [0 1; 1 1]^(n-1)*ones(2, 1);
f = z(1);
else
f = 1;
end
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
}
}
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>
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))]
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 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]"""
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
J ^{[1]} 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
[1] http://www.jsoftware.comThanks to scalaz ^{[1]}
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)
[1] http://code.google.com/p/scalaz/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);
}
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).
JavaScript
var x = 6;
document.write((function(n){
return n <= 1 ? n : arguments.callee(n-1)+arguments.callee(n-2);
})(x)); // outputs 8
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:
(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), ...]
{ 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, ...]
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
^{[1]}
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