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

224 Answers 224

1
\$\begingroup\$

APL: 26 characters

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

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

For example,

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

yields the vector:

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

C, 45 (37)

Only because it's easy:

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

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

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

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

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

Befunge, 15 13 characters

1:.:00p+00g\#

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

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

Befunge 98, 10 characters

1:"]"y+#

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

1#;:"]"y+;

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

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

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

1#;:.:"]"y+:0`2*k#@;

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

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

Breakdown:

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

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

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

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

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

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

Ruby, 27

What, no Ruby answers?

p a=b=1;loop{a,b=(p b),a+b}

Prints each number, starting correctly with the first two 1s, to STDOUT ad infinitum (VERY QUICKLY from irb in my environment - you've been warned). I've been learning Ruby lately, so I figured I'd contribute this. If it can be shortened in any way, let me know.

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

Julia - 20 Characters

f=n->([1 1;1 0]^n)[]

I used the same basic algorithm as the Octave answer. This starts with f(0)->1, f(1)->1, to avoid needing an explicit array index. This is 4 characters shorter than the naive recursive algorithm.

f=n->n<2?1:f(n-1)+f(n-2)
\$\endgroup\$
1
\$\begingroup\$

Python 3, 39 38 bytes

a=1
b=1
while 1:c=a+b;print(c);a=c;b=c

Ungolfed:

a = 1
b = 1
while 1:
    c = a + b
    print(c)
    a = c
    b = c

Is there some way of getting rid of the b=c statement?

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Does a=b=c work in Python? (Same for a=b=1.) Also, do you really need the space after :? \$\endgroup\$ – Martin Ender Oct 12 '15 at 13:26
  • \$\begingroup\$ @MartinBüttner It did print the Fibonnaci sequence, and it also showed a weird wavy "animation" :P \$\endgroup\$ – m654 Oct 12 '15 at 14:07
  • \$\begingroup\$ @MartinBüttner Assignments can be chained, just like comparisons, but they don't return a value so you can't do a=1+(b=c). \$\endgroup\$ – lirtosiast Oct 12 '15 at 14:13
  • \$\begingroup\$ This doesn't print the right sequence. It's not hard to fix though. \$\endgroup\$ – Ørjan Johansen Jan 31 at 23:03
1
\$\begingroup\$

Rust, 44 bytes

fn f(n:u8)->u8{if n<2{n}else{f(n-1)+f(n-2)}}
\$\endgroup\$
1
\$\begingroup\$

ArnoldC, 451 bytes

IT'S SHOWTIME
HEY CHRISTMAS TREE a
YOU SET US UP 1
HEY CHRISTMAS TREE b
YOU SET US UP 1
HEY CHRISTMAS TREE c
YOU SET US UP 1
STICK AROUND c
TALK TO THE HAND a
GET TO THE CHOPPER a
HERE IS MY INVITATION a
GET UP b
ENOUGH TALK
TALK TO THE HAND b
GET TO THE CHOPPER b
HERE IS MY INVITATION b
GET UP a
ENOUGH TALK
GET TO THE CHOPPER c
HERE IS MY INVITATION 1e300
LET OFF SOME STEAM BENNET a
ENOUGH TALK
CHILL
YOU HAVE BEEN TERMINATED

This is actually my first ArnoldC program. Horrible for golfing, but great for lolz!

Produces an stream of Fibonacci numbers up to 1.1253474885494065e+274.

Explanation

IT'S SHOWTIME               #start program

HEY CHRISTMAS TREE a        #declare a...
YOU SET US UP 1             #and set it to 1
HEY CHRISTMAS TREE b        #declare b...
YOU SET US UP 1             #and set it to 1
HEY CHRISTMAS TREE c        #declare c...
YOU SET US UP 1             #and set it to 1

STICK AROUND c              #while c is truthy
TALK TO THE HAND a          #output a
GET TO THE CHOPPER a        #assign a to...
HERE IS MY INVITATION a     #a...
GET UP b                    #plus b
ENOUGH TALK                 #end assignment
TALK TO THE HAND b          #output b
GET TO THE CHOPPER b        #assign b to...
HERE IS MY INVITATION b     #b...
GET UP a                    #plus a
ENOUGH TALK                 #end assignment
GET TO THE CHOPPER c        #assign c to...
HERE IS MY INVITATION 1e300 #whether 1e300...
LET OFF SOME STEAM BENNET a #is greater than a (returns 0 or 1)
ENOUGH TALK                 #end assignment
CHILL                       #end while

YOU HAVE BEEN TERMINATED    #end program
\$\endgroup\$
1
\$\begingroup\$

Vitsy, 11 Bytes

I'm certain there's a way to shorten these.

Print out all fibonacci (to Integer.MAX_VALUE)

01[D}+DNaO]
01          Push 0 and 1 to the stack.
  [       ] Repeat infinitely.
   D        Duplicate the top item of the stack.
    }       Rotate the stack to right.
     +      Add the top two items.
      D     Duplicate the top item.
       N    Print the top item out as a number.
        aO  Print a return.

Print out to input fibonacci (13 bytes):

01}\[D}+DNaO]
01            Push 0 and 1 to the stack.
  }\[       ] Get the input and repeat that many times.
     D        Duplicate the top item of the stack.
      }       Rotate the stack to right.
       +      Add the top two items.
        D     Duplicate the top item.
         N    Print the top item out as a number.
          aO  Print a return.
\$\endgroup\$
1
\$\begingroup\$

Minkolang 0.10, 10 bytes

This language was created after this challenge but not for it.

Stream (link, do not click "Run"):

01d1R+dN2@

A mite clever, if I do think so. The 2@ at the end is a 2-trampoline that jumps over the 01 at the beginning, allowing the sequence to rise unabated.

Nth Fibonacci (link):

01nd,7&[d1R+]rN.

Worse than I expected, 16 bytes. 01 sets it up, nd,7&...N. prints out 0 if the input is 0 and does the loop otherwise. [d1R+] builds up the sequence, then r reverses the stack and the correct number is outputted and the program ends with N..

\$\endgroup\$
  • \$\begingroup\$ Grar! Again? You beat me by one again. grumble \$\endgroup\$ – Addison Crump Oct 30 '15 at 20:26
  • \$\begingroup\$ .... ¯\_(ツ)_/¯ \$\endgroup\$ – El'endia Starman Oct 30 '15 at 20:38
1
\$\begingroup\$

ShapeScript, 16 14 bytes

_1@0@'@1?+'*!#

This reads an integer n (in unary) from STDIN and prints the nth Fibonacci number.

The submission is non-competing, since this challenge predates ShapeScript's creation by a few years.

Try it online!

How it works

        Input: a string of n 1's 
_       Get the length of the input to push n.
1@      Swap it with 1 (F[-1]).
0@      Swap it with 0 (F[0]).
        STACK: F[-1]   F[0]   n
'       Push a string that, when evaluated for the i-th time,
        does the following:
  @       Swap F[i-2] on top of F[i-1].
  1?      Push a copy of F[i-1].
  +       Add the copy of F[i+1] to F[i].
'       STACK: F[i-1]   F[i]
*!      Repeat the string n times and evaluate it.
#       Discard F[n] from the stack.
\$\endgroup\$
1
\$\begingroup\$

Brainf*ck, 489 466 characters

Granted, this is a bit overkill, not to mention that it could be optimised a lot. I will get to improving it tomorrow, since it's too late today.

EDIT: Improved by a few bytes by putting stuff closer together on the tape.

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

(With added newlines for readability)

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

Oration, 135 bytes

I believe that this is "optimal"... takes a deep breath here we go!

Inhale
Start a function f with n
If n<2
Return n
Backtracking
Inhale
Here
Literally, f(n-2)+f(n-1)
I'm done
Listen
Invoke f with number

The little ~> is input. This outputs the (input)th Fibonacci number. This transpiles to (in Python):

def f(n):
    if n<2:
        return  n
    return f(n-2)+f(n-1) 
print(f(eval(input("~>"))))
\$\endgroup\$
  • 1
    \$\begingroup\$ Why is the transpiled Python code not golfed D: \$\endgroup\$ – Downgoat Feb 2 '16 at 4:01
1
\$\begingroup\$

beeswax, 12 bytes (sequence), 42 bytes (n-th Fib.)

Beeswax is newer than the question, so no competition here.

Fibonacci sequence.

p{N<P{*
>~+d

No promotion to higher bit widths implemented in my solution, so 64-bit overflow starts at the 93rd or 92nd Fibonacci number, depending if you start counting your sequence at 0 or 1:

0  
1  
1  
2  
3  
5  
8  
13 
21 
34 
55 
89 
.
.
.
4660046610375530309
7540113804746346429
12200160415121876738   ← 93rd Fibonacci number
1293530146158671551    ← 1st. 64-bit overflow/wraparound
13493690561280548289

N-th Fibonacci number:

;{#'<>~P~L#MM@>+@'p@{;
  _TNX~P~K#{; d~@M<

The same limit applies to this solution.

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

CJam, noncompeting, 11 bytes

0X{_@+}q~*;
\$\endgroup\$
  • \$\begingroup\$ F(0) = 0. You should eliminate the backslash. \$\endgroup\$ – Dennis Mar 2 '16 at 15:40
  • \$\begingroup\$ Ah I was assuming that we were starting from 1,1..... so I guess this is a good convention since it saves a byte :) \$\endgroup\$ – A Simmons Mar 2 '16 at 16:18
  • \$\begingroup\$ People start the Fibonacci sequence at different values, so F(0) = 0 may or may not be defined. However, when it comes to indexing, F(1), F(2) = 1, since a lot of the sequence's properties depend on that. \$\endgroup\$ – Dennis Mar 2 '16 at 16:29
1
\$\begingroup\$

DUP, 10 bytes

1$[^^+2!]!

Try it here.

An infinite stream that leaves results on stack. Use the Step button to avoid setting off the infinite loop.

Explanation

1$         {start w/ 2 1's}
  [     ]! {execute lambda}
   ^^      {take top 2 items on stack}
     +     {add them}
      2!   {self recurse!}
\$\endgroup\$
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\$

Python 2, 43 bytes

def f(n):k=9**n;return k**-~-~n/~-(k*~-k)%k
\$\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\$

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.