Fibtraction - Fibonacci but with subtraction [duplicate]

Question

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

Answer 1

Oasis, 4 bytes

c-21

Try it online!

0-indexed.

I saw this language used for a similar challenge once, and immediately I knew I should try it here. Can't say I'm disappointed.

Explanation

   1    a(0) = 1
  2     a(1) = 2
c       a(n) = a(n - 2)
 -                      - a(n - 1)

Answer 2

Python 2, 35 34 bytes

^{-1 byte thanks to ovs!}

f=lambda n:n*(n<3)or f(n-2)-f(n-1)

Try it online!

Answers are 1-indexed. Takes advantage of f(2) and f(1) being equal to their respective inputs.

Answer 3

Javascript, 24 bytes

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

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

for (let i = 1; i <= 20; i++) {
  console.log(f(i))
}

Answer 4

Octave, 27 bytes

0-indexed.

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

Try it online!

Answer 5

x86 Machine Code, 12 bytes

Iterative solution; 0-indexed

31 C0
40
8D 50 01
29 D0
92
E2 FB
C3

The above function takes a single input, n (passed in the ECX register, following Microsoft's fastcall calling convention), and returns the n^th number of the Fibtraction sequence in the EAX register.

The implementation is based on the well-known trick for calculating a Fibonacci number using two variables, which Snowman's answer in Java reminded me of.

Not only is this solution much smaller in size than my first attempt (it even competes with Mathematica using a built-in), it will also be much faster because it is iterative, rather than recursive. Theoretical comp-sci's love for recursion is foiled once more!

Ungolfed assembly mnemonics:

Fibtraction:
   xor  eax, eax
   inc  eax                ; EAX = 1  (XOR+INC are 3 bytes; same as PUSH+POP)
   lea  edx, [eax + 1]     ; EDX = 2  (LEA is 3 bytes; same as PUSH+POP)
Iterate:
   sub  eax, edx           ; EAX = EAX - EDX
   xchg eax, edx           ; swap EAX and EDX
   loop Iterate            ; decrement ECX and keep looping as long as ECX != 0
   ret                     ; return, with result in EAX

Try it online!

A couple of things worth pointing out here…

• We start by loading the constants 1 and 2 into registers. These are our starting values. The standard way, of course, to load constants into registers is mov reg, imm. That's fast, but it takes a whopping 5 bytes to encode. So, for code-golfing purposes, we make use of various other tricks to load values into registers. A 2-byte PUSH that pushes the immediate value onto the stack, followed by a 1-byte POP that pops the value off the top of the stack and into a register, is the workhorse trick—very common and very useful. But, if you are just setting the register to 1, you can do XOR+INC, which is the same 3 bytes. And, if you already have the value you want in a register, then you can build off of it using the magic LEA instruction, which is also only 3 bytes. Both of those tricks are showcased here, since they are more interesting and somewhat faster than the good old PUSH+POP.

• Inside of the body of the loop, we do a pretty neat optimization. The fundamental operation we're doing here is:

  edx = (eax - edx)
  eax -= edx
  

  which would naively be translated to (indeed, this is what most C compilers do):

  sub  eax, edx                              ; 2 bytes
  mov  ebx, edx                              ; 2 bytes
  mov  edx, eax                              ; 2 bytes
  mov  eax, ebx                              ; 2 bytes
  

  or, somewhat better—rewrite the subtraction as addition of a negative so that the operand order can be reversed, allowing the result to end up in the desired register without having to clobber a temporary register (ICC is able to apply this optimization):

  neg  edx                                   ; 2 bytes
  add  edx, eax     ; edx = (eax - edx)      ; 2 bytes
  sub  eax, edx     ; eax -= edx             ; 2 bytes
  

  but I have written it as:

  sub  eax, edx                              ; 2 bytes
  xchg eax, edx                              ; 1 byte
  

  which is conceptually similar to the naive version (only one subtraction is done, then some moves), but much more compact because of the XCHG instruction. This avoids clobbering a register, and decreases the size of the code. (I guess you could have equally well used an XOR to avoid clobbering a register—the famous move-without-a-temporary trick—but XCHG is 1 fewer byte for golfing purposes.)

  Now, to be fair, the MOVs are probably much faster in real-world code, especially on modern processors that can elide moves in the front end via register renaming. Exchanges can't be elided, and aren't known for being particularly fast. If it weren't for register renaming, ICC's code (the add-a-negative approach) would probably be the fastest in the real-world, since it's compact and arithmetic operations are extremely efficient.

• The LOOP instruction. This is an old CISC-style instruction that is equivalent to:

  dec  ecx
  jnz  Label
  

  but is avoided in modern code (and by all compilers) because it's actually slower than the above sequence. It's also less versatile, because it has the ECX register hard-coded as the counter. However, for code-golf purposes, it's great! And since we used a calling convention that passes the parameter in ECX, we don't even have to do anything!

  (If you wanted to use a different calling convention, you'd just have to do a MOV or XCHG at the very top of the function to copy the parameter into ECX; or, you could swap out the LOOP instruction for the expanded form shown above. Either of these would only cost a couple of bytes, maximum, so this optimization isn't really saving us much, but I think it does earn a couple of style points! :-)

Similarly, if you wanted to write this for x86-64, like my original answer, which uses a different calling convention, it would be easy to adapt. Either of these will do it, and both are only 14 bytes:

Fibtraction_64_A          |      Fibtraction_64_B:
   push 1                 |         mov  ecx, edi
   pop  rax               |         push 1
   lea  edx, [rax+1]      |         pop  rax
Iterate:                  |         lea  edx, [rax+1]
   sub  eax, edx          |      Iterate:
   xchg eax, edx          |         sub  eax, edx
   dec  edi               |         xchg eax, edx
   jg   Iterate           |         loop Iterate
   ret                    |         ret

Answer 6

Haskell, 29 26 bytes

Inspired by alephalpha's answer I thought, I'd derive an explicit formula. It's been a while since I did an Eigenvalue decomposition, turns out the explicit formula (even after golfing it down) is longer and fails because of floating point issues.

0-indexed:

(g!!)
g=1:scanl(flip(-))2g

Try it online!

Saved 3 bytes thanks to @Laikoni

Decomposition solution, 48 bytes

There are a couple eigenvector decompositions; the simplest is actually -1-indexed rather than 0-indexed or 1-indexed:

Prelude> map (\n -> ((-1 + sqrt 5)/2)**n + ((-1 - sqrt 5)/2)**n) [0..10]
[2.0,-1.0,3.0,-4.0,7.0,-11.0,18.0,-29.000000000000004,47.0,-76.0,123.0]

Since the (-1 + sqrt 5)/2 term is less than 1, we can absorb that into the needed round at the cost of adding some leading terms,

Prelude> [round$((-1 - sqrt 5)/2)^n|n<-[0..10]]
[1,-2,3,-4,7,-11,18,-29,47,-76,123]

So e.g. one can get to a function by, but this is not much-more golfable and it's 48 bytes:

((1:2: -1:[round$(-(1+sqrt 5)/2)^n|n<-[2..]])!!)

Try it online!

Answer 7

cQuents, 8 bytes

=1,2:y-z

1-indexed. Since cQuents isn't stack based it isn't as terse as Oasis. Prints the whole sequence if no input is given.

Try it online!

Explanation

=1,2      Sequence start equals 1,2
    :     Mode: sequence. Prints the 1-indexed nth term for input n.
     y-z  Each item in the sequence equals the second to last item minus the last item

Answer 8

Jelly, 5 bytes

1_@¡3

0-indexed.

Try it online!

Answer 9

Perl 6, 19 bytes

{(1,2,*-*...*)[$_]}

test it

Expanded:

{  # bare block lambda with implicit parameter ｢$_｣
  (

    1, 2,  # seed the sequence

    * - *  # WhateverCode lambda used to generate the rest of the values

    ...    # keep generating until:

    *      # never stop

  )[ $_ ]  # index into the sequence
}

Answer 10

05AB1E, 7 bytes

3XIFDŠ-

Try it online!

Explanation

3         # push 3
 X        # push 1
  IF      # input times do:
    D     # duplicate top of stack
     Š    # move the copy down 2 spaces on the stack
      -   # subtract top 2 numbers

Answer 11

Mathematica (using a built-in), 18 12 bytes

Several bytes saved by user202729 !

LucasL[2-#]&

Or the same idea without a built-in, for 32 31 30 29 bytes:

Tr[{p=(1+5^.5)/2,1-p}^(2-#)]&

Uses 1-indexing. Try them at the Wolfram sandbox (they don't work in Mathics, unfortunately).

This uses the observation by ETHproductions and user202729 that the sequence is nearly the Lucas numbers (only with alternating sign, or reading backwards). The 29-byte function is the closed formula for the Lucas numbers.

Answer 12

Mathics, 31 bytes

f@1=1
f@2=2
f@x_:=f[x-2]-f[x-1]

-2 thanks to @MartinEnder!

Try it online!

Answer 13

Brainfuck, 51 44 bytes

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

0-indexed, the input is on cell 0 and the output on cell 1.

Output is in two complement format.

_{Per this meta consensus, input for Turing machines may be written to the tape pre-execution, and the contents of the tape post-execution may be used as a Turing machine's output.}

How?

# The tape: I O A B . . .
# I = input, O = output

>+     # O = 1
>++    # A = 2
<<[    
    >[>>+<<-]     # B = O              [ I   0   A   O  ]
    >[<+>>-<-]    # B = B - A, O = A   [ I   A   0  O-A ]
    >[<+>-]<<<    # A = B = O - A      [ I   A  O-A  0  ]
-]     # Repeat I times

Answer 14

PHP, 45 bytes

0-indexed

for($x=1,$y=2;$argn--;)$x=$x-$y=$x-$y;echo$x;

Try it online!

PHP, 46 bytes

1-indexed recursive function

function f($i){return$i<3?$i:f($i-2)-f($i-1);}

Try it online!

Answer 15

Java, 65 61 bytes

Golfed:

n->{int a=1,b=2;for(;n-->0;a-=b)b=a-b;System.out.println(a);}

This uses the standard trick of calculating Fibonacci using only two variables to hold the state, but modified to work with subtraction. I am aware that theoretically, System.out.print() should work here but in practice it is inconsistent with flushing output and sometimes (often enough to be an issue) will literally print nothing using the Oracle JVM.

This function is zero-indexed.

Try it online!

Ungolfed:

public class FibtractionFibonacciButWithSubtraction {

  public static void main(String[] args) {
    for (int i : new int[] { 1, 2, 11, 14, 21, 24, 31 }) {
      f(n -> {
        int a = 1, b = 2;
        for (; n-- > 0; a -= b)
          b = a - b;
        System.out.println(a);
      } , i);
    }
  }

  private static void f(java.util.function.Consumer<Integer> function, int n) {
    function.accept(n);
  }
}

Answer 16

C, 30 bytes

Try Online 1-indexed

s;f(n){s=n>2?f(n-2)-f(n-1):n;}

Answer 17

Pari/GP, 26 bytes

n->([1,2]*[0,1;1,-1]^n)[1]

Try it online!

Answer 18

Common Lisp, 46 bytes

(defun f(n)(if(< n 3)n(-(f(- n 2))(f(1- n)))))

Try it online!

1-indexed, plain recursive solution.

Answer 19

R, 38 bytes

f=function(n)`if`(n<3,n,f(n-2)-f(n-1))

1-indexed solution

Explanation :

The 'if' function has the same syntax as ifelse : ifelse(test, TRUE, FALSE).

In this solution, we create a function f that begins to test if the input n is strictly inferior to 3 (i.e. equals to 1 or 2 ; test part of the 'if'). If its the case, the output is simply the input (TRUE part).

The function otherwise recursively calls itself and outputs the final result (FALSE part)

Answer 20

Mini-Flak, 72 bytes

(1-indexed)

({}(()()())(())[()()()()]){({}(([{}]({})))[({}([{}]{})[({})])][()])}{}{}

Try it online!

The TIO links have more comments, so it is easier to understand.

Answer 21

Charcoal, 34 33 bytes

Ａ¹αＡ²βＦ…²θ¿﹪ι²Ａ⁻βαβＡ⁻αβα⎇﹪Ｉθ²ＩαＩβ

Try it online!

1-indexed. I insist on writing answers in a language with a totally different purpose... Link to the verbose version.

Answer 22

Ruby, 26 bytes

Nothing fancy here, it's just a translation of Python or Javascript solutions :

f=->n{n<3?n:f[n-2]-f[n-1]}

The results are 1-indexed.

Try it online!

Answer 23

x86-64 Machine Code, 29 bytes

Simple recursive solution; 1-indexed

The following is a function written according to the System V AMD64 calling convention that computes and returns the n^th number of the Fibtraction sequence. The sole parameter, n, is passed in the EDI register. The function returns its result in the EAX register.

53
51
89 F9
83 EF 02
7E 10
E8 00 00 00 00
8D 79 FF
91
E8 00 00 00 00
29 C1
91
59
5B
C3

Try it online! _{^{(Hey, I finally figured out how to make TIO work for assembly language! Ignore the ugly boilerplate to print numbers… :-p)}}

Ungolfed assembly mnemonics:

Fibtraction:
   push     rbx           ; preserve original value in EBX
   push     rcx           ; preserve original value in ECX
   mov      ecx, edi      ; preserve original 'n' in ECX
   sub      edi, 2        ; EDI = n - 2
   jle      .Finished     ; if n <= 2, we're done (base case for recursion)
   call     Fibtraction   ; compute f(EDI), which is f(n - 2)
   lea      edi, [rcx-1]  ; EDI = n - 1
   xchg     eax, ecx      ; save result of f(n-2) in ECX (which we can now safely clobber)
   call     Fibtraction   ; compute f(EDI), which is f(n - 1)
   sub      ecx, eax      ; calculate f(n - 2) - f(n - 1)
.Finished:                ; fall through...
   xchg     eax, ecx      ; move result from ECX into EAX
   pop      rcx           ; restore original value to ECX
   pop      rbx           ; restore original value to EBX
   ret                    ; return, with result in EAX

Okay, it's assembly language, so there are no fancy built-ins to help us. But just look at all of those 1-byte opcodes! PUSH, POP, and XCHG are all very handy here.
These XCHG instructions are really just substitutions for register-to-register MOVes. We don't actually need to exchange the values; we just care about a one-way movement. But, although normally MOV reg, reg and XCHG reg, reg are both 2 bytes, there is a special 1-byte encoding for XCHG when one of the operands is the accumulator (EAX). Thus, this substitution saves us a few bytes (at the possible expense of speed).

The only long, ugly instructions are the CALLs, used to invoke the function recursively. (Technically, all of those 0s in the opcodes get replaced by the linker with the function's actual 32-bit relative displacement when the code gets linked, but the resulting binary will be the same size in bytes because this won't change the length of the instruction.) But there isn't really anything we can do to reduce the size. CALL can be emulated as PUSH+JMP, but just the PUSH instruction alone consumes more bytes than CALL!

The recursive nature of this algorithm made it a fun and interesting challenge—to me, at least. It's not very often in the real world that you get to write recursive code! It just isn't an efficient way to do things. (Double recursion leads to exponential complexity! Bleh!) Compilers also do a bad job, in general, optimizing it, so this hand-written assembly is head-and-shoulders above what a C compiler would generate for the naive solution:

int Fibtraction(int n)  { return n <= 2 ? n : f(n-2) - f(n-1); }

(although it has been optimized for size, rather than speed, obviously).

Answer 24

SWI Prolog, 88bytes

Did I hear recursion? Prolog is here!

g(1,1).
g(2,2).
g(X,Y):-A is X-2,g(A,B),C is X-1,g(C,D),Y is B-D.
f(X):-g(X,Y),print(Y).

Try it: SWISH

Answer 25

><>, 17+3 = 20 bytes

43\n;
?!\:@-{1-:}

Try it online!

Input is expected on the stack at the start of the program, so +3 bytes for the -v flag.

Answer 26

Julia, 24 bytes

f(n)=n>2?f(n-2)-f(n-1):n

1-indexed

Try it online!

Answer 27

Fortress 0.1 Alpha, 39 bytes.

f(n)=if n<3then n else f(n-2)-f(n-1)end

The interpreter is archived here (direct download).

This language is old and dead, very dead. (1-indexed: f(1)=1, f(2)=2).

Can be placed into a program like this:

export Executable
f(n)=if n<3then n else f(n-2)-f(n-1)end
run(args) = do
    println(f(3))
end

Does this really need explaining? This is just the definition.

Answer 28

Mathematica, 37 bytes

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

Answer 29

dc, 32 bytes

?3sb1sc[lblcdsb-sc1-d0<d]dsdxlbp

1-indexed.

Try it online!

Explanation

?     # Take input and push it onto the main stack.
3sb   # Push 3 into register "b".
1sc   # Push 1 into register "c".
[     # Begin macro definition.
 lblc # Load the values in registers "b" and "c" onto the main stack.
 dsb  # Duplicate the top-of-stack value and push it into register "b".
 -sc  # Push the difference of the top two values into register "c".
 1-d  # Subtract 1 from the top-of-stack value and duplicate the result.
 0<d  # If the result is greater than 0, execute the macro in register "d".
]     # End macro definition.
dsdx  # Duplicate the macro, push a copy into register "d", and execute the 
      # remaining copy.
lbp   # Output the value stored in register "b".      

Answer 30

VBA, 62 Bytes

Recursive function that takes input, n, as integer and outputs the 1-indexed element of A061084

Function f(n):If n<3Then f=n Else f=f(n-2)-f(n-1):End Function