# Fibonacci function or sequence

The Fibonacci sequence is a sequence of numbers, where every number in the sequence is the sum of the two numbers preceding it. The first two numbers in the sequence are both 1.

Here are the first few terms

1 1 2 3 5 8 13 21 34 55 89 ...


Write the shortest code that either:

• Generates the Fibonacci sequence without end.

• Given n calculates the nth term of the sequence. (Either 1 or zero indexed)

You may use standard forms of input and output.

(I gave both options in case one is easier to do in your chosen language than the other.)

For the function that takes an n, a reasonably large return value (the largest Fibonacci number that fits your computer's normal word size, at a minimum) has to be supported.

/* Configuration */

var QUESTION_ID = 85; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.

/* App */

return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(a) {
});
comment_page = 1;
}
});
}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
});
else process();
}
});
}

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

function getAuthorName(a) {
return a.owner.display_name;
}

function process() {
var valid = [];

var body = a.body;
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});

var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
});
else console.log(body);
});

valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});

var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;

.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)

var lang = a.language;
lang = jQuery('<a>'+lang+'</a>').text();

languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
});

var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);

langs.sort(function (a, b) {
if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
return 0;
});

for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
language = jQuery(language);
jQuery("#languages").append(language);
}

}
body {
text-align: left !important;
display: block !important;
}

width: 290px;
float: left;
}

#language-list {
width: 290px;
float: left;
}

font-weight: bold;
}

table td {
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="language-list">
<h2>Shortest Solution by Language</h2>
<table class="language-list">
<tr><td>Language</td><td>User</td><td>Score</td></tr>
<tbody id="languages">

</tbody>
</table>
</div>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>

</tbody>
</table>
</div>
<table style="display: none">
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
</tbody>
</table>

• I am sort of waiting for a response like "f", 1 byte, in my math based golf language. – Zsolt Szilagy Aug 11 '20 at 11:57

# PHP, 39 bytes

<?php for($b=1;;)echo$a=-$a+$b+=$a,' ';  Try it online! Explanation <?php  An infinite loop is started. The zero-th term in the series, initially $a, is 0, so needn't be assigned. $b is initially the second term and so is set to 1. for ($b = 1;;)


The part which does all the work is echo $a = -$a + $b +=$a, ' ';. Here it is expanded.

{


Calculate the new value for $b: the next term is the sum of the previous two. $b = $b +$a;


$a needs to be moved on one term as well. It is calculated by subtracting itself from the new value of $b.

    $a =$b - $a;  For byte-saving convenience, it is$a that is echoed each time—followed by a space!

    echo $a, ' '; }  • This can be 31 bytes since you don't need PHP's opening tag (you can run with php -r "code here" without opening tag) and you can use _ as separator instead of space: Try it online! – Night2 Sep 25 '19 at 9:42 # Klein, 2322 21 + 3 = 24 bytes (non-competing) Run with the 000 topology (1)\((@ ):?\1-+(:(+)$


## Explanation

When the program starts it executes (1) which will put a 1 under the input. It then deflects into the main loop.

The main loop is on the second line. It starts with the \ character. Unwrapped it looks like:

\1-+(:(+)$):?  This will redirect our pointer if the counter is zero or perform one iteration of the fibonacci sequence otherwise. Once the counter reaches zero we are deflected to the code ((@, this will hide the top two values (the counter and one of the fibonacci numbers) and terminate the program. # C, 64 bytes a,x,y,z=1;main(){for(;;){a=y;y=z;z=a;x+=y;y=x;printf("%d ",x);}}  Try it online! Uses the same method as my Implicit answer. • – Jonathan Frech Aug 19 '18 at 4:01 # ><>, 11 bytes 10r:n:@+aor  Try it online! Prints the Fibonacci sequence forever, separated by newlines. ## Whitespace, 50 47 Replace S,T,L with Space,Tab,Linefeed: SSSLSSSTLSLSTLSTLSSSLSLSSTSSTSLTSSSSLSTLSTLSLSL  Explanation: push 0 SS SL push 1 SS STL dup SLS outn TLST lbl 0 LSS SL dup SLS cpy 2 STS STSL add TSSS dup SLS outn TLST jmp 0 LSL SL  Outputs all the Fibonacci numbers concatenated (the question didn't mention separating them :) 1123581321345589144233377610987159725844181676510946...  (Thanks to @KevinCruijssen for -3 bytes.) • Hmmm... When I posted this (the 60th answer), the question automatically became "community wiki" :( – r.e.s. Dec 2 '13 at 13:48 • Yes, this site automatically community-wikis any posts after the 60th answer. But as a mod, I can undo that, and I'm going through the laborious process of removing community-wiki from all the answers, one by one. :-P – Chris Jester-Young Dec 2 '13 at 13:56 • I know it's been 4.5 years, but you can golf three bytes by changing SS SSL (push 0) to SS SL (push 0), LSS SSL (label_0) to LSS SL (label_0) and LSL SSL to LSL SL (jump to label_0). Pushing 0 is done implicitly after stating it's either positive/negative, even when you have no S and/or T for the binary part. Try it online (or with just raw spaces/tabs/new-lines: Try it online (47 bytes)). +1 from me, though. Nice answer! – Kevin Cruijssen Mar 14 '18 at 16:40 • @KevinCruijssen - Thanks for the tip. When implementing it, I found and corrected an error that was causing the output to be 01235... instead of the intended 11235.... – r.e.s. Mar 15 '18 at 3:28 # R16K1S60 Assembly, 36 bytes mov bx, ip mov ax, ip mov sp, data jmp inner prg: mov cx, [sp+ax] mov [sp+bx], cx inner: mov ex, [sp] mov dx, [sp+bx] mov [sp], dx add ex, dx mov [sp+ax], ex send ax, ex jmp prg data: dw 0x0000 dw 0x0001  Pretty simple. Abuses 7 registers, including the instruction pointer (for some predefines) To note why I used the IP instead of a constant, it's because the R16K1S60 has to use an extra word (two bytes) to encode a constant into an instruction. Alongside that, I used ax and bx instead of ex and dx for the offset because ex and dx cannot be referenced in only 3 bits (the size of the offset section of instructions that support it) Outputs the number as a word on port 2 # Haskell, 30 bytes (was 33) f=0:1:[f!!n+f!!(n+1)|n<-[0..]]  Try it online! • You should add a TIO link and some sample cases – Muhammad Salman Aug 9 '18 at 19:32 • @MuhammadSalman They do not have to add a link. I think "should" is a bit too forceful. – Jonathan Frech Aug 9 '18 at 19:52 • Ok I added the TIO link, this is my first time posting – mrFoobles Aug 9 '18 at 22:04 • @mrFoobles For demonstration purposes, I think main=print f would be more impressive as it shows the magnitude of infinite lists. – Jonathan Frech Aug 9 '18 at 22:19 • @JonathanFrech yeah, should have been you could add and not should add – Muhammad Salman Aug 10 '18 at 10:28 ## Prolog, 3635 29 bytes X+Y:-writeln(X),Z is X+Y,Y+Z.  Run with 1+1. (I don't think having to call the base case is cheating, but let me know.) Prints the first parameter and a newline, sets Z to X+Y, then does a recursive call. Edit 1: Can use writeln(X) instead of write(X),nl, saving one character. Edit 2: Can use X+Y as a predicate instead of f(X,Y), saving 6 characters. Also the initial call is shorter. • Welcome to PPCG! The usual consensus is to include the function invocation if it needs to be called with special arguments. – Laikoni Nov 4 '18 at 10:46 • Should I include the call in the character count? – Alex Trotta Nov 4 '18 at 16:54 • 26 bytes: X+Y+O:-O=X;Z is X+Y,Y+Z+O. Try it online! – ankh-morpork Feb 5 '20 at 19:18 ## Burlesque, 8 bytes Update: With current WIP one can use 1J2q?+C~. Shortest way to produce [fib(0)..fib(n)] without trashing the stack (14B): {0 1q?+#RC!}RS  Explanation There's the concept of "Continuation" in Burlesque which basically means that you run a function on a stack without destroying the stack. Fibonacci is the perfect example use-case for what these continuations are good for. If you have a program like 1 1 add then this results in a stack of 2 because add destroys the data. If add were not to destroy the data the stack would look like 1 1 2 and if we just do 1 1 add add it would look like 1 1 2 3. So all we need to do to generate a Fibonacci sequence is to call add n-times without popping the arguments. A continuation takes a snapshot of the stack, runs the function, pops the result from the stack, reverts the stack to the snapshot and pushes the result of the function to it. C! is the Burlesque built-in for "run this continuation n-times". However, doing so would trash our stack (which is no problem if you just want to print out Fibonacci numbers). Otherwise we need to use the RS built-in which runs a function in a different stack environment. RS takes a value as an argument, creates an empty stack, pushes that value to it and then runs the given function on that stack and after the function has run it will collect that stack into a list and push that list to the main stack. #R rotates the stack because the stack layout will look like N 0 1 but we need that N because it's the argument for C! so we rotate the stack. q?+ is just shorthand for {?+} (q wraps the next token into a block). If you don't care about trashing the stack you just drop the RS: blsq ) 10 0 1q?+#R!C 0 1 1 2 3 5 8 13 21 34 55 89  Shortest way to produce fib(n) as a reusable non stack-trashing piece of code I can think of is (17B): 0 1{Jx/?+}#RE!jvv  # Older Stuff There's dozens of ways to do that. These push the fibonacci numbers to the stack: blsq ) 0 1{#s2.+++}10E! blsq ) 0 1q?+10C!  However, the snippets above will also trash your stack. Alternatives for that are either: blsq ) 0 1{Jx/?+}10E!jvv  which just computes the 10th fibonacci number. Also by still using continuations you can let the whole thing run in a seperate stack environment like uhm so: blsq ) {10}{0 1q?+#RC!}rs {89 55 34 21 13 8 5 3 2 1 1 0} blsq ) 10{0 1q?+#RC!}RS {89 55 34 21 13 8 5 3 2 1 1 0}  Really depends on your needs. • This is code-golf, so please post the shortest solution you can find with its byte count. – lirtosiast Oct 22 '15 at 17:20 # Alchemist, 68 bytes y+_->y+a+b y+0_->z z+a->z+_ z+0a->x x+b->x+a x+0b->y+Out_a+Out_" "!y  Try it online! Outputs the 1-based sequence infinitely, If you want 0-based (i.e. 0 1 1 2 3 5...), you can change the trailing y to either x or z. ### Explanation: !y # Initialise the program with the y flag alongside the default _ y+_->y+a+b # Convert all _ atoms to a and b atoms y+0_->z # Once we're out of _ atoms, change to the z flag z+a->z+_ # Convert the a atoms back to _ atoms z+0a->x # Switch to the x flag x+b->x+a # Convert all b atoms to a atoms x+0b->y # Once we're out, change to y flag +Out_a # Print the number of a atoms +Out_" " # And a separator  If it makes you feel better, here's a more pseudo-codey version: _=1 while true: a=a+_ b=_ _=a a=b print a  # BitCycle, 21 bytes  1+ ~! CB0CA~ ^ 1 <  Outputs an unending sequence. Use the -u flag to get output in decimal. Try it online! Note: the current BitCycle interpreter doesn't play very well with infinite output. You have to halt the program (Ctrl-C) before it displays anything. On TIO, letting the program run until the 60-second timeout shows no output, either--you have to click the Run button (or hit Ctrl-Enter) again to halt it. ### Explanation This explanation assumes you're familiar with BitCycle. Conceptually, we store two numbers at a time, the smaller and the larger. At each step, we output the larger, set the new larger to be the larger plus the smaller, and set the new smaller to be the larger. We store and output the numbers in unary (using 1 bits), but we also need a separator (0 bit) after each number output. Our approach is to store the separator at the end of each number. When adding two numbers, we discard the separator from the first number added, and keep the separator from the second number added. In the code, the leftmost C collector holds the smaller number, while the rightmost C collector holds the larger. We're actually going to store everything negated, so the numbers are made of 0 bits and the separators are 1 bits. Thus, the leftmost C initially gets a single 1 (unary zero plus a separator bit) and the rightmost C gets 01 (unary one plus a separator bit). The C collectors open and dump their contents straight into the B and A collectors. Next, the A collector opens, holding the larger number. It goes through a couple of dupneg devices, with the following results: • A copy goes into the leftmost C collector, becoming the new smaller number. • A negated copy goes into the sink ! and is output. • A doubly-negated copy goes into the rightmost C collector, but the + ensures that it's only the 0 bits, not the trailing 1 separator. Finally, the B collector opens and dumps its contents into the rightmost C, adding the former smaller number to the former larger number to create the new larger number. The cycle repeats forever. ### Other versions Here's a modified version (still 21 bytes) that strips the separator off the smaller number (instead of the larger) before adding: 10>v ~! BA+BA~ ^ <  And here's an 18-byte version that starts at 0 instead of 1. (Thanks to Jo King for golfing it down from 21 bytes.) Here, we start with the "smaller" number at 1 and the "larger" number at 0, generating the extended Fibonacci sequence 1,0,1,1,2,3,... (Since the "larger" number is what we output, we don't see the first 1.)  1+ ~! CBCA~ ^10 <  # Pyramid Scheme, 385 bytes  ^ ^ / \ /l\ /set\ /oop\ ^-----^ ^-----^ - ^- /]\ ^-^ ^- ^---^ ^- -^ ^- ^- -/ \ -^ ^- -^ /set\ -^ /[\ / \ ^-----^ -^ ^---^ /out\- ^- / \ -^ -^ ^-----^ /+\ /set\ /1\ / \- /x\ ^---^-----^ ---/set\ --- - /x\ /+\ ^-----^ --- ^---^ /x\ /1\ /x\ - --- --- ---  Try it online! This guy's a whopper. Prints terms indefinitely with no separator. The bit on the left initializes the blank variable and x to one, and the bit on the right does the Fibonaccing. The loop condition (everything to the left below loop) prints both variables before checking the blank one for truthiness (it'll always be nonzero). The loop body updates first blank and then x, thus generating the next two terms for the condition to print. I can't quite figure out set. It doesn't quite follow the chain of execution, but it almost does, I think. I'll be looking at the Pyramid Scheme source in the next few days (and possibly extending the language); perhaps this will provide me with the insight required to golf some bytes off this monstrosity. # pure bash, 43 chars Inspired from user unknown's answer: for((r=l=i=1;i++<40;l+=r+=l)){ echo$r $l;}  Not really golfed, but I like it anyway. Or r=1 l=0;echo {,,}{,,}{,,}\$[r+=l]\ $[l+=r]  # Zsh, 31 bytes try it online for ((a=1;b+=a;a+=b))echo$a $b  32 bytes, based on James Brown's awk solution: for ((y=1;z=x+y;y=z))echo$[x=y]

42 bytes, to halt before int overflow:
(for ((a=1;b+=a;a+=b))echo $a$b)|head -46

NB: For a properly "endless" solution I need logic for long long (..) long integers, per this post

?01
^/
|.#
!9]
-0
!0]
+1


Try it online!

Outputs the Fibonacci numbers separated by tabs starting from 1. This shows off the behaviour of variables in Cascade, in that the variables 1 and 0 aren't static in this program.

Unfolded, this looks something like:

     @
^
^ \
/ . |
#  9 |
]    |
0 -   |
] 0  |
1 +   /
1 0 /
|


Try it online!

This initially branches twice, with the leftmost going down the tree until it sets ([) the variable 1 to the sum (+) of 1 and 0. Then it sets 0 to that value to the result of that minus 0. This has the effect of advancing one element in the Fibonacci sequence.For example, the values of repeated executions are:

0 1
1 1
1 2
2 3
3 5
5 8
8 13
...


Finally it prints the total result of that, which is the new value of 0. The next branch prints the tab separator (.9), and the final branch loops back around to the top of the program.

# Taktentus, 87 bytes

a:=1
@wy_n:=a
@wy:=32
b:=1
n:=44
@>=n
_:=@stop
@wy_n:=a
@wy:=32
c:=a
a+=b
b:=c
n--
_-=8


n are variable how many times we count (n-1 because first are writing directly)

# Erlang (escript), 36 bytes

I'm a total idiot. I didn't even think of this formula!

f(X)when X<2->1;f(X)->f(X-1)+f(X-2).


Try it online!

# Erlang (escript), 50 bytes

f(X,Y)->io:write(X),io:nl(),f(Y,X+Y).
f()->f(1,1).


Try it online!

# Erlang (escript), 51 bytes

Tail-recursion optimized.

f(0,X,_)->X;f(I,X,Y)->f(I-1,Y,X+Y).
f(X)->f(X,1,1).


Try it online!

# International Phonetic Esoteric Language, 28 bytes

<f>/b1ɨʌʟ|e|1zb1z<f>d<fib>s|e|\


A function that expects a number $$\n \ge 0\$$ to be on the stack, and leaves the $$\n\$$-th Fibonacci number.

Explanation:

<f>/ (n1 -- n2) (where n2 is the n1-th fibonacci number)
(check for case n=1)
b        (dup)
1       (push 1)
ɨ      (n>1?)
ʌ     (skip if n>1)
1                (push 1)
z               (subtract)
b              (dup)
1             (push 1)
z            (subtract)
<f>         (recurse)
d        (swap)
<f>     (recurse)
⟨e⟩ (end label)
\


# R, 33 32 bytes

CAUTION: This attempts to print the whole Fibonacci sequence. It does not stop.

a=b=1;repeat print(a<-(b=b+a)-a)


Pretty simple. Initialize a and b. Then a repeat loop which adds them to find the next number and print it. This loop will not stop, though eventually the overflow means it just prints NaN repeatedly.

Edit: saved 1 byte by switching to a=b=1 which required a different loop control mechanism to print the first few values, and then a different assignment location, etc.

# Arn, 5 bytes

Since I finally implemented sequences in my interpreter this is now a valid submission :)

╔Tò”7


# Explained

Unpacked: [1 1{+

[ Sequence...
1 1 ...with 2 values initialized at 1...
{ ...the rest of which are determined by the block...
+ ...that adds the top two values
} Implied, can be removed
] Implied, can be removed


Since Arn supports infinite sequences and BigNums, this will continuously output fibonacci numbers infinitely (hypothetically)

## Javascript, 272625 23 characters

for(a=b=1;n--;)a+=b=a-b


In an interactive javascript command line (Like google chrome console) it'll print out the nth fibonacci term for n > 1. undefined for n=1, runs forever for n < 1.

Credit to Bojidar Marinov

### 41 characters

for(x=[1,1],y=1;n-++y;)x[y]=x[y-1]+x[y-2]


Saving the n (>=2) first terms in an array.

• 25: for(b=a=1;n--;)b*=a=1+1/a 23: for(a=b=1;n--;)a+=b=a-b – Bojidar Marinov Sep 25 '20 at 17:10

## Bash 100

This is a very slow, but hey no performance penalty. First line needed.

#!/bin/bash
if [ $1 -lt 2 ]; then echo$1; exit; fi
expr $0 \expr$1 - 1\ + $0 \expr$1 - 2\

• More a question: You don't need a shebang, do you? See ruby, python and xy-script. – user unknown Apr 12 '11 at 1:39
• (($1<2))&& echo$1 && exit;v=$1;p=$0;echo $(($($p$((v-1)))+$($p \$((v-2))))) 77 chars with the same approach, just different syntax and a bit faster – user unknown Apr 12 '11 at 1:50
• I see the white space surrounding the brackets and instinctively click the "comment" button to tell you it should be removed... then I remember this is bash – Cyoce Mar 25 '16 at 6:05
• There is redundant whitespace here, after each semicolon. – Peter Cordes Dec 7 '16 at 15:04
• solution fails on TIO.run , and so does the version in comments. – roblogic Aug 28 '19 at 9:20

## Scala, 52 chars:

def f(a:Int,b:Int):Int={println(a);f(b,a+b)};f(0,1)


CHIP 8

Not so short but displays the fibonacci sequence on screen:

00E06600690060006101221E3900120E8200801081206F00810489F0120A6500830064F083428336833683368336F32900E0D56575088300640F8342F329D56500EE


without displaying on screen:

00E06000610182008010812081041206


Clojure: 38 chars

    (def f(lazy-cat[0 1](map +(rest f)f)))


run with:

    f


# Javascript - 48 chars

for(i=1;i<n;i++){f[i]=f[i-1]+(f[i-2]?f[i-2]:0);}


Clean and simple... probably not a shortness winner :D

Here is the full implementation:

function a(n) {
var i;
var f = new Array();
f[0]=1;

for(i=1;i<n;i++){f[i]=f[i-1]+(f[i-2]?f[i-2]:0);}

console.log(f);
}


# APL: 26 characters

This is a function which will print out the n and n-1 Fibonacci numbers:

{({⍵+.×2 2⍴1 1 1 0}⍣⍵)0 1}


For example,

{({⍵+.×2 2⍴1 1 1 0}⍣⍵)0 1}13


yields the vector:

233 144

• Surely, with APL's prodigious operator vocabulary, it should be able to compete in size with the GolfScript one? ;-) – Chris Jester-Young Apr 8 '13 at 11:32
• @ChrisJester-Young Oh probably, but I only started learning APL today... – SL2 Apr 8 '13 at 23:41

## C, 45 (37)

Only because it's easy:

f(n){return n<2?n?1:0:f(n-1)+f(n-2);}


Or the more compiler-friendly/standards-compliant but more verbose version:

#define m main(n
m){return n<2?n?1:0:m-1)+m-2);}


note: once compiled, you have to call main() with an actual value (which will likely take some command line fiddling depending on OS)

• Doesn't run for me. – Johannes Kuhn Nov 28 '13 at 22:53
• It only runs as a stand-alone in some environments with very specific settings. I'll add a friendlier version though. – Stuntddude Nov 28 '13 at 23:48
• Number of arguments could work. Intresting way to pass the parameter. – Johannes Kuhn Nov 29 '13 at 7:15
• n?1:0 can be replaced with just n. – Cyoce May 2 '16 at 15:23

### Befunge, 15 13 characters

1:.:00p+00g\#


I didn't spot any Befunge solutions, so I thought I'd write one. Too bad Befunge doesn't have a rotate-n operation, and trampoline # doesn't work at end-of-line to skip first character after looping around. Turns out that part of the spec is considered ambiguous on that point, and my initial interpretation is actually valid.

# Befunge 98, 10 characters

1:"]"y+#


8-character code generating the fibonacci sequence on the stack, under the assumption that # should first wrap around then skip, which sadly does not hold in CCBI (where I run my Befunge code). It would work if we restricted the fungespace X dimension to 8 cells.

1#;:"]"y+;


Using 10 characters, the code actually works in CCBI, generating the sequence on the stack.

1#;:.:"]"y+;


With 12 characters, we have working code that outputs space-delimited numbers to stdout (would be 10 chars if based on the first version).

1#;:.:"]"y+:02*k#@;


This 20-character version ends the loop as soon as overflow occurs (on 32bit system, it delivers the sequence up to 1836311903). If you add 2 more characters, each number is on a separate line (insert a, after :.)

All these versions operate purely on the stack, no modification of fungespace cells. The 'printing' versions do so in addition to generating the sequence on the stack.

## Breakdown:

1. 1 pushes 1 on the empty stack.
2. # skips the next fungespace cell (;).
3. :. duplicates, pops and prints the top-of-stack value (1 in the first iteration). Inserting a, here outputs an ASCII 10 character, which makes a new line.
4. : duplicates again. (Stack now [1 1])
5. "]" pushes 93 (ASCII). This is explained further below. (Stack now [1 1 93])
6. y pops a value and pushes system information for it. In our case, that's the third-of-top value on the stack. In the first iteration, this is 0, as there are only two elements there. (Stack now [1 1 0])
7. + pops two values and pushes their sum. (Stack now [1 1])
8. :0' compares the TOS value with 0 and pushes 1 if it was greater, else 0. (It should be a backtick.) (Stack now [1 1 1])
9. 2*k# pops and doubles our comparison result, and performs the # that many times (0 or 2). While the numbers are positive, it skips to the ;, otherwise to the @ (because k automatically moves the IP beyond its target with a 0 argument). (Stack now [1 1])
10. @ terminates the program. It is only reached when overflow occurred.
11. ; creates kind of a wormhole. It skips everything until it encounters another ;, which it will at the third character of the line. Execution continues with step 3.)

In step 5.), I use 93 as an argument to y. This value is individual, because y outputs things like the command line arguments and environment variables, and starts returning values from the stack (top-down) if its argument is greater than the size of actual system information y emits. If eg. you rename the script to a different length name, you have to adjust this value.

To find the correct value, you can insert 01-y (which pushes ALL system information) at the beginning, start in the debugger (-t switch for CCBI), step 4, see how big your stack is, add 3, and replace ] with the resulting character.

Note that the use of y may cause CCBI to report an Access violation on @ which can be safely ignored, as is the case on my system (Win8.1/64, ccbi.exe/32). The short versions keep on looping into eternity (given infinite memory).

PS: If we move the :. between the y and +, the printed sequence becomes 0 1 1 2 ... If we want it starting with 0 on the stack, we simply insert 0 at the beginning (and leave :.` where it is now).