147
\$\begingroup\$

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.


Leaderboard

/* 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 ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

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

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

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

var OVERRIDE_REG = /^Override\s*header:\s*/i;

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

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      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],
        link: a.share_link,
      });
    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;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    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)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

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

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

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

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
5
  • 4
    \$\begingroup\$ I am sort of waiting for a response like "f", 1 byte, in my math based golf language. \$\endgroup\$ Aug 11, 2020 at 11:57
  • \$\begingroup\$ @ChrisJesterYoung can we use 1.0 are 1 only? \$\endgroup\$ May 11, 2022 at 2:45
  • \$\begingroup\$ @NumberBasher 1.0 is fine. \$\endgroup\$ May 20, 2022 at 19:10
  • \$\begingroup\$ What about 1.3? \$\endgroup\$ Aug 28, 2022 at 15:10
  • 1
    \$\begingroup\$ Am I allowed to start the sequence with 0, 1? \$\endgroup\$
    – hakr14
    Oct 11, 2022 at 3:41

319 Answers 319

1
3 4
5
6 7
11
2
\$\begingroup\$

Pyt, 1 byte

Get the nth Fibonacci number:

Explanation:

           Implicit input
 Ḟ         Return (input)-th Fibonacci number

Try it online!

Pyt, 7 bytes

Get an infinite list of Fibonacci numbers:

0`ĐḞƤ⁺ł

Explanation:

0           Push 0 [this is the counter]
 `    ł     While the counter is not zero (checked at 'ł')
  Đ         Duplicate the counter
   ḞƤ       Print the (counter)-th Fibonacci number
     ⁺      Increment the counter

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Japt, 3 bytes

Just to add to the collection.

0-indexed, using 0 as the first number in the sequence.

MgU

Try it

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Haskell, 30 bytes (was 33)

f=0:1:[f!!n+f!!(n+1)|n<-[0..]]

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ You should add a TIO link and some sample cases \$\endgroup\$ Aug 9, 2018 at 19:32
  • \$\begingroup\$ @MuhammadSalman They do not have to add a link. I think "should" is a bit too forceful. \$\endgroup\$ Aug 9, 2018 at 19:52
  • \$\begingroup\$ Ok I added the TIO link, this is my first time posting \$\endgroup\$
    – mrFoobles
    Aug 9, 2018 at 22:04
  • \$\begingroup\$ @mrFoobles For demonstration purposes, I think main=print f would be more impressive as it shows the magnitude of infinite lists. \$\endgroup\$ Aug 9, 2018 at 22:19
  • \$\begingroup\$ @JonathanFrech yeah, should have been you could add and not should add \$\endgroup\$ Aug 10, 2018 at 10:28
2
\$\begingroup\$

Prolog, 36 35 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.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Welcome to PPCG! The usual consensus is to include the function invocation if it needs to be called with special arguments. \$\endgroup\$
    – Laikoni
    Nov 4, 2018 at 10:46
  • \$\begingroup\$ Should I include the call in the character count? \$\endgroup\$ Nov 4, 2018 at 16:54
  • \$\begingroup\$ 26 bytes: X+Y+O:-O=X;Z is X+Y,Y+Z+O. Try it online! \$\endgroup\$ Feb 5, 2020 at 19:18
2
\$\begingroup\$

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

Try it online here.

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.

\$\endgroup\$
1
  • \$\begingroup\$ This is code-golf, so please post the shortest solution you can find with its byte count. \$\endgroup\$
    – lirtosiast
    Oct 22, 2015 at 17:20
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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 <
\$\endgroup\$
2
\$\begingroup\$

Jasmin, 120 bytes

Defines a class F with a static method f that calculates the nth Fibonacci number. My implementation is essentially an iterative solution that stores partially computed Fibonacci numbers on the stack.

.class F
.super java/io/File
.method static f(I)I
ldc 0
ldc 1
dup_x1
iadd
iinc 0 -1
iload_0
ifgt $-9
ireturn
.end method

Some interesting golfing tricks used

  1. Extending java/io/File is shorter than extending java/lang/Object (The super line cannot be omitted). I've check and File is tied for the shortest fully qualified class name.
  2. Making this an instance method would let me remove static from the method header but, then I would have to explicitly implement an empty constructor to make the function callable (costing quite a few bytes).
  3. Juggling the Fibonacci values on the stack turned out to be shorter than storing them in local variables.
  4. On the other hand it's worth storing the index in a local variable. This makes stack management easier (i.e. shorter) without too much extra length since there is an instruction for adding or subtracting from locals variables.
  5. Although the JVM technically requires that you declare the maximum stack size before hand with .limit stack 5, this can be omitted if the class file is executed with the -noverify flag. I'm pretty sure this is some sort of undefined behavior but, it works in this this case.

Test setup

To test the code you, need a main method to invoke the static method.

class FibTest {
    public static void main(String[] args){
        for(int i = 0; i < 20; i++){
            System.out.println(F.f(i));
        }
    }
}

You then need to use jasmin.jar (obtained from the source forge linked in the title) to build F.class before building and executing the test file. Since the stack size was omitted, you need to execute the class with -noverify. The makefile below handles this.

test: FibTest.class
    java -noverify FibTest

FibTest.class: FibTest.java F.class
    javac FibTest.java    

F.class: F.j
    java -jar jasmin.jar F.j
\$\endgroup\$
2
\$\begingroup\$

Brachylog, 10 bytes

0;1⟨t≡+⟩ⁱh

Try it online!

Generates an infinite list of Fibonacci numbers through the output variable.

Brachylog, 14 12 bytes

0;1⟨{tẉ₂}↰+⟩

Try it online!

Prints terms infinitely, separated by newlines.

0;1             Starting with [0,1],
    {tẉ₂}       get and print the second element,
          +     sum the two elements,
   ⟨     ↰ ⟩    and recur on the pair of those two values.

A variant to find the nth term of the sequence, 0-indexed:

Brachylog, 13 bytes

∧0;1⟨t≡+⟩ⁱ↖?t

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ An interesting (very slow) 12-byter, 0-indexed but wrong on element 0: {ḃ₁~clᵐ⌉<3}ᶜ \$\endgroup\$ Nov 20, 2019 at 23:45
2
\$\begingroup\$

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]
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Oasis, 2 bytes

Answer to the open exercise on the Oasis repo.

+T

Explanation

Expanded program:

bc+10

When + requires 1 parameter, it tries to calculate a(n-1). For the other parameter, it tries to calculate a(n-2). (Hence the expansion.)

In addition, the T instruction expands to 10 in the program, which are the base test cases (a(0) is 0. a(1) is 1. Since base test cases are popped from the end before the Oasis program is executed in reverse.)

TIO

\$\endgroup\$
2
\$\begingroup\$

Cascade, 28 25 bytes

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

\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
2
\$\begingroup\$

dc, 21 17 bytes

0z[dp_3R+lmx]dsmx

Try it online!

This prints the Fibonacci sequence endlessly.



My previous (21-byte) version accepted an input \$n\$ on stdin, outputting the \$n^\text{th}\$ Fibonacci number on stdout (1-indexed):

9k5v1+2/?^5v/.5+0k1/p

\$\endgroup\$
2
\$\begingroup\$

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)
    ʟ⟨e⟩ (if n<=1, jump to end label)
1                (push 1)
 z               (subtract)
  b              (dup)
   1             (push 1)
    z            (subtract)
     <f>         (recurse)
        d        (swap)
         <f>     (recurse)
            s    (add)
             ⟨e⟩ (end label)
\
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 25 bytes by using T and F as variables. \$\endgroup\$ May 21, 2022 at 15:39
  • 1
    \$\begingroup\$ 23 bytes by using T and F as variables, and additional inspiration from Giuseppe... \$\endgroup\$ May 26, 2022 at 21:22
  • 1
    \$\begingroup\$ As far as I'm concerned, those are sufficient improvements you should submit them independently. Really like them by the way \$\endgroup\$ Jun 2, 2022 at 1:29
2
\$\begingroup\$

Flurry, 46 bytes

{}{<{}{<[<>{}]{{}[<><<>()>]}>}>}{{}{{}}{{}}}()

How to run:

$ target/Flurry -nin -c "{}{<{}{<[<>{}]{{}[<><<>()>]}>}>}{{}{{}}{{}}}()" 8
34

It doesn't use the stack at all (except for fetching the input number from the pre-populated stack). Instead, it uses pure functional construction developed by Anders Kaseorg in my SKI golf challenge.

one = \f. \x. f x
    = I
    = {{}}

one-pair = \f.f one one
         = {{}{{}}{{}}}

succ = \n. \f. \x. f (n f x)
     = \n. \f. S (\x. f) (n f)
     = \n. S (\f. S (K f)) n
     = S (S . K)
     = <><<>()>

next-pair-helper = \f. \m. \n. f n (m succ n)
                 = \f. \m. S f (m succ)
                 = \f. S f ∘ (\m. m succ)
                 = {<[<>{}]{{}[<><<>()>]}>}

next-pair = \p. \f. p (next-pair-helper f)
          = \p. p ∘ next-pair-helper
          = {<{}{<[<>{}]{{}[<><<>()>]}>}>}

fib = {} next-pair one-pair K
    = {}{<{}{<[<>{}]{{}[<><<>()>]}>}>}{{}{{}}{{}}}()
\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
2
+100
\$\begingroup\$

Barrel, 26 bytes

Disclaimer: The language is newer than the question, but I didn't even think of golfing this until after I'd created the language. I did update the language after I originally wrote the answer, and changed my answer, but that was because I was fixing the interpreter and made some changes to the spec to make the language work better. I wasn't cheating, I promise :)

+&1:0¤n &0:@1&1:a#@0+←1

Explanation:

+                          // set the accumulator to one by incrementing (initialization)
 &1:0                      // set register 1 to value 0 (initialization)
     ¤               ←1   // define a target that can be jumped to; then, jump to the previously defined jump target
      n                    // print the accumulator as a number and implicitly print the following space
        &0:@1              // set register 0 to register 1
             &1:a          // set register 1 to the value of the accumulator
                 #         // for as many times...
                  @0       //     ... as [value of register 0]...
                    +      //         ... increment the accumulator

I find it a bit hard to explain this further, so here's a rough chart of the accumulator and the two registers used during execution which will hopefully remove any confusion:

acc   reg[0]    reg[1] |
---------------------- |
1     <uninit>  0      | initialize; print acc("1")
1     0         1      | set reg[0] to reg[1]; set reg[1] to acc
1     0         1      | add reg[0] to acc; jump back and print acc ("1")
1     1         1      | set reg[0] to reg[1]; set reg[1] to acc
2     1         1      | add reg[0] to acc; jump back and print acc ("2")
2     1         2      | set reg[0] to reg[1]; set reg[1] to acc
3     1         2      | add reg[0] to acc; jump back and print acc ("3")
3     2         3      | set reg[0] to reg[1]; set reg[1] to acc
5     2         3      | add reg[0] to acc; jump back and print acc ("5")
5     3         5      | set reg[0] to reg[1]; set reg[1] to acc
8     3         5      | add reg[0] to acc; jump back and print acc ("8")

...and so forth and so on.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Added the bounty! Also, you don't need the disclaimer, there used to be a rule banning languages newer than the challenge but it was removed a while back :) \$\endgroup\$ Apr 14, 2021 at 1:52
2
\$\begingroup\$

Pinecone, 35 bytes

b:0;a:1;tru@(print:a;t:a;a:a+b;b:t)

Competitive Pinecone answer!

\$\endgroup\$
2
  • \$\begingroup\$ How did you get to know Pinecone? For me it was because I wanted to learn how to make my own language \$\endgroup\$
    – user100690
    Apr 21, 2021 at 16:14
  • \$\begingroup\$ @ophact I was researching on creating Lexers, and I found an article on it, that's how i reached there :) \$\endgroup\$
    – Wasif
    Apr 21, 2021 at 16:15
2
\$\begingroup\$

Red, 47 bytes

F: func[N][either N < 2[n][(F N - 2)+ F N - 1]]

Try it online!

First red answer. Modified from the solution on this page.

\$\endgroup\$
0
2
\$\begingroup\$

Python 3.8 (pre-release), 126 bytes

Neither short nor pretty, but possibly a new method!

from decimal import*
def f(n):l=n//4+1;p=10**l;getcontext().prec=n*l-l+1;return int(str(Decimal(p**2)/Decimal(p**2-p-1))[-l:])

Uses, for example:

1/(1000000-1000-1) = 0.000 001 001 002 003 005 008 013 021 034 055 089 ...

l can be any upper bound for the number of digits of the Fibonacci number after the one we want.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Grok, 16 bytes

1z1j
wYZlYp2yp+9

Try it Online!

Prints an infinite, tab-separated sequence. (Tabs instead of spaces/newlines since they are golfier.) The 5 flag is just so it times out faster.

Explanation:

1z           # Print the initial 1
  1          # Push 1 to the stack
   j         # Start the IP moving down
   l         # Start the IP moving right
    Yp       # Get the last number on the stack
      2yp    # Get the number before that (initially 0)
         +   # Add them together
w         9  # Print a Tab
 YZ          # Print the next number without popping it
\$\endgroup\$
2
\$\begingroup\$

Lua, 40 36 bytes

Prints the infinite Fibonacci sequence. Saved 4 bytes by using a goto operator instead of a while loop.

i,j=0,1::a::j,i=i,i+j print(i)goto a

Try it online!

\$\endgroup\$
2
\$\begingroup\$

LOLCODE, 262 bytes

HAI 1
I HAS A x
GIMMEH x
x IS NOW A NUMBR
BOTH SAEM x 0
O RLY?
YA RLY
VISIBLE "0"
NO WAI
I HAS A a ITZ 0
I HAS A b ITZ 1
I HAS A c ITZ 0
IM IN YR l UPPIN YR i WILE BOTH SAEM i SMALLR OF i DIFF OF x 2
c R SUM OF a b
a R b
b R c
IM OUTTA YR l
VISIBLE b
OIC
KTHXBYE

Reads n from STDIN and returrns the nth Fibonacci number.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Nim, 38 bytes

var a,b=1
while 1>0:a=b-a;echo a;b+=a

Attempt This Online!

Nim, 64 bytes, with arbitrary precision

import bigints
var a,b=initBigInt(1)
while 1>0:a=b-a;echo a;b+=a

Attempt This Online!

Thanks to @JoKing and @cairdcoinheringaahing

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Can you golf true to 1 and temp to c? \$\endgroup\$ Jun 28, 2021 at 22:32
  • 1
    \$\begingroup\$ You can also golf the declaration to var a,b=1 if you then change the update section to a=b-a;echo a;b+=a. You can also update the true part to be 1>0 like in your arbitrary precision code \$\endgroup\$
    – Jo King
    Jun 29, 2021 at 4:33
  • \$\begingroup\$ Right thanks, stupid of me to leave it like that. \$\endgroup\$
    – Qaziquza
    Jun 30, 2021 at 1:35
2
\$\begingroup\$

BitCycle -u, 67 45 bytes

v1<   <
BvC1Av
v~~v <
>  Cv>^
   v~~
  \>101!

Try it online!

It's beautiful... I have some idea of how this works.

The A, B and C are collectors. when the field is empty, the first non-empty collector (sorting in alphabetical order) has all collectors opened.

The basic idea is that the two numbers are stored in the B and A collectors. On each iteration:

  • The bits stored in A are emitted into the main C collector
  • The bits stored in B are duplicated and sent to the main C collector, and the C collector next to the A collector. This is necessary because otherwise the A collector would open before the C collector.
  • Both C collectors open. One emits its bits into A (previously stored in B).
  • The other duplicates its bits, and sends one stream to the B collector and the other stream to an output device
  • Duplicating bits also emits negated bits. one of these (a 0) from the B collector is sent to the output device via the \

This is because integer outputt in BitCycle is done in unary, with a sequence of n 1s and then a 0. a 0 must be sent before the next iteration begins.

The 101 is initially emitted to the output device to print 1, 1 (the 0 to print the next 1 is supplied before the 2 is emitted).

\$\endgroup\$
2
\$\begingroup\$

Factor + benchmark.fib3, 3 bytes

fib

Try it online!

And a non- built-in version:

Factor, 32 bytes

[ 0 1 rot [ tuck + ] times nip ]

Try it online!

\$\endgroup\$
1
3 4
5
6 7
11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.