30
2
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
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
3Note that after the first two terms it devolves into the Lucas sequence with alternating signs. – ETHproductions – 2017-07-08T17:05:26.890
2i 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 – Downgoat – 2017-07-08T17:33:47.523
8Even 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. – Martin Ender – 2017-07-08T17:37:49.750
1Okay, should I write a meta post? I strongly believe we should have a good "repository" of solutions for one of our most basic challenges. – totallyhuman – 2017-07-08T17:40:33.843
2Is 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, ....
. – cst1992 – 2017-07-09T06:55:13.760Yeah, the Fibonacci sequence either starts with 1 and then adds/subtracts (leading to cst1992's solution) or starts with 1,1 (so then goes 0, 1, -1, 2, -3... and is thus also the Fibonacci sequence, albeit delayed by three places). Defining this as starting with 1, 2 seems... dubious. – BlueHairedMeerkat – 2017-07-10T10:49:10.113
3I 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. – Poke – 2017-07-10T17:34:37.023
I marked this as a duplicate to "lock" the question and answers while the Meta question is sorted out. Thanks. – AdmBorkBork – 2017-07-20T12:50:34.583