149
\$\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, in accordance to the standard rules:

  • Generates the Fibonacci sequence without end.

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

  • Given n calculates the first n terms of the sequence

You may use standard forms of input and output.


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\$ Commented Aug 11, 2020 at 11:57
  • \$\begingroup\$ @ChrisJesterYoung can we use 1.0 are 1 only? \$\endgroup\$ Commented May 11, 2022 at 2:45
  • \$\begingroup\$ @NumberBasher 1.0 is fine. \$\endgroup\$ Commented May 20, 2022 at 19:10
  • \$\begingroup\$ What about 1.3? \$\endgroup\$ Commented Aug 28, 2022 at 15:10
  • 2
    \$\begingroup\$ Am I allowed to start the sequence with 0, 1? \$\endgroup\$
    – hakr14
    Commented Oct 11, 2022 at 3:41

336 Answers 336

1 2
3
4 5
12
4
\$\begingroup\$

Fig, \$4\log_{256}(96)\approx\$ 4.125 3.292 bytes

G:1'+

New language! Yay! This is a fractional byte language I've been advertising on TNB for a while now. It's pure printable ASCII, and has a 97 96 char codepage. Although the spec is mostly written by now, this commit only has the bare minimum implemented for this challenge. To run this, check the README. It will print Fibonacci numbers until your computer runs out of RAM. Explanation:

G1'+ - Takes no input
G    - Generate an infinite list using initial terms...
 1   - 1...
  '  - And the generating function...
   + - Addition (the initial terms are repeated to fit the arity)
\$\endgroup\$
0
4
\$\begingroup\$

C, 43 bytes

a;main(z){for(;;)printf("%d ",a=(z+=a)-a);}

try it out

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$
    – naffetS
    Commented Nov 9, 2022 at 20:59
4
\$\begingroup\$

Brachylog, 10 9 bytes

1⟦⟨t≡+⟩ⁱh

Try it online!

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

1⟦           Starting with [0, 1],
       ⁱ     iterate some (possibly zero) number of times:
  ⟨ ≡ ⟩      pair
   t         the last element with
     +       the sum of the two elements.
        h    Yield the first element of the result.

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\$ Commented Nov 20, 2019 at 23:45
3
\$\begingroup\$

Python, 36

f=lambda x:x>1and f(x-1)+f(x-2)or x
\$\endgroup\$
3
\$\begingroup\$

J - 20

First n terms:

(+/@(2&{.),])^:n i.2
\$\endgroup\$
3
\$\begingroup\$

Common Lisp, 48 Chars

(defun f(n)(if(< n 2) n(+(f(decf n))(f(1- n)))))
\$\endgroup\$
4
  • \$\begingroup\$ Is left-to-right evaluation order guaranteed in CL? If not, your solution won't work. (There is no such guarantee in Scheme, and many implementations are right-to-left.) \$\endgroup\$ Commented Apr 5, 2011 at 2:12
  • \$\begingroup\$ Left-to-right is in the standard so since these are all built-in functions it is reliable. (Macros can of course do stupid things :-) \$\endgroup\$
    – Dr. Pain
    Commented Apr 29, 2011 at 18:00
  • \$\begingroup\$ This is actually 47; you can get rid of the space between (< n 2) and n. \$\endgroup\$ Commented Nov 17, 2015 at 20:54
  • \$\begingroup\$ And a slight modification is 46: (defun f(n)(if(< n 2)n(+(f(1- n))(f(- n 2))))). \$\endgroup\$ Commented Nov 17, 2015 at 20:55
3
\$\begingroup\$

BrainFuck, 172 characters

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

Credit goes to Daniel Cristofani

\$\endgroup\$
3
\$\begingroup\$

PowerShell: 42 or 75

Find nth Fibonacci number - 42

A spin-off of Joey's answer, this will take user input and output the nth Fibonacci number. This retains some weaknesses also inherent to Joey's original code:

  • Technically off by 1, since it starts the Fibonacci sequence at 1,1 instead of the more proper 0,1.
  • Only valid for Fibonacci numbers which will fit into int32, because this is PowerShell's default type for integers.
  • Example: Due to the int32 limitation, the highest input that will return a valid report is 46 (1,836,311,903) and this is technically the 47th Fibonacci number since zero was skipped.

Golfed:

($b=1)..(read-host)|%{$a,$b=$b,($a+$b)};$a

Un-Golfed & Commented:

# Feed integers, from 1 to a user-input number, into a ForEach-Object loop.
# Initialize $b while we're at it.
($b=1)..(read-host)|%{
    # Using multiple variable assignment...
    # ...current $b is put into new $a, and...
    # ...sum of current $b and current $a are put into new $b.
    $a,$b=$b,($a+$b)
};
# When loop exits, output $a.
$a

# Variable cleanup, not included in golfed code.
rv a,b

List Fibonacci numbers - 75

Another derivative of Joey's answer, but with some improvements:

  • Zero is included in the output, as it should be according to OEIS.
  • Goes up to the maximum Fibonacci number that can be handled as uint64 instead of the default int32. (Highest Fibonacci number in uint64 is 12,200,160,415,121,876,738.)
  • Output stops once the maximum value is reached, instead of looping through 'Infinity' or continuously throwing errors.

Golfed:

for($a,$b=0,1;$a+$b-le[uint64]::MaxValue){$a;$a,$b=$b,[uint64]($a+$b)}$a;$b

Un-Golfed & Commented:

# Start Fibonacci loop.
for
(
    # Begin with $a and $b at zero and one.
    $a,$b=0,1;

    # Continue so long as the sum fits in uint64.
    $a+$b-le[uint64]::MaxValue
)
{
    # Output current $a.
    $a;

    # Using multiple variable assignment...
    # ...current $b becomes new $a, and...
    # ...sum of current $b and current $a is forced to uint64 and stored in new $b.
    $a,$b=$b,[uint64]($a+$b)
}

# Output $a and $b one more time.
$a;$b

# Variable cleanup - not included in golfed code.
rv a,b
\$\endgroup\$
5
  • \$\begingroup\$ One thing that bugs me a little in PowerShell: Read-Host always reads interactively and won't pick up things you pipe into the script (or process), whereas $input (which is what I tend to use) only picks up piped input (for obvious reasons; that's how it's defined) but cannot be used interactively. Which means that you can write a PowerShell script that either works interactively or one that works with piped input, but not both at the same time (at least not for golfing). \$\endgroup\$
    – Joey
    Commented Nov 28, 2013 at 20:21
  • \$\begingroup\$ Yeah, and I personally prefer my scripts to be interactive whether the challenge calls for it or not. Wait... Did you just golf the un-golfed code? And not just any part of it, but particularly the bit that's not at all in the golfed code? \$\endgroup\$
    – Iszi
    Commented Nov 28, 2013 at 22:57
  • \$\begingroup\$ I merely optimized it, since Remove-Variable takes a string[]. There is no need to have two calls ;-) \$\endgroup\$
    – Joey
    Commented Nov 29, 2013 at 6:13
  • \$\begingroup\$ I meant to say I found it amusing that of all the code to be optimized, you had to go and fix the bit that wasn't even part of the golfed solution. It's like you had an OCD moment or something. \$\endgroup\$
    – Iszi
    Commented Nov 29, 2013 at 7:25
  • \$\begingroup\$ Sometimes I do ;-). I don't see anything that makes the golfed code smaller either. For an algorithm this simple there aren't many options and range|% is often the shortest (but also the slowest) way. \$\endgroup\$
    – Joey
    Commented Nov 29, 2013 at 7:27
3
\$\begingroup\$

Forth - 38 33 bytes

: f dup . 2dup + 2 pick recurse ;

Generates and prints a Fibonacci series recursively until it runs out of stack space.

Usage:

 1 1 f

Or to generate Fn, where n>=1 (66 bytes):

: f dup 3 < if 1 nip else dup 1- recurse swap 2 - recurse + then ;

Example of usage:

9 f .

output:

34 
\$\endgroup\$
6
  • \$\begingroup\$ It does work, but like I said it doesn't terminate itself. It should generate correct output up until 46! at least, and after that it will just keep on going and output "garbage". And since that online compiler doesn't appear to have any way of halting the execution without clearing the console output it gets pretty hard to see the correct output at the beginning. \$\endgroup\$
    – Michael
    Commented Oct 14, 2015 at 15:23
  • \$\begingroup\$ So it just runs so fast that all I can see is the zeros? \$\endgroup\$
    – mbomb007
    Commented Oct 14, 2015 at 18:39
  • \$\begingroup\$ Right. If you run it in Win32Forth you can scroll up and get it to stay at the top so that you actually can see the correct output for Fn up to n=46. \$\endgroup\$
    – Michael
    Commented Oct 14, 2015 at 19:37
  • \$\begingroup\$ Also, if I'm not mistaken : f over . 2dup + recurse ; is shorter (27 bytes). This way, the first number is printed first, and the numbers are in order on the stack, so we don't need 2 pick. \$\endgroup\$
    – mbomb007
    Commented Oct 14, 2015 at 20:19
  • \$\begingroup\$ Yup, that seems to generate the same sequence as my version. \$\endgroup\$
    – Michael
    Commented Oct 14, 2015 at 20:53
3
\$\begingroup\$

Java, 41 bytes

There are a couple other Java answers here, but I'm surprised nobody has posted this simple one:

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

For an extra byte you can extend the range up to long.

\$\endgroup\$
3
\$\begingroup\$

TeaScript, 4 bytes

F(x)

F(x) //Find the Fibonacci number at the input

Compile online here (DOES NOT WORK IN CHROME). Enter input in the first input field.

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

J, 9 bytes

+/@:!&i.-

Gets the nth Fibonacci number by finding the sums of the binomial coefficients C(n-i-1, i) for i from 0 to n-1.

Also, a short way using 12 bytes to generate the first n Fibonacci numbers is

+/@(!|.)\@i.

It uses the same method as above but works by operating on prefixes of the range [0, 1, ..., n-1].

Usage

   f =: +/@:!&i.-
   f 10
55
   f 17
1597

Explanation

+/@:!&i.- Input: n
        - Negate n
     &i.  Form the ranges [n-1, n-2, ..., 0] and [0, 1, ..., n-1] 
    !     Find the binomial coefficient between each pair of values
+/@:      Sum those binomial coefficients and return
\$\endgroup\$
1
  • \$\begingroup\$ Whoa. Just whoa. \$\endgroup\$ Commented Sep 24, 2016 at 0:38
3
\$\begingroup\$

Javascript, 28 Characters

f=n=>(n<=2)?1:f(n-1)+f(n-2);

Try it here!

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Welcome to PPCG! How about n<3? And do you really need the parentheses around the inequality? You can probably also omit the semicolon. \$\endgroup\$ Commented Mar 25, 2017 at 19:43
  • \$\begingroup\$ @MartinEnder is correct, use f=n=>n<3?1:f(n-1)+f(n-2) for a total of 24 bytes \$\endgroup\$
    – user100690
    Commented Mar 16, 2021 at 10:44
3
\$\begingroup\$

Emojicode, 100 bytes

🐖🔢➡️🚂🍇🍊◀️🐕2🍇🍎🐕🍉🍓🍇🍎➕🔢➖🐕1🔢➖🐕2🍉🍉

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Piet, 17 codels

Not sure how to count this one. There are 17 pixels within the code that count as instructions/control flow modifiers (18 if you count the required NOP to get the color back to the correct cycle for the loop).

Shown here at 20 pixels per codel:

Short Fibonacci in Piet

Explanation in pseudocode:

push 1
push 1
push 1
push 1
out (number)
out (number)
START OF INFINITE LOOP
duplicate
push 3
push 1
roll ; the last three instructions amount to "rotate the top to the third spot once"
add
duplicate
out (number)
END OF INFINITE LOOP

This outputs the Fibonacci sequence (starting with 1,1) without delimiters.

Actual image (way too small to see clearly): SMALLER Fibonacci in Piet

\$\endgroup\$
1
  • \$\begingroup\$ Oh, didn't know there was a convention for this. Was unsure. Will change now. \$\endgroup\$ Commented Sep 13, 2017 at 11:29
3
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ Hmmm... When I posted this (the 60th answer), the question automatically became "community wiki" :( \$\endgroup\$
    – r.e.s.
    Commented Dec 2, 2013 at 13:48
  • 4
    \$\begingroup\$ 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 \$\endgroup\$ Commented Dec 2, 2013 at 13:56
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ Commented Mar 14, 2018 at 16:40
  • \$\begingroup\$ @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.... \$\endgroup\$
    – r.e.s.
    Commented Mar 15, 2018 at 3:28
3
\$\begingroup\$

Lean, 42 35 bytes

7 bytes thanks to Mario Carneiro.

def f:_->nat|(n+2):=f(n+1)+f n|x:=x

Try it online!


Lean is a completely different kind of a programming language: it is a proof-assistant. That means, mathematical theorems can be formalized and proved in Lean, and mathematical objects can be constructed in Lean.

In this case, the auto-generated correctness theorems are (cf tio link):

f.equations._eqn_1 : f 0 = 0
f.equations._eqn_2 : f 1 = 1
f.equations._eqn_3 : ∀ (n : ℕ), f (n + 2) = f (nat.succ n) + f n
\$\endgroup\$
10
  • \$\begingroup\$ I had no idea anyone else knew about Lean. \$\endgroup\$
    – qwr
    Commented Mar 31, 2018 at 17:38
  • \$\begingroup\$ "else" :o ... are you in the lean chat? \$\endgroup\$
    – Leaky Nun
    Commented Mar 31, 2018 at 17:39
  • \$\begingroup\$ No, but the only reason I know it exists is because I know someone who contributed to it \$\endgroup\$
    – qwr
    Commented Mar 31, 2018 at 17:47
  • \$\begingroup\$ @qwr might I know him? \$\endgroup\$
    – Leaky Nun
    Commented Mar 31, 2018 at 17:47
  • \$\begingroup\$ If you know Jeremy Avigad \$\endgroup\$
    – qwr
    Commented Mar 31, 2018 at 17:50
3
\$\begingroup\$

C++, 42 bytes

I haven't read every solution in this challenge, but the leaderboard doesn't have a C++ solution, which is a travesty.

int f(int i){return i-->1?f(i)+f(i-1):!i;}
\$\endgroup\$
1
  • \$\begingroup\$ You can save 1 byte by getting rid of the --, making it f(i-1)+f(i-2) and then (that's where you save the byte) !i can be just i. \$\endgroup\$
    – BrainStone
    Commented Jul 15, 2020 at 8:32
3
\$\begingroup\$

BitCycle, 17 16 bytes

~1~ +
AB~/!
^ +/

Try it online!

Outputs the 0 based sequence. This could be 14 bytes:

~1~+
AB~!
^ +/

Try it online!

But it prints an extra 0 in front of the sequence, which takes a couple of bytes to fix...

There's also a 17 byte solution:

v0<
AB~
~ +\
~  !

Try it online!

Which I like because you can switch between 0-based and 1-based just by changing the 0 on the first line to a 1.

For both solutions, the numbers are infinitely output is in unary 1 bits separated by 0 bits. The -u flag converts the unary numbers to decimal instead, but the TIO tends to cut off the outputting section sometimes, and the last number is always truncated too. There's a bit in the footer to prevent this.

Explanation:

Basically, these solutions only use a single pair of collectors and distinguishes between the two numbers by storing one as unary 1 bits and the other as unary 0 bits.

This starts off with 1 being pushed to the collectors to initialise the sequence.

~ ~    Invert the whole stack
AB~    This basically swaps the values of the two numbers
       Also duplicate a copy downwards and rightwards
       Split the stream into zeroes and ones with the plus
!  /!  Print a single 0 as the separator
^ +/   And add a copy of the 1s to the collector
  ~ +
    !  Print a copy of the 1s to the output

This repeats infinitely, basically executing the pseudocode:

a=0
b=1
while 1:
    oldA = a
    b,a = a,b
    print ','
    a += oldA
    print oldA
\$\endgroup\$
3
\$\begingroup\$

bash pur, 49 chars, third solution

r=0;l=1;echo -e {1..45}" $((r+=l)) $((l+=r))\n";

bash pur, 52 chars, second solution

r=0;l=1;echo -e {1..40}" "$((r+=l))" "$((l+=r))\\n;

former solution (60 chars):

r=0;l=1;for i in {1..40};do((r+=l));((l+=r));echo $r $l;done
\$\endgroup\$
7
  • \$\begingroup\$ Could be written: r=1 l=0;echo -e {,,}{,,}{,,}" $[r+=l] $[l+=r]" \$\endgroup\$ Commented Feb 27, 2019 at 0:08
  • \$\begingroup\$ ... And former version: for((r=1,l=1;l<9**9;r+=l,l+=r)){ echo $r $l;} \$\endgroup\$ Commented Feb 27, 2019 at 0:16
  • 2
    \$\begingroup\$ 34 chars: for((a=1;b+=a;a+=b)){ echo $a $b;} \$\endgroup\$
    – roblogic
    Commented Aug 28, 2019 at 8:56
  • \$\begingroup\$ @F.Hauri: My improved solution is only 1 char longer than yours, with preserving the line oriented output, while your solution doesn't reach the max possible value before integer overrun. \$\endgroup\$ Commented Aug 28, 2019 at 19:27
  • 1
    \$\begingroup\$ @roblogic: In my opinion, negative results are not acceptable, but with a halting condition like for((a=1;b+=a;a+=b)){ echo $a $b;}|head -n46 your code is still 4 characters shorter than mine (improved one) - so why don't you publish your solution as an answer, or did you? \$\endgroup\$ Commented Aug 28, 2019 at 19:32
3
\$\begingroup\$

Flobnar, 19 bytes

@\
#_+_1
!_:.
9>$!,

Try it online!

Generates the sequence with no end, separating each number with a tab.


One year later...

I should probably check if I've already answered a question before I start coding...

Anyway, here's an alternative 19 byter that outputs in the same way, only 1-indexed this time and without the leading tab.

Flobnar, 19 bytes

!\$\@
:>+_,9
+ <>$.

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ +1 for 'I should probably check if I've already answered a question' \$\endgroup\$
    – EdgyNerd
    Commented Aug 29, 2019 at 9:00
3
\$\begingroup\$

Java, 90 characters and just two variables

There was one before with 55 characters, but it used a variable without declaring it and had no output. This one has both and (the actual logic) is shorter. And as a little bonus it looks absolutely horrific code-style-wise and depends on compiler quirks, yay!

interface A{static void main(String[]x){for(int a,b=a=1;;System.out.println(b=a+(a=b)));}}

The special features I used are:

  • Using an interface instead of a class. The program can still be run as normal, but I don't need to write "public" twice. This saves 10 characters
  • Declaring multiple variables at once: int a,b;
  • Initializing multiple variables at once and in the declaration, needs a second a: b=a=1;
  • Everything is done in the for head, the body is empty: for(...);
    The first and third block of for are intended for variable initialization and variable incrementation, but they can hold any commands.
  • The whole logic is inside the output: System.out.println(b=a+(a=b))
  • Just two variables without recursion! This is done by using the way the compiler works: The assignment to b first reads the value of a, then it evaluates the right side of the +, where it reads the value of b and writes it into a, but the left side of the + still has the old value of a that gets added to the value of b after assigning the value of b to a. Then that sum gets written to b while a already holds the old value of b.
    I was lucky that the compiler works this way, because it could also have first evaluated the expression in the brackets, like for example C does, then it just lists all powers of 2 instead of the Fibonacci numbers.

In a dream programming language this would just be: b=a+(a=b

\$\endgroup\$
1
  • \$\begingroup\$ Dammit, referring to this answer just helped me in actually useful code, but I can't upvote it! :D \$\endgroup\$ Commented May 27, 2019 at 21:56
3
\$\begingroup\$

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!

\$\endgroup\$
0
3
\$\begingroup\$

Flurry, 54 bytes

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

This is an anonymous function that takes a number \$n\$ as a Church numeral and pushes \$F_n\$ to the stack as a Church numeral.

It can be tested by invoking the interpreter as follows:

$ ./Flurry -inn -c '<>{<>(){}(<>())}{{}[<>{<>(){}{}[<><<>()>]}{({})}]{{}}}{}' 10
55

Note that this is very slow for large inputs (>30 or so) because Church numeral addition is \$O(n)\$.

Explanation

The basic idea is to loop \$n\$ times and keep track of the smaller number using the stack and the larger number using function parameters, so the function to iterate looks like this:

next = λb. pop() + push(b)

Flurry is mostly combinator-based, and so doesn't really have lambdas. The closest approximation is to write a function that pushes its argument onto the stack (using the {...} monad) and then pops from the stack to read the argument back (using the {} nilad). So the function λx. f x gets represented as:

{ f {} }

However, this translation doesn't work if f depends on the stack, which is true in this case, so we need to use a combinator-based approach instead. Rather than popping using {} directly, we can write an anonymous function that ignores its argument and returns a value popped from the stack:

  λa. pop()
{ <> () {} {} }

Here, <> and () represent the S and K combinators respectively.

Of course, the next thing we do with the popped value is apply it to the successor function <><<>()> to compute addition:

  λa. pop()(suc)
{ <> () {} {} [<><<>()>] }

Now all we need is to write a function that pushes its argument to the stack and returns it unchanged:

  λa. push(a)
{ ({}) }

We can then put these functions together using the S combinator:

  λb. pop() + push(b)
  λb. S (λb. pop()(suc)) (λb. push(b)) b
<> {<>(){}{}[<><<>()>]} {({})}

The main function is responsible for setting up the initial values and calling next the appropriate number of times. In other words, it looks like this:

main = λn. push(0); n (next) (1)

Since we don't care about the return value, we can just use function application to sequence the two actions:

main = λn. push(0) (n (next) (1))

Again, we can't keep lambda variables on the stack because we're already doing stack manipulation, so we'll have to create intermediate functions. First, one that ignores its argument and pushes 0 to the stack:

  λa. push(0)
{ <> () {} (0) }

Second, one that applies its argument to next and 1 (which we can finally use stack lambdas for):

  λa. a next 1
{ {} next 1 }

Again, we can put these together with S:

<> {<>(){}(0)} {{}[next]1}

Substituting the definitions of 0, next, and 1 gives us the final result:

<>{<>(){}(<>())}{{}[<>{<>(){}{}[<><<>()>]}{({})}]{{}}}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Is it some kind of functional brain-flak? :D \$\endgroup\$
    – Bubbler
    Commented Aug 10, 2020 at 23:13
  • \$\begingroup\$ @Bubbler Pretty much. \$\endgroup\$ Commented Aug 10, 2020 at 23:46
  • \$\begingroup\$ Given the git description is "Brain-flak, but functional.", I'd say yes \$\endgroup\$
    – Jo King
    Commented Aug 11, 2020 at 0:52
  • \$\begingroup\$ I just opened a chat room for Flurry. \$\endgroup\$
    – Bubbler
    Commented Aug 12, 2020 at 23:49
3
+100
\$\begingroup\$

Red, 36 bytes

Infinitely outputs the fibonacci sequence. Also see @Razetime's answer for a recursive version which outputs the nth number.

a: b: 1
forever[print a b: a + a: b]

Try it online!

Red, 36 bytes

An alternative 36.

a: 1 b: 0
forever[print b: a + a: b]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

BQN, 17 13 bytes

(non-recursive version)

Edit: -4 bytes thanks to hints from ovs

{⊑+´⊸∾⟜⊏⍟𝕩↕2}

Try it at BQN online REPL


BQN, 17 bytes

(recursive version)

{𝕩>1?+´𝕊¨𝕩-1‿2;𝕩}

Try it at BQN online REPL

\$\endgroup\$
2
  • 1
    \$\begingroup\$ The second version can be simplified if you only keep track of the last two values instead of the entire sequence (one-indexed algorithm: Start with 0‿1 ≡ ↕2; 𝕩-times join sum and first element; Return first value of final pair) \$\endgroup\$
    – ovs
    Commented Dec 28, 2021 at 19:15
  • \$\begingroup\$ @ovs - Thanks for the hints! Much better now. \$\endgroup\$ Commented Dec 28, 2021 at 20:22
3
\$\begingroup\$

Hexagony - 61 bytes, return seperator

))')).............../{\/{\)))/=.(\=.+\\*{/..==..\>{;"!<.({("/

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You know you can use digits for numbers too, right? \$\endgroup\$
    – Jo King
    Commented Jan 9, 2022 at 23:40
3
\$\begingroup\$

rSNBATWPL, 28 bytes

n~cond{n<2}{1}${n- 1}+{n- 2}

Try It Online!

\$\endgroup\$
3
\$\begingroup\$

R, 23 bytes

repeat show(F<-T+(T=F))

Try it online!

Similar to, but shorter than, this answer, prints the sequence indefinitely. Based on this answer to a related challenge. Thanks to Dominic van Essen for some golfs.

\$\endgroup\$
3
\$\begingroup\$

Chocolate, 4 bytes

G+c1

Try it online!

Explanation

G+c1
G     ## Generate an infinite list...
 +    ## With the addition function
  c1  ## Starting from [1, 1]
\$\endgroup\$
1 2
3
4 5
12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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