115
\$\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\$

239 Answers 239

1
\$\begingroup\$

Gogh, 10 bytes

¹Ƥ{Ƥ÷®+Ø}x

Executed from the command line like this:

$ ./gogh "" "¹Ƥ{Ƥ÷®+Ø}x"

Explanation

¹       “ Push two ones to the stack.                 ”
Ƥ       “ Print the TOS.                              ”
{       “ Open a code block.                          ”
 Ƥ      “ Print the TOS.                              ”
 ÷      “ Duplicate the TOS.                          ”
 ®      “ Rotate the stack leftward.                  ”
 +      “ Destructively add the TOS to the STOS.      ”
 Ø      “ Loop all preceding code (within the block). ”
}       “ Close a code block.                         ”
x       “ Execute the TOS.                            ”
\$\endgroup\$
1
\$\begingroup\$

Scratch, 106 characters

This isn't impressive at all but someone had to do it.

scratch blocks

when gf clicked
add[1]to[f v
forever
 add((item[last v]of[f v])+(item((length of[f v])-(1))of[f v]))to[f v

scratchblocks2 render

Fairly bog-standard solution. "f" is a list which starts off empty. Runs as long as you let it.

Since it's not easy to define what is and isn't a "character" in Scratch I've used the forum plugin's formatting. This allows me to cheat off some additional characters (scratchblocks2 is very lenient with dropping closing parenthesis, "end"s, and shaving off whitespace here and there)

\$\endgroup\$
1
\$\begingroup\$

Alpax, 5 bytes (non-competing)

Non-competing since the language postdates the challenge. Code:

⇇+
1¹

Yes, that's right mates. My newest invention, which is more mathematically based than 05AB1E. This language uses a lot of recursion, so be aware. This is a bit like a stack based language, but a little bit different. The elaborated version of the above code is:

a(n) = ⇇+
a(0) = 1, a(1) = 1

Explanation:

⇇ is short for pushing a(n - 1), a(n - 2)
+ adds both functions up.

It then implicitly prints the result of a(n), whereas n is the input.

Uses the Alpax encoding.

\$\endgroup\$
1
\$\begingroup\$

PlatyPar, 7 bytes

0A1wAC+

Try it online!

Explanation:

0A1       ## push first two Fibonacci numbers to stack and print them
    w     ## while last item != 0 (always true)
     A      ## print the most recently calculated Fibonacci number
      C+    ## push the sum of the last two items of the stack

This one is a sequence.

\$\endgroup\$
1
\$\begingroup\$

C#: 83 69 68 66 58 53 51

I used a nasty trinary and recursive lambda expression to achieve this one.

Source: StackOverflow

Func<ulong,ulong> f=null;f=x=>x<2?x:f(x-2)+f(x-1);

Usage:

    public static void Main()
    {
        // Recursive lambda expression...
        Func<ulong, ulong> f = null;
        f = x => (x < 2) ? x : f(x - 2) + f(x - 1);

        Console.WriteLine("Please enter a whole number to obtain the Fibonacci sequence number for:");
        string value = Console.ReadLine();

        long numValue;
        if(UInt64.TryParse(value, out numValue))
            Console.WriteLine(f(numValue));

        Console.WriteLine("Press any key to end the program.");
        Console.ReadKey();
    }
\$\endgroup\$
  • 2
    \$\begingroup\$ You don't have no support negative indices. Also, the "ternary" conditional operator isn't nasty if you use it right. :-) \$\endgroup\$ – Chris Jester-Young Apr 8 '13 at 15:21
  • \$\begingroup\$ That helps, thanks! I don't consider ternaries nasty usually, but in a case like the one I've posted, I would do everything in my power to avoid that getting into a codebase. It gets points for clever/short, but not readable. \$\endgroup\$ – Andrew Gray Apr 8 '13 at 15:28
  • 1
    \$\begingroup\$ lol - I posted mine without ever seeing yours. Funny to see that they're almost identical. :) \$\endgroup\$ – Troy Alford Apr 17 '13 at 17:54
  • 1
    \$\begingroup\$ Yeah, but trying to calculate anything above f(45) will cause either a StackOverflow, or just take forever and some time to calculate. \$\endgroup\$ – Andrew Gray Apr 17 '13 at 18:09
  • 1
    \$\begingroup\$ I don't think you need the parentheses around (n<2) \$\endgroup\$ – Cyoce May 2 '16 at 15:00
1
\$\begingroup\$

Detour, 20 bytes

This one is going for the "infinite sequence" option.

v1vq:$
  $+
p,p^
^ q

Try it online!

Branch 1 takes a number, prints it, adds it with the number from Branch 2, then puts the result in Branch 2
Branch 2 takes a number, feeds it to the addition with branch 1 then puts the original number (not the sum) in Branch 1.

For a better explanation click the link and you'll see it in action.

More "readable" version:

Detour, 267 bytes

:$v  1v   q   # split into branches

          +   # push sum of last 2 fibonacci numbers to branch 2
      {  

  p , p   ^   # print branch 1, merge with branch 3

      }

  ^   q       # push branch 2 into branch 1 for printing and recycling

# 1   2   3

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 23 bytes

22 bytes, plus 1 for -nE instead of -e.

say$.-=$b+=$.*=-1;redo

Hat tip.

\$\endgroup\$
1
\$\begingroup\$

Sesos, 11 bytes (non-competing)

Not in-place, linear memory.

Hexdump:

0000000: ae8583 ef6bc7 045fe7 b907                         ....k.._...

Size   : 11 byte(s)

Try it online!

Assembler

set numin
set numout
add 1,rwd 1,get    ;setup tape
jmp
  fwd 1
  jmp,sub 1,fwd 1,add 1,fwd 1,add 1,rwd 2,jnz
  rwd 1
  sub 1
  jmp,sub 1,fwd 1,add 1,rwd 1,jnz
  fwd 1
jnz
fwd 2
put
\$\endgroup\$
1
\$\begingroup\$

Java, 71 chars

Single number: (Binet formula, considering 1.62 as the golden ratio))

int f(int n){return(Math.pow(1.62,n)-(Math.pow(-1.62,-n))/Math.sqrt(5)}

I know this isn't surprisingly short, however Math is beautiful and this formula is even more!

\$\endgroup\$
1
\$\begingroup\$

Ruby

Ungolfed, 60 bytes

def fib(prev,nxt)
  x = prev + nxt
  puts x
  fib(nxt,x)
end

Golfed, 33 bytes

def f(a,b)x=a+b;puts x;f(b,x)end

Pretty simple to call, use f(first, next).

\$\endgroup\$
  • 1
    \$\begingroup\$ You can still golf it further. Try taking out the unnecessary whitespace. Also, there are some good tips here \$\endgroup\$ – DJMcMayhem Sep 12 '16 at 5:14
  • 1
    \$\begingroup\$ x=a+b;puts x can become puts x=a+b \$\endgroup\$ – Cyoce Dec 11 '16 at 3:26
1
\$\begingroup\$

Java 8 29 bytes

Using Java 8 lambdas. This is a valid statement if there exists a function interface with a method that returns an int and takes an int as a parameter. Also the variable that stores the lambda must be declared as a member (static or non static) of the class it is in so that it can be used recursively.

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

Ungolfed:

@FunctionalInterface interface F
{
    int f(int n);
}

public class Main
{
    static F f;

    public static void main(String[] args)
    {
        f=n->n<2?0:f.f(n-1)+f.f(n-2);
    }
}
\$\endgroup\$
1
\$\begingroup\$

Prismatic, 113 bytes (can be smaller)

right wideness wideness left forward up vertex longness backward right vertex tallness forward down vertex vertex

Inspired by Brainfuck, Cubix and Hexagony.

\$\endgroup\$
1
\$\begingroup\$

Forth, 27 bytes

Prints them forever (until it exceeds the maximum integer).

: f over . 2dup + recurse ;

Try it online

Returns the nth Fibonacci number. This assumes I can leave garbage on the stack (the result is still on top), 30 bytes:

: f 1 0 rot 0 DO 2dup + LOOP ;

Try it online

\$\endgroup\$
1
\$\begingroup\$

bc, 21

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

The trailing newline is significant.

Outputs the entire sequence. bc has arbitrary precision arithmetic, so this continues forever.

\$\endgroup\$
1
\$\begingroup\$

Alice, 11 bytes

This was a collaborative golfing effort with Sp3000.

1 \ O
,+{.3

Try it online!

This prints the Fibonacci sequence indefinitely, starting from 1,1, one integer on a line. Unfortunately, it's horrible in terms of memory, because it leaks one stringified copy of each number in the sequence. The things you do for bytes...

Explanation

1   Push 1 to initialise the sequence. There's already an implicit zero underneath.
\   Reflect to NE. Switch to Ordinal.
    Immediately reflect off top boundary, move SE.

    The remainder of the program runs in an infinite loop. At this point of the loop
    there's the current number F_n of the sequence on top of the stack, and the 
    previous number F_n-1 is below.

                                                            Stack:
                                                            [... F_n-1 F_n] 
.   Implicitly convert F_n to a string and duplicate it.    [... F_n-1 "F_n" "F_n"]
    Reflect off bottom boundary, move NE.
O   Output F_n with a trailing linefeed.                    [... F_n-1 "F_n"]
    Reflect off top right corner, move back SW.
.   Make another copy of F_n. (We don't need this one.)     [... F_n-1 "F_n" "F_n"]
    Reflect off bottom boundary, move NW.
\   Reflect to S. Switch to Cardinal.
{   Turn 90 degrees left, i.e. east.
.   Implicitly convert F_n to an integer and duplicate it.  [... F_n-1 "F_n" F_n F_n]
3   Push 3.                                                 [... F_n-1 "F_n" F_n F_n 3]
,   Pull up the third stack element, which is F_n-1.        [... "F_n" F_n F_n F_n-1]
+   Add F_n and F_n-1.                                      [... "F_n" F_n F_n+1]  
{   Turn 90 degrees left, i.e. north.
\   Reflect to SE. Switch to Ordinal.

    After this point, the loop repeats.
\$\endgroup\$
1
\$\begingroup\$

Taxi, 864 bytes

1 is waiting at Starchild Numerology.1 is waiting at Starchild Numerology.Go to Starchild Numerology:W 1 L 2 R 1 L 1 L 2 L.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to Cyclone.Go to Sunny Skies Park:W 1 R.[a]Go to Cyclone:N 1 L.Pickup a passenger going to The Babelfishery.Pickup a passenger going to Addition Alley.Go to Fueler Up:N 2 R, 2 R.Go to The Babelfishery:S.Pickup a passenger going to Post Office.Go to Post Office:N 1 L 1 R.Go to Sunny Skies Park:S 1 R 1 L 1 R.Pickup a passenger going to Cyclone.Go to Cyclone:N 1 L.Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Go to Addition Alley:N 2 R 1 R.Pickup a passenger going to Sunny Skies Park."," is waiting at Writer's Depot.Go to Writer's Depot:N 1 L 1 L.Pickup a passenger going to Post Office.Go to Sunny Skies Park:N 2 R.Switch to plan "a".

Try it online!

Ungolfed:

1 is waiting at Starchild Numerology.
1 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 1st left 2nd right 1st left 1st left 2nd left.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to Cyclone.
Go to Sunny Skies Park: west 1st right.
[a]
Go to Cyclone: north 1st left.
Pickup a passenger going to The Babelfishery.
Pickup a passenger going to Addition Alley.
Go to Fueler Up: north 2nd R, 2nd right.
Go to The Babelfishery: south.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st left 1st right.
Go to Sunny Skies Park: south 1st right 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left.
Pickup a passenger going to Addition Alley.
Pickup a passenger going to Cyclone.
Go to Addition Alley: north 2nd right 1st right.
Pickup a passenger going to Sunny Skies Park.
"," is waiting at Writer's Depot.
Go to Writer's Depot: north 1st left 1st left.
Pickup a passenger going to Post Office.
Go to Sunny Skies Park: north 2nd right.
Switch to plan "a".
\$\endgroup\$
1
\$\begingroup\$

Braingolf, 23 bytes

1!_# @.!_[# @!+!_<1+>];

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 17 bytes \$\endgroup\$ – Skidsdev Jun 16 '17 at 9:20
  • \$\begingroup\$ 14 bytes \$\endgroup\$ – Skidsdev Jun 16 '17 at 9:23
  • \$\begingroup\$ 8 bytes for output the nth number \$\endgroup\$ – Skidsdev Jun 16 '17 at 9:35
1
\$\begingroup\$

Joy, 45 bytes

DEFINE f ==[2<][][[1 - f][2 - f]cleave+]ifte.

Try it online! Zero-indexed. Example usage: 6 f yields 8.

[2<]                         ifte . if the top stack element is less than two  
    []                            . then do nothing
      [              cleave ]     . else duplicate the element and apply two functions
                           +      . and sum the results
       [1 - f][2 - f]             . where the functions compute the two previous Fibonacci numbers

Alternative (same byte count):

DEFINE f ==[2<][][dup 1 - f swap 2 - f+]ifte.
\$\endgroup\$
1
\$\begingroup\$

cQuents, 6 bytes

=1:z+y

Try it online!

This works both with and without input - it prints the sequence without input, and the nth item (1-indexed) with input n.

For 0, 1, 1, ... version, 8 bytes:

=0,1:z+y

Try it online!

Explanation

=1      Set first item in sequence to 1
  :     Mode: Sequence 1 (prints sequence with no input, or nth item with input n
   z+y  Each term equals the previous two terms added together (defaults to 0)

I really, really like the way this language is going :)

\$\endgroup\$
  • \$\begingroup\$ Note current version uses Z and Y instead of z and y \$\endgroup\$ – Stephen Feb 1 at 4:54
1
\$\begingroup\$

ReRegex, 50 bytes.

(0+),(0+):0/$1,$2,$1$2:/.*?(0+),0+:$/$1/0,0:#input

0 indexed. Takes input and gives output via Unary.

Try it online!

About the Program

ReRegex was designed to be much like an advanced version of ///. It offers the same very basic concept of repeatedly doing string match and replace operations. However, that's where the similarities end. ReRegex instead uses a list of match and replace operations, separated by /s, to perform in a loop, and the original string to effect. The Regexes will continue being performed on the original string until a constant state is achieved, at which point the program will dump the string to STDOUT.

This program in particular is just 2 regular expressions and then the input with some default values.

(0+),(0+):0  -> $1,$2,$1$2:
.*?(0+),0+:$ -> $1

And the input is formatted with;

0,0:#input

ReRegex defaultly replaces #input with whatever is passed to the program on STDIN.

For an example, let's say 00000 is passed to STDIN. First, the "Memory" looks like this:

0,0:00000

In the first loop, the regex (0+),(0+):0 is matched, the replace then creates the next itteration of the fibonnachi sequence.

0,0,00:0000

And in doing so, it also pops one of the 0's off, which is why :0 is at the tail end of the match, but not the replace. This then happens 4 more times in a row.

0,0,00,000,00000,00000000,0000000000000:

Now that first regex doesn't match, as there's no more :0 at the end, so we're almost at a stable end point. Now that there's nothing after :, .*?(0+),0+:$ matches, and all it does is clear all data but the second last group of 0s.

00000000

Now, nothing else matches, so it's outputted.

\$\endgroup\$
1
\$\begingroup\$

Joy, 28 bytes

[2<][][1 - dup 1 -][+]binrec

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Husk, 7 2 bytes (non-competing)

İf

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Forth, 39 36 bytes

0 1 : f BEGIN 2DUP + ROT . AGAIN ; f

Explanation

First 0 and 1 are pushed to the stack. Then starts an endless loop where 2DUP duplicates the top two stack items which are then summed with +. At this point stack is 0 1 1. Then the bottom item of the stack is moved on top with ROT. . prints and removes the item on the top of the stack. Creates an endless sequence of Fibonacci numbers.

Had to check out what's Forth about. And is there a better way to learn than trying to golf Fibonacci series. I see that there's already an answer with Forth but desided to post anyway. At least this is a different approach.

\$\endgroup\$
1
\$\begingroup\$

Proton, 24 bytes

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

Try it online!

(Not working on TIO yet; waiting for pull)

The @ is not necessary but it enables caching for the lambda which makes it considerably faster (as in, it actually finishes in a reasonable amount of time). That being said, when I tried computing it up to 10000 (which I needed to increase sys.setrecursionlimit to do), it gave me a Segmentation Fault because the program ran out of memory (Proton is very inefficient) :P

\$\endgroup\$
  • \$\begingroup\$ Polyglot with ES6. \$\endgroup\$ – Zacharý Aug 12 '17 at 21:54
  • \$\begingroup\$ @Zacharý Huh that's cool. This is weird; Proton is often a polyglot with Python too :P \$\endgroup\$ – HyperNeutrino Aug 13 '17 at 0:51
1
\$\begingroup\$

C, 224 229 227 chars

...prints the n'th fibonacci or 2^n

Golfed up:

#import <Foundation/Foundation.h>
typedef unsigned long long f;f main(int c,char*v[]){f n=strtoull(v[1],(char**)v[2],10)-1;f x=(c>2&&++n==0)?0:1;f y=0;while(n--!=0&&x+y>=x&&x>0){f z=x;c>2?x+=y=z:(x+=y,y=z);}printf("%llu\n",x);}

Readable:

#import <Foundation/Foundation.h>
typedef unsigned long long f;
f main(int c,char*v[]){
    f n=strtoull(v[1],(char**)v[2],10)-1;
    f x=(c>2&&++n==0)?0:1;
    f y=0;
    while(n--!=0&&x+y>=x&&x>0){
        f z=x;
        c>2?x+=y=z:(x+=y,y=z);
    }
    printf("%llu\n",x);
}

If the number exceeds the length of an unsigned long long it will print the highest it can get. Return type is f (unsigned long long) for short code, it does generate 2 compiler warnings and a note but it still compiles!

It also has the option to calculate 2^n because it initially printed that.

Usage:

  • ./fibbin 42 - prints 42'th fibonacci number (267914296)
  • ./fibbin 42 anyInputHere - prints 2^n (4398046511104).

Don't enter values of 0, higher than 93 (fibonacci) or higher than 63 (2^n).

Examples:

  • ./fibbin 1 = 1
  • ./fibbin 2 = 1
  • ./fibbin 3 = 2
  • ./fibbin 4 = 3
  • ./fibbin 42 = 267914296
  • ./fibbin 92 = 7540113804746346429
  • ./fibbin 93 = 12200160415121876738 - this is the highest i can go
  • ./fibbin 94 = should be 19740274219868223167, but it doesn't fit into an unsigned long long so i will print #93

  • ./fibbin 1 bin - 2

  • ./fibbin 2 bin - 4
  • ./fibbin 3 bin - 8
  • ./fibbin 4 bin - 16
  • ./fibbin 42 bin - 4398046511104
  • ./fibbin 62 bin - 4611686018427387904
  • ./fibbin 63 bin - 9223372036854775808 - this is the highest i can go
  • ./fibbin 64 bin - should be 18446744073709551616, but it doesn't fit into an unsigned long long so i will print 0

These tests match the output of wolfram-alpha, due to the heavy calculations wolfram may time out but it generally doesn't.

\$\endgroup\$
  • \$\begingroup\$ I'm no C expert but I think n--!=0&&... can be replaced with n--&&... \$\endgroup\$ – Cyoce May 2 '16 at 15:17
1
\$\begingroup\$

Element, 12 (option two) or 11 (option one)

I've decided to go back in time and answer some classic golfing questions with Element to give it some more street cred.

The following code prints out the Fibonacci sequence continuously (it overflows rather quickly). Each number is printed separately, although there is no whitespace separation.

1!{4:`~2@+}
1            push 1 onto the stack
 !           flip the empty control stack to 1 to enable looping
  {       }  infinite while loop
  {4:     }  have 4 copies (3 additional) of the newest number on the stack
  {  `    }  output one copy
  {   ~   }  A fancy way to get zero from a copyusing the variable retrieval function
  {    2~ }  Move one copy from position 0 to position 2 (behind the old number)
  {      +}  add the number to the old number

The following code inputs a number and outputs the Nth number in the sequence (0-indexed).

1_'[3:~2@+]`
1             push a 1
 _'           take input then move it to the control stack
   [      ]   FOR loop
   [3:    ]   make two additional copies of the top number (3 is the total count)
   [  ~   ]   turn one copy into a zero
   [   2@ ]   move from position 0 to position 2, behind the old number
   [     +]   add the old and newer number
           `  output the result 

For completion's sake, here is a link to the interpreter.

\$\endgroup\$
1
\$\begingroup\$

Recursiva, 16 bytes

<a3:1!+#~a$#~~a$

Try it online!

Explanation:

<a3:1!+#~a$#~~a$
<a3:1            - If a<3 then 1
     !           - Else
      +          - Sum
       #~a$      - Call Self but with parameter a-1, will be replaced by result
           #~~a$ - Call self but with parameter a-2, will be replaced by result      
\$\endgroup\$
1
\$\begingroup\$

Chip-8, 36 bytes

6301 'LD v3,1
6D05 'LD vD,5
6E0A 'LD vE,A
8344 'ADD v3,v4
A200 'LD I,200
F333 'LDD [I],v3
8343 'XOR v3,v4
8433 'XOR v4,v3
8343 'XOR v3,v4
F265 'LD v2,[I]
F029 'LDF I,v0
00E0 'CLS
DFF5 'DRW vF,vF,5
F129 'LDF I,v1
DDF5 'DRW vD,vF,5
F229 'LDF I,v2
DEF5 'DRW vE,vF,5
1206 'JMP 206

Displays Fibonacci numbers (up to 233) in decimal. (It might be shorter to use hexadecimal, but I think that's cheating)

This one writes the numbers into memory:

6001
A300
8014
F055
8013
8103
8013
1204

... but it's actually longer than valid numbers it writes:

01 01
02 03
05 08
0D 15
22 37
59 90
E9 79 (overflow)
\$\endgroup\$
1
\$\begingroup\$

Cy, 11 + 1 (-p flag) = 12 bytes (non-competing)

This is going for the infinite stream

0 1 $&+ &do

(the -p flag implicitly prints every non-block value pushed to the stack)

Literally,

  • push 0
    • print it
  • push 1
    • print it
  • forever
    • push the sum of the last two items
    • print it



Without the -p flag semi-cheat:

Cy, 24 bytes

0 &:< 1 &:< {&+ &:<} &do
\$\endgroup\$
1
\$\begingroup\$

J-uby, 8 6 bytes

:++2.*

In J-uby, + on a proc (or a symbol in this case, as symbols can be used as procs in J-uby), defines a recurrence relation. It takes a starter array, and then produces a function that takes n, and then applies itself to the starter array n times, pushing the result to the end and removing the first element. Naturally :+ + [0,1] is a recurrence relation that starts with elements 0, 1 and adds them together n times.

2.* is shorthand for [0,1]

\$\endgroup\$

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.