29
\$\begingroup\$

The Fibtraction sequence (as I call it) is similar to the Fibonacci sequence except, instead of adding numbers, you subtract them.

The first few numbers of this challenge are:

1, 2, -1, 3, -4, 7, -11, 18, -29, 47, -76, 123, -199, 322, -521, 843, -1364...

The sequence starts with 1 and 2. Every next number can be calculated by subtracting the previous number from the number before it.

1
2
-1 = 1 - 2
3  = 2 - (-1) = 2 + 1
-4 = -1 - 3
7  = 3 - (-4) = 3 + 4
...

In other words:

f(1) = 1
f(2) = 2
f(n) = f(n - 2) - f(n - 1)

This is OEIS sequence A061084.

Challenge

Write a program/function that takes a positive integer n as input and prints the nth number of the Fibtraction sequence.

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.
  • Your solution can either be 0-indexed or 1-indexed but please specify which.
  • This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
  • Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
  • Built-in functions that compute this sequence are allowed but including a solution that doesn't rely on a built-in is encouraged.
  • Explanations, even for "practical" languages, are encouraged.

Test cases

These are 0-indexed.

Input      Output

1          2
2          -1
11         123
14         -521
21         15127
24         -64079
31         1860498

That pattern was totally not intentional. :P

This challenge was sandboxed.

Before you go pressing any buttons that do scary things, hear me out. This might be considered a dupe of the regular Fibonacci challenge and I agree, to some extent, that it should be easy enough to port solutions from there. However, the challenge is old and outdated; is severely under-specified; allows for two types of solutions; has answers that don't have easy ways to try online; and in general, is lacking of answers. Essentially, in my opinion, it doesn't serve as a good "catalogue" of solutions.

plz send teh codez

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Note that after the first two terms it devolves into the Lucas sequence with alternating signs. \$\endgroup\$ Jul 8, 2017 at 17:05
  • 2
    \$\begingroup\$ i could close this as a dupe of other Lucas number challenges but not having enough online executable answers is not reason to not be dupe. We could have a discussion about making that challenge clearer but it is still dupe regardless \$\endgroup\$
    – Downgoat
    Jul 8, 2017 at 17:33
  • 8
    \$\begingroup\$ Even if the old Fibonacci challenge has some shortcomings and doesn't serve it's purpose as a catalogue very well, the best solution would be to make a good, canonical Fibonacci challenge, not an almost-Fibonacci challenge, because no one will look for that as a repository of Fibonacci solutions. Before you do though, this should probably be brought up on meta. We've discussed retiring the old Fibonacci challenge a couple of times, and I think Chris said he'd be fine with it, but I'm not sure what to do with all the answers that do work there. \$\endgroup\$ Jul 8, 2017 at 17:37
  • 2
    \$\begingroup\$ Is this exactly similar to the regular Fibonacci sequence? If we say the first term of the Fibonacci sequence is 1, then second is also 1(0th term = 0 + 1). By that logic, this sequence should be 1, -1, 2, -3, 5, -8, 13, ..... \$\endgroup\$
    – cst1992
    Jul 9, 2017 at 6:55
  • 3
    \$\begingroup\$ I voted to close this challenge. If we want to make a proper catalog for the Fibonacci sequence that has a well-defined specification, then I think it should be for the vanilla Fibonacci sequence and not a manipulation of it. The challenge this is a dupe of is a better candidate in my opinion. \$\endgroup\$
    – Poke
    Jul 10, 2017 at 17:34

36 Answers 36

1
2
1
\$\begingroup\$

Braingolf, 22 bytes

[vl1-?!-|l1e2|l0e1|R]v

Try it online!

Why is it so long D:

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

Positron, 63 bytes

a=function{k=$1;if(k>2)then{k=((a@(k-2))-(a@(k-1)))};return k;}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ *aggressive parenthesizing* \$\endgroup\$ Jul 11, 2017 at 17:06
  • 1
    \$\begingroup\$ @totallyhuman It's to get around the 5000000000 bugs lol \$\endgroup\$
    – hyper-neutrino
    Jul 11, 2017 at 17:21
1
\$\begingroup\$

Go, 50 bytes

func f(n int)int{if n>2{n=f(n-2)-f(n-1)};return n}

Try it online!

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

Kotlin, 52 bytes

fun f(n:Int):Int{return if(n<3)n else f(n-2)-f(n-1)}

Try it online!

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

Groovy, 27 26 bytes

f={n->n<3?n:f(n-2)-f(n-1)}

Try it online!

Okay, so I feel like I stumbled upon a great language for golfing. This code is basically what most other answers are doing, if n is lesser than 3, then return n or else return f(n - 2) - f(n - 1). But there are a few cool things about this.

For a language that compiles to the JVM, Groovy is surprisingly terse. Variable declarations need no type definition. Functions (called closures in Groovy) are denoted with the {} syntax. it can be used to refer to the sole argument to the function, which means you don't need to specify the argument name and type. Turns out naming the argument was shorter. Combined with the ternary operator, this code ended up quite golfy for a "practical" language.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Tip: Using it is better if there are 3 or fewer references to it. \$\endgroup\$ Jul 10, 2017 at 20:19
0
\$\begingroup\$

Pyth, 15 bytes

First time doing Pyth. ^^

L?<b3b-y-b2y-b1

Try it online!

Explanation

L?<b3b-y-b2y-b1

L                define a function y that takes an argument b
 ?<b3            if b < 3...
     b           ...return b
      -y-b2y-b1  else return y(b - 2) - y(b - 1)
\$\endgroup\$
1
1
2

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