30
\$\begingroup\$

The Fibonacci sequence is a fairly well known thing around here. Heck, it even has its own tag. However, for all that, we sure like to stick to our roots of 1, 1, ... (or is it 0, 1, ...? We may never know...). In this challenge, the rules are the same, but instead of getting the nth item in the Fibonacci sequence, you will get the nth item in the Fibonacci-esque sequence starting with x, y, ....

Input

Three integers, in whatever order you want. n is the index (0 or 1 indexed) of term in the sequence for your output. x and y are the first two items in your current program run's Fibonacci sequence.

Output

The nth term in the Fibonacci sequence starting with x, y.

Test Cases

(0-indexed)

n   x     y     out
5   0     0     0
6   0     1     8
6   1     1     13
2   5     5     10
10  2     2     178
3   3     10    23
13  2308  4261  1325165
0   0     1     0
1   0     1     1

(1-indexed)

n   x     y     out
6   0     0     0
7   0     1     8
7   1     1     13
3   5     5     10
11  2     2     178
4   3     10    23
14  2308  4261  1325165
1   0     1     0
2   0     1     1

Caveats

Assume 0 <= x <= y.

Please note your input order (must be constant).

\$\endgroup\$
14
  • \$\begingroup\$ Can we take a list as input? \$\endgroup\$ May 17, 2017 at 14:41
  • \$\begingroup\$ @BusinessCat you mean like [1, 2, 3]? Yes. Whatever you need to accept 3 integers. \$\endgroup\$
    – Stephen
    May 17, 2017 at 14:42
  • \$\begingroup\$ @StephenS How about taking an input as n,[x,y] where n is a number and x and y are numbers in a list? That's probably being a little too flexible though ;) \$\endgroup\$
    – Tom
    May 17, 2017 at 14:54
  • 1
    \$\begingroup\$ @CAD97 I'll add them, I had forgotten about them :) \$\endgroup\$
    – Stephen
    May 17, 2017 at 17:48
  • 1
    \$\begingroup\$ Related \$\endgroup\$
    – xnor
    May 17, 2017 at 22:55

51 Answers 51

18
\$\begingroup\$

Jelly, 3 bytes

+¡ạ

Takes x, y, and n (0-indexed) as separate command-line arguments, in that order.

Try it online!

How it works

+¡ạ  Main link. Left argument: x. Right argument: y. Third argument: n

  ạ  Yield abs(x - y) = y - x, the (-1)-th value of the Lucas sequence.
+¡   Add the quicklink's left and right argument (initially x and y-x), replacing
     the right argument with the left one and the left argument with the result.
     Do this n times and return the final value of the left argument.
\$\endgroup\$
0
11
\$\begingroup\$

CJam, 14 9 bytes

l~{_@+}*;

Try it online!

Input format is "x y n". I'm still a noob at this, so I'm 100% sure there are better ways to do this, but please instead of telling me "do this" try to only give me hints so that I can find the answer myself and get better. Thanks!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ ririri can be shortened to 2 bytes. fI can be shortened to 1 byte. \$\endgroup\$
    – Dennis
    May 17, 2017 at 14:54
  • 6
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ May 17, 2017 at 14:54
  • \$\begingroup\$ @Dennis improved! Thank you! And thanks for the welcome. \$\endgroup\$
    – FrodCube
    May 17, 2017 at 15:04
9
\$\begingroup\$

Python 2, 37 bytes

f=lambda x,y,n:n and f(y,x+y,n-1)or x

Try it online!

0-indexed, you may need to adjust the recursion limit for n≥999

\$\endgroup\$
9
\$\begingroup\$

JavaScript (ES6), 27 26 bytes

Nothing fancy here, just a standard JS Fibonacci function with the initial values of 0 & 1 removed.

n=>g=(x,y)=>n--?g(y,x+y):x

Try it

f=
n=>g=(x,y)=>n--?g(y,x+y):x
o.value=f(i.value=13)(j.value=2308,k.value=4261)
oninput=_=>o.value=f(+i.value)(+j.value,+k.value)
*{font-family:sans-serif;}
input{margin:0 5px 0 0;width:50px;}
#o{width:75px;}
<label for=i>n: </label><input id=i type=number><label for=j>x: </label><input id=j type=number><label for=k>y: </label><input id=k type=number><label for=o>= </label><input id=o>

\$\endgroup\$
6
\$\begingroup\$

Python 2, 40 bytes

0-indexed
Try it online

n,a,b=input()
exec'a,b=b,a+b;'*n
print a
\$\endgroup\$
2
  • \$\begingroup\$ Haha not subject to a recursion/stack limit unlike some other answers. Nice trick. \$\endgroup\$ May 19, 2017 at 4:16
  • \$\begingroup\$ @ShreevatsaR Thanks! But recursive lambda beats me anyway :D \$\endgroup\$ May 19, 2017 at 8:17
5
\$\begingroup\$

Haskell, 30 bytes

x#y=(f!!)where f=x:scanl(+)y f

Try it online! 0-indexed. Use as (x#y)n, e.g. (0#1)5 for the fifth element of the original sequence.

The most likely shortest way to get the Fibonacci sequence in Haskell is f=0:scanl(+)1f, which defines an infinite list f=[0,1,1,2,3,5,8,...] containing the sequence. Replacing 0 and 1 with arguments x and y yields the custom sequence. (f!!) is then a function returning the nth element of f.

\$\endgroup\$
5
\$\begingroup\$

Mathematica, 36 bytes

LinearRecurrence[{1,1},{##2},{#+1}]&

input

[n,x,y]

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can use ##2 instead of #2,#3. \$\endgroup\$
    – alephalpha
    May 18, 2017 at 8:45
  • \$\begingroup\$ very nice! fixed! \$\endgroup\$
    – ZaMoC
    May 18, 2017 at 8:58
5
\$\begingroup\$

PowerShell, 40 bytes

$n,$x,$y=$args;2..$n|%{$y=$x+($x=$y)};$y

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Brain-Flak, 38 bytes

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

Try it online!

{({}[()]<                      >)}     # For n .. 0
         (({}<>)<>            )        # Copy TOS to the other stack and add it to...
                  {}                   # The second value
                    <(<>{}<>)>         # Copy what was TOS back
                                  {}{} # Pop the counter and the n+1th result
\$\endgroup\$
4
\$\begingroup\$

Ruby, 27 bytes

->a,b,n{n.times{b=a+a=b};a}
\$\endgroup\$
3
\$\begingroup\$

Jelly, 6 bytes

;SḊµ¡I

Try it online!

Explanation

   µ¡  - repeat n times (computes the n+1th and n+2th element):
 S     -  take the sum of the elements of the previous iteration (starting at (x,y))
;      -  append to the end of the previous iteration
  Ḋ    -  remove the first element
     I - Take the difference of the n+1th and n+2th to get the n-th.
\$\endgroup\$
3
\$\begingroup\$

TAESGL, 4 bytes

ēB)Ė

1-indexed

Interpreter

Explanation

Input taken as n,[x,y]

 ēB)Ė
AēB)     get implicit input "A" Fibonacci numbers where "B" is [x,y]
    Ė    pop the last item in the array
\$\endgroup\$
3
\$\begingroup\$

Prolog (SWI), 77 bytes

f(N,Y,Z):-M is N-1,f(M,X,Y),Z is X+Y.
l(N,A,B,X):-asserta(f(0,A,B)),f(N,X,_).

Try it online!

Started off golfing Leaky Nun's answer and arrived at something completely different.

This one has a rule for (Nᵗʰ, (N+1)ᵗʰ) in terms of ((N-1)ᵗʰ, Nᵗʰ) and uses database management to assert 0ᵗʰ and 1ˢᵗ elements at runtime.

f(N,X,Y) means Nᵗʰ element is X and (N+1)ᵗʰ element is Y.

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

R, 39 bytes

f=function(x,y,n)'if'(n,f(y,x+y,n-1),x)

A simple recursive function. Funnily enough this is shorter than anything I can come up with for the regular Fibonacci sequence (without built-ins), because this doesn't have to assign 1 to both x and y =P

Calculates n+1 numbers of the sequence, including the initial values. Each recursion is calculates with n-1 and stopped when n==0. The lowest of the two numbers is then returned, giving back the n-th value.

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

Octave, 24 bytes

@(n,x)(x*[0,1;1,1]^n)(1)

Input format: n,[x,y].

Try it online!

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

Prolog (SWI), 85 bytes

l(0,X,Y,X).
l(1,X,Y,Y).
l(N,X,Y,C):-M is N-1,P is N-2,l(M,X,Y,A),l(P,X,Y,B),C is A+B.

Try it online!

0-indexed.

\$\endgroup\$
2
  • \$\begingroup\$ Could you edit this answer? I seem to have accidentally downvoted it the day you posted it. \$\endgroup\$ Apr 21, 2018 at 22:29
  • 1
    \$\begingroup\$ @EsolangingFruit done \$\endgroup\$
    – Leaky Nun
    Apr 21, 2018 at 22:30
3
\$\begingroup\$

x86 machine code, 7 bytes

EDX = x = fib[1], EAX = y = fib[2], RCX = n (1-indexed)
returns in EAX. Works in all 3 modes (16, 32, and 64).
Try it online! (64-bit NASM source with a _start that parses 3 integers from argv strings)

0000000000401070 <cfib>:
  401070:       eb                      .byte 0xeb      # jmp rel8 consuming the 01 add opcode as a rel8
0000000000401071 <cfib.loop>:
  401071:       01 d0                   add    eax,edx
# loop entry point on first iteration, jumping over the ModRM byte of the ADD
  401073:       92                      xchg   edx,eax
  401074:       e2 fb                   loop   401071 <cfib.loop>
  401076:       c3                      ret 

This "jumps" into the loop with machine code that decodes 2 different ways: with a jmp +1 when falling into the loop from the top of the function, or with that 01 byte being an ADD opcode when the loop instruction jumps backwards. Equivalent to jmp .entry but with only 1 byte outside the loop instead of 2.

(Credit to @Ira Baxter for pointing out the general idea of falling into a loop with 1 byte outside that consumes some loop bytes to do something different on the first iteration, e.g. the opcode for cmp al, imm8 as a 1-byte encoding for a jump forward by 1. I got lucky that 01 add could be consumed by jmp rel8 to skip a total of 2 bytes without needing a 66 prefix for cmp ax, imm16 or being in 16-bit mode. 01 or 03 add didn't work well as a modrm for anything like add r/m32, imm8; we need to avoid a memory operand. Note that this trick is not good for performance on some modern CPUs, e.g. AMD that caches instruction boundaries in L1i tags, and probably not newer Intel/AMD with uop caches.)

Stripping labels lets objdump decode as the CPU would on the first pass:

cfib:
  401070:       eb 01                   jmp    0x401073   # jmp rel8 = +1
  401072:       d0                      .byte 0xd0        # jumped over
  401073:       92                      xchg   edx,eax
  401074:       e2 fb                   loop   0x401071
  401076:       c3                      ret    

It's easy to see that the EDX input will be the EAX return value for ECX=1 (exit right away, loop is never taken so add never runs).

Use strace ./custom-fib 14 2308 4261 to see the full integer value passed to the exit() system call before truncation to an 8-bit exit status.

In 32-bit mode, the same machine code is callable with GCC regparm(3) calling convention as __attribute__((regparm(3))) unsigned custom_fib(unsigned y /*eax*/, unsigned x /*edx*/, unsigned n /*ecx*/);, returning in EAX as usual.


Without the 2-way decode hack: x86 machine code, 8 bytes

0-indexed n in RCX, x (fib[0]) in EAX, y (fib[1]) in EDX - note opposite arg order

0000000000401070 <cfib>:
  401070:       e3 05                   jrcxz  401077 <cfib.done>
0000000000401072 <cfib.loop>:
  401072:       0f c1 c2                xadd   edx,eax
  401075:       e2 fb                   loop   401072 <cfib.loop>
0000000000401077 <cfib.done>:
  401077:       c3                      ret    

This way shows off x86's xadd instruction, normally only used with a memory destination and a lock prefix to implement fetch_add.

The reg,reg form of xadd decodes to only 3 uops on Intel Skylake, same as xchg reg,reg (https://uops.info/). (The loop instruction is slow on Intel so this is hardly optimized for speed. If you want a speed-efficient asm implementation, unroll by 2 to remove the xchg as shown in my SO answer using clever loop setup to avoid excess branching for odd vs. even n for standard 0,1 Fibonacci.)

\$\endgroup\$
2
  • 1
    \$\begingroup\$ While it is a neat trick to re-use the 01h as a jump displacement, am I missing anything or could you equally well drop the EBh byte by defining the entrypoint to be within the loop as in codegolf.stackexchange.com/questions/132981/… ? \$\endgroup\$
    – ecm
    Oct 27, 2021 at 22:40
  • 1
    \$\begingroup\$ @ecm: actually yeah, good point, that would get us down to 6 bytes. I often forget about putting the function entry point somewhere after the first byte. I think in this case I'll leave this answer as-is, because I've linked it from a few places as an example of this trick, which is useful if you need something else before the loop, or as part of a larger function. \$\endgroup\$ Oct 28, 2021 at 0:50
3
\$\begingroup\$

Vyxal, 5 bytes

⁽+dḞi

Takes input as [x, y] then n.

Try it online!

Explanation:

   Ḟ   # Create an infinite list from the initial vector [x, y] from:
  d    # a dyadic,
⁽      # single element lambda
 +     # which adds its two arguments.
    i  # Index into that list with the second input (n).
\$\endgroup\$
2
\$\begingroup\$

Python 2, 112 bytes

1-indexed.

import itertools
def f(x,y):
 while 1:yield x;x,y=y,x+y
def g(x,y,n):return next(itertools.islice(f(x,y),n-1,n))

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Erp, too late and too big. \$\endgroup\$ May 17, 2017 at 14:12
2
\$\begingroup\$

dc, 36 bytes

?sdsbsa[lddlb+sdsbla1-dsa1<c]dscxldp

Try it online!

0-indexed. Input must be in the format n x y.

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

PHP>=7.1, 55 Bytes

for([,$n,$x,$y]=$argv;$n--;$x=$y,$y=$t)$t=$x+$y;echo$x;

Online Version

PHP>=7.1, 73 Bytes

for([,$n,$x,$y]=$argv,$r=[$x,$y];$i<$n;)$r[]=$r[+$i]+$r[++$i];echo$r[$n];

Online Version

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Taking advantage of strange PHP's evaluation order: $y=+$x+$x=$y. Also, you can use just $n-- instead of $i++<$n. \$\endgroup\$
    – user63956
    May 19, 2017 at 11:56
2
\$\begingroup\$

Common Lisp, 49 Bytes, 0-indexed

(defun fib(n x y)(if(= 0 n)x(fib(1- n)y(+ x y))))

I'm a Lisp noob so any tips would be appreciated ;)

Explanation:

(defun fib(n x y)                                  | Define a function taking 3 arguments
                 (if(= 0 n)x                       | If n = 0, return x
                            (fib(1- n)y(+ x y))))  | Otherwise, call fib with n-1, y, and x+y
\$\endgroup\$
2
\$\begingroup\$

br**nfuck, 39 29 bytes

Thanks to @JoKing for -10!

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

TIO won't work particularly well for this (or for any BF solution to a problem involving numbers). I strongly suggest @Timwi's EsotericIDE (or implementing BF yourself).

Takes x, then y, then n. 0-indexed. Assumes an unbounded or wrapping tape.

Explanation

,<,<,            Take inputs. Tape: [n, y, x]
[                While n:
  > [->+>+<<]      Add y to x, copying it to the next cell along as well. Tape: [n, 0, x+y, y]
  < [>+<-]         Move n over. Tape: [0, n, x+y, y]
  >-               Decrement n.
] >>.            End loop. Print cell 2 to the right (x for n == 0).
\$\endgroup\$
5
  • \$\begingroup\$ Why do you bother moving x and y when you can just move n? Try It Online \$\endgroup\$
    – Jo King
    Apr 21, 2018 at 23:07
  • \$\begingroup\$ @JoKing Considered that (but longer on my own), but it doesn't quite work, unless OP allows "-1-indexing". \$\endgroup\$ Apr 21, 2018 at 23:35
  • \$\begingroup\$ Oh, just add a > to the end or swap x and y order \$\endgroup\$
    – Jo King
    Apr 21, 2018 at 23:48
  • \$\begingroup\$ @JoKing My palm hit my face quite hard just now. Thanks! \$\endgroup\$ Apr 21, 2018 at 23:53
  • \$\begingroup\$ Why did you bother to censor "brain" but not the second word in the programming language's name? \$\endgroup\$
    – MilkyWay90
    Mar 12, 2019 at 16:51
2
\$\begingroup\$

C (gcc), 29 bytes

f(n,x,y){n=n?f(n-1,y,x+y):x;}

Try it online!

This implementation is 0-based.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice, and welcome! Here's a prettier TIO setup for testing, should you choose to use it. \$\endgroup\$ Apr 22, 2018 at 0:19
2
\$\begingroup\$

MATL, 7 bytes

:"wy+]x

Output is 0-based.

Try it at MATL Online!

Explanation

Let the inputs be denoted n (index), a, b (initial terms).

:"     % Implicitly input n. Do this n times
       %   At this point in each iteration, the stack contains the two most
       %   recently computed terms of the sequence, say s, t. In the first
       %   iteration the stack is empty, but a, b will be implicitly input
       %   by the next statement
  w    %   Swap. The stack contains t, s
  y    %   Duplicate from below. The stack contains t, s, t
  +    %   Add. The stack contains t, s+t. These are now the new two most
       %   recently comnputed terms
]      % End
x      % Delete (we have computed one term too many). Implicitly display
\$\endgroup\$
2
\$\begingroup\$

Braingolf, 15 bytes

VR<2-M[R!+v]R_;

_; is no longer needed on the latest version of Braingolf, however that's as of ~5 minutes ago. This could be 13 bytes by removing that.

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

05AB1E, 9 bytes

`©GDŠ+}®@

Try it online!

Explanation

`           # split inputs as separate to stack
 ©          # store n in register
  G         # n-1 times do
   D        # duplicate top of stack
    Š       # move down 2 places on stack
     +      # add top 2 values of stack
      }     # end loop
       ®@   # get the value nth value from the bottom of stack
\$\endgroup\$
0
1
\$\begingroup\$

Lua, 44 bytes

0-Indexed

n,x,y=...for i=1,n do
x,y=y,x+y
end
print(x)

Try it online!

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

Klein, 18 + 3 bytes

This uses the 000 topology

:?\(:(+)$)1-+
((/@

Pass input in the form x y n.

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

Axiom, 88 57 bytes

f(k,x,y)==(repeat(k<=0=>break;c:=y;y:=x+y;x:=c;k:=k-1);x)

this would pass the test proposed (0 indexed)

(14) -> f(5,0,0)
   (14)  0
                                                 Type: NonNegativeInteger
(15) -> f(6,0,1)
   (15)  8
                                                    Type: PositiveInteger
(16) -> f(2,5,5)
   (16)  10
                                                    Type: PositiveInteger
(17) -> f(10,2,2)
   (17)  178
                                                    Type: PositiveInteger
(18) -> f(3,3,10)
   (18)  23
                                                    Type: PositiveInteger
(19) -> f(13,2308,4261)
   (19)  1325165
                                                    Type: PositiveInteger
\$\endgroup\$

Your Answer

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

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