[Question]
  [
# Definition
* \$a(0) = 0\$
* \$a(n) = n-a(a(a(n-1)))\$ for integer \$n > 0\$
# Task
Given non-negative integer \$n\$, output \$a(n)\$.
# Testcases
```
n     a(n)
0     0
1     1
2     1
3     2
4     3
5     4
6     4
7     5
8     5
9     6
10    7
11    7
12    8
13    9
14    10
15    10
16    11
17    12
18    13
19    13
20    14
10000 6823
```
# References
* [WolframMathWorld](http://mathworld.wolfram.com/HofstadterH-Sequence.html)
* [OEIS A005374](https://oeis.org/A005374)
  
[Answer]
## Haskell, ~~23~~ 22 bytes
```
f 0=0
f n=n-f(f$f$n-1)
```
Simply uses the definition of the sequence. `f(f$f$n-1)` is equivalent to `f (f (f (n-1)))`.
Test:
```
main = putStrLn . show $ map f [0..20]
-- => [0,1,1,2,3,4,4,5,5,6,7,7,8,9,10,10,11,12,13,13,14]
```
Thanks to [Anders Kaseorg](https://codegolf.stackexchange.com/users/39242/anders-kaseorg) for a byte!
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 8 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
‚Äô√ü√ü√ü·∫°¬µ·π†¬°
```
[Try it online!](http://jelly.tryitonline.net/#code=4oCZw5_Dn8Of4bqhwrXhuaDCoQ&input=&args=MjA) or [verify the smaller test cases](http://jelly.tryitonline.net/#code=4oCZw5_Dn8Of4bqhwrXhuaDCoQowcjIwwrXFvMOH4oKsRw&input=).
### How it works
```
‚Äô√ü√ü√ü·∫°¬µ·π†¬°  Main link. Argument: n
     ¬µ·π†¬°  Execute the preceding chain sign(n) times.
‚Äô         Decrement n, yielding n - 1.
 √ü√ü√ü      Recursively call the main link thrice.
    ·∫°     Take the absolute difference of n and the result.
```
[Answer]
## Mathematica, 20 bytes
Byte count assumes ISO 8859-1 (or compatible) encoding and `$CharacterEncoding` set to a matching value, like the Windows default `WindowsANSI`.
```
¬±0=0
¬±n_:=n-¬±¬±¬±(n-1)
```
This defines a unary operator `¬±`.
[Answer]
# J, ~~14~~ 12 bytes
```
-$:^:3@<:^:*
```
Saved 2 bytes thanks to @[Leaky Nun](https://codegolf.stackexchange.com/users/48934/leaky-nun).
Computes the result by calling itself recursively when *n* > 0 three times on *n*-1 and subtracting that result from *n*. There is a different situation for the base case when *n* = 0. There it computes *n*-*n* which equals 0.
```
a(n) = n - n = 0           if n = 0
       n - a(a(a(n-1)))    if n > 0
```
[Try it here.](http://tryj.tk)
## Explanation
```
-$:^:3@<:^:*  Input: n
           *  Get the sign of n (n = 0 => 0, n > 0 => 1)
         ^:   Execute that many times
                (0 times means it will just be an identity function)
       <:       Decrement n
 $:             Call itself recursively
   ^:3          three times
      @         on n-1
-             Subtract that result from n and return
```
[Answer]
# Julia, 16 bytes
```
!n=n>0&&n-!!!~-n
```
[Try it online!](http://julia.tryitonline.net/#code=IW49bj4wJiZuLSEhIX4tbgoKZm9yIG4gaW4gMDoyMAogICAgQHByaW50ZigiJTJ1ICUydVxuIiwgbiwgIW4pCmVuZA&input=)
### How it works
We redefine the unary operator `!` for our purposes.
If **n = 0**, the comparison `n>0` returns *false* and so does `!`. 
Otherwise, the code after `&&` gets executed. `~-n` is equivalent to `(n-1)` in two's complement, `!!!` recursively calls `!` thrice on **n - 1**, and the resulting value is subtracted from **n**.
[Answer]
# Python, 31 bytes
```
a=lambda n:n and n-a(a(a(n-1)))
```
Recursion limit and time constraints make above function impractical, but in theory it should work (and does work for small n).
[Answer]
## JavaScript (ES6), 52 bytes
```
n=>[0,...Array(n)].reduce((p,_,i,a)=>a[i]=i-a[a[p]])
```
I could have been boring and written the recursive version but this version is much faster (easily coping with the last test case) and also uses `reduce` so that's a plus!
[Answer]
## [Retina](https://github.com/m-ender/retina/), ~~49~~ 43 bytes
```
.+
$*1:
{`^1(1*):
$1:::-1$1
}`^:*(1*)-\1
1
```
[Try it online!](http://retina.tryitonline.net/#code=LisKJCoxOgp7YF4xKDEqKToKJDE6OjotMSQxCn1gXjoqKDEqKS1cMQoKMQ&input=MTA)
[Answer]
## CJam, ~~13~~ 12 bytes
*Thanks to Dennis for saving 1 byte.*
```
ri0{_(jjj-}j
```
[Test it here.](http://cjam.aditsu.net/#code=ri0%7B_(jjj-%7Dj&input=20)
[Answer]
# R, ~~42~~ 41 bytes
```
a=function(n)ifelse(n<1,0,n-a(a(a(n-1))))
```
Usage:
```
> a(1)
1
> a(10)
7
```
This recursive approach doesn't scale well for larger values of `n` though.
[Answer]
# [Oasis](http://github.com/Adriandmen/Oasis), 6 bytes
Code:
```
nbaa-0
```
Expanded version:
```
a(n) = nbaa-
a(0) = 0
```
Code:
```
n      # Push n
 b     # Calculate a(n - 1)
  a    # Calculate a(a(n - 1))
   a   # Calculate a(a(a(n - 1)))
    -  # Subtract a(a(a(n - 1))) from n
```
[Try it online!](http://oasis.tryitonline.net/#code=bmJhYS0w&input=&args=MjA)
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~18~~ 17 bytes
```
{‚çµ=0:0‚ãÑ‚çµ-‚àá‚ç£3‚ä¢‚çµ-1}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///v/pR71ZbAyuDR90tQJbuo472R72LjR91LQLxDGv/pz1qm/Cot@9R31RP/0ddzYfWGz9qmwjkBQc5A8kQD8/g/2mHVhjoPOrdbGoKAA "APL (Dyalog Unicode) ‚Äì Try It Online")
Surprisingly, there's no APL answer to this challenge. This is a literal implementation of the function in the OP.
TIO times out for \$n>90\$.
Saved a byte thanks to @Zachar√Ω.
[Answer]
# [Sesos](https://github.com/DennisMitchell/sesos), ~~58~~ 55 bytes
```
0000000: 16e0d7 bdcdf8 8cdf1b e6cfbb 840d3f bf659b 38e187  ..............?.e.8..
0000015: f8639b 39dc37 fc893f 666c05 7e7ed9 b88b3f ae0d3f  .c.9.7..?fl.~~...?..?
000002a: 676ed8 bd9940 7fdc3b 36619e f1                    gn...@..;6a..
```
Handles inputs up to **400** reasonably well, but run time increases dramatically after that point.
[Try it online!](http://sesos.tryitonline.net/#code=c2V0IG51bWluLCBzZXQgbnVtb3V0CgpnZXQKam1wCglqbXAKCQlyd2QgMywgYWRkIDEsIHJ3ZCAxLCBhZGQgMSwgZndkIDQsIHN1YiAxCglqbnoKCXJ3ZCAzLCBzdWIgMQpqbnoKcndkIDMsIGFkZCAxLCBmd2QgMgpqbXAKCXJ3ZCAxLCBzdWIgMSwgZndkIDMsIHN1YiAxLCBmd2QgMiwgYWRkIDMKCWptcAoJCXJ3ZCAyCgkJam1wCgkJCXJ3ZCAzCgkJam56CgkJZndkIDYsIGdldCwgcndkIDQsIHN1YiAxCgkJam1wCgkJCWZ3ZCAxLCBzdWIgMQoJCQlqbXAKCQkJCXJ3ZCAzCgkJCWpuegoJCQlzdWIgMQoJCQlqbXAKCQkJCWZ3ZCAzCgkJCWpuegoJCQlyd2QgNCwgc3ViIDEKCQlqbnoKCQlmd2QgMQoJCWptcAoJCQlyd2QgMSwgYWRkIDEsIGZ3ZCAxLCBhZGQgMQoJCWpuegoJCXN1YiAxLCBmd2QgMywgc3ViIDEKCQlqbXAKCQkJZndkIDMKCQlqbnoKCQlyd2QgMSwgc3ViIDEKCWpuegoJcndkIDIsIGdldAoJbm9wCgkJcndkIDMKCWpuegoJZndkIDMsIGdldCwgcndkIDIKCWptcAoJCWZ3ZCAyLCBhZGQgMQoJCWptcAoJCQlmd2QgMwoJCWpuegoJCXJ3ZCAxLCBhZGQgMSwgcndkIDIKCQlqbXAKCQkJcndkIDMKCQlqbnoKCQlmd2QgMSwgc3ViIDEKCWpuegoJZndkIDIKCWptcAoJCXJ3ZCAyLCBhZGQgMSwgZndkIDIsIHN1YiAxCglqbnoKCW5vcAoJCWdldCwgZndkIDMKCWpuegoJcndkIDEsIGFkZCAxLCBmd2QgMgpqbnoKcndkIDIsIHN1YiAxCmptcAoJcndkIDEsIHN1YiAxLCBmd2QgMSwgc3ViIDEKam56CnJ3ZCAxLCBwdXQ&input=MjA) Check *Debug* to see the generated SBIN code.
### Sesos assembly
The binary file above has been generated by assembling the following SASM code.
```
set numin, set numout
get
jmp
    jmp
        rwd 3, add 1, rwd 1, add 1, fwd 4, sub 1
    jnz
    rwd 3, sub 1
jnz
rwd 3, add 1, fwd 2
jmp
    rwd 1, sub 1, fwd 3, sub 1, fwd 2, add 3
    jmp
        rwd 2
        jmp
            rwd 3
        jnz
        fwd 6, get, rwd 4, sub 1
        jmp
            fwd 1, sub 1
            jmp
                rwd 3
            jnz
            sub 1
            jmp
                fwd 3
            jnz
            rwd 4, sub 1
        jnz
        fwd 1
        jmp
            rwd 1, add 1, fwd 1, add 1
        jnz
        sub 1, fwd 3, sub 1
        jmp
            fwd 3
        jnz
        rwd 1, sub 1
    jnz
    rwd 2, get
    nop
        rwd 3
    jnz
    fwd 3, get, rwd 2
    jmp
        fwd 2, add 1
        jmp
            fwd 3
        jnz
        rwd 1, add 1, rwd 2
        jmp
            rwd 3
        jnz
        fwd 1, sub 1
    jnz
    fwd 2
    jmp
        rwd 2, add 1, fwd 2, sub 1
    jnz
    nop
        get, fwd 3
    jnz
    rwd 1, add 1, fwd 2
jnz
rwd 2, sub 1
jmp
    rwd 1, sub 1, fwd 1, sub 1
jnz
rwd 1, put
```
[Answer]
# LISP, 61 bytes
```
(defun H(N)(if(= N 0)(return-from H 0)(- N(H(H(H(- N 1)))))))
```
Probably not the optimal solution, but it works.
[Answer]
# Java 7, 42 bytes
```
int c(int n){return n>0?n-c(c(c(n-1))):0;}
```
**Ungolfed & test cases:**
[Try it here.](https://ideone.com/KFLVfm)
```
class Main{
  static int c(int n){
    return n > 0
              ? n - c(c(c(n-1)))
              : 0;
  }
  public static void main(String[] a){
    for(int i = 0; i < 21; i++){
      System.out.println(i + ": " + c(i));
    }
    System.out.println("1000: " + c(1000));
  }
}
```
**Output:**
```
0: 0
1: 1
2: 1
3: 2
4: 3
5: 4
6: 4
7: 5
8: 5
9: 6
10: 7
11: 7
12: 8
13: 9
14: 10
15: 10
16: 11
17: 12
18: 13
19: 13
20: 14
 (last case takes too long..)
```
[Answer]
# Ruby, 27 bytes
The obvious implementation.
```
a=->n{n<1?0:n-a[a[a[n-1]]]}
```
This is a longer, faster answer that caches previous entries in the sequence.
Both answers only work for versions after 1.9, as that was when `->`, the stabby lambda, was introduced to Ruby.
```
->n{r=[0];i=0;(i+=1;r<<i-r[r[r[i-1]]])while i<n;r[n]}
```
[Answer]
## C#, 35 bytes
```
int a(int n)=>n>0?n-a(a(a(n-1))):0;
```
[Answer]
# Golfscript, ~~26~~ 25 bytes
```
~~~[0]{....,(===\.,@-+}@\*)\;~~
~[0]{...)\;==\.,@-+}@*)\;
```
[Try it online!](http://golfscript.tryitonline.net/#code=flswXXsuLi4pXDs9PVwuLEAtK31AKilcOw&input=MTAwMDA)
Locally `10000` takes less than half a second.
[Answer]
# C, ~~35~~ 32 bytes
*Saved 3 bytes thanks to @PeterTaylor!*
```
a(n){return n?n-a(a(a(n-1))):0;}
```
[Try it on Ideone!](https://ideone.com/8O5mPR)
[Answer]
# Javascript ES6, 22 bytes
```
a=n=>n&&n-a(a(a(n-1)))
```
I'll be boring and do the recursive version :P
[Answer]
## VBA, 69 bytes
```
Function H(N):ReDim G(N):For j=1To N:G(j)=j-G(G(G(j-1))):Next:H=G(N)
```
Works in the blink of an eye on the test set, slows down a little above n=1000000, runs into a memory wall a little above n=25 million. 
[Answer]
# Pyth, 10 bytes
```
L-WbbyFtb3
```
Defines a function `y`. Try it online: [Demonstration](https://pyth.herokuapp.com/?code=L-WbbyFtb3%0Ay20&debug=0)
This uses a relative new feature of Pyth. You can apply a function multiple times using the fold-syntax. It doesn't actually save any bytes, I used it just for demonstration purposes. 
### Explanation:
```
L-WbbyFtb3
L            define function y(b), that returns:
    b           b
 -Wb            and subtract the following if b>0
     yF  3      y applied three times to
       tb       b - 1
```
[Answer]
# Maple, ~~28~~ 26 bytes
```
`if`(n=0,0,n-a(a(a(n-1))))
```
Usage:
```
> a:=n->ifelse(n=0,0,n-a(a(a(n-1))));
> seq(a(i),i=0..10);
0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7
```
[Answer]
# dc, 34 bytes
```
dsn[zdddd1-;a;a;a-r:aln!=L]dsLx;ap
```
Input is taken from the top of the stack. This must be the only item on the stack, because the stack depth is used as a counter. Example of usage:
```
$ dc
10000dsn[zdddd1-;a;a;a-r:aln!=L]dsLx;ap
```
This is a fairly straightforward implementation of the sequence definition:
```
dsn               # Store n as `n', and keep a copy as a depth buffer (see below)
[                 # Open loop definition
 z                # Push stack depth i for i-th term
 dddd             # Duplicate stack depth four times, for a total of five copies
 1-               # Get i-1 for use as index to previous term
                  #   Note that if we hadn't duplicated n above, or left something else
                  #   on the stack, 0-1 would be -1, which is not a valid array index
 ;a;a;a           # Fetch a(a(a(i-1)))
 -                # Calculate i-a(a(a(i-1)))
 r                # Arrange stack to store i-th term: TOS |  i  (i-a(a(a(i-1))))
 :a               # Store i-th term in array `a'
 ln!=L            # Load n. If n!=i, we're not done calculating terms yet, so execute loop
]                 # Close loop definition. Note that we started with five copies of i:
                  #   i-1 was used to get last term
                  #   i-a(...) was used to calculate current term
                  #   ... i :a was used to store current term
                  #   i ln !=L was used to check loop exit condition
                  # One copy of i is left on the stack to increment counter
dsLx              # Duplicate loop macro, store it, and execute copy
;a                # Last i stored on stack from loop will equal n, so use this to get a(n)
p                 # Print a(n)
```
Anyways, it started out straightforward...then the golfing happened.
[Answer]
# [Common Lisp](http://www.clisp.org/), 44 bytes
```
(defun f(x)(if(= x 0)0(- x(f(f(f(1- x)))))))
```
[Try it online!](https://tio.run/##Vc5LCsMwDEXReVbhoTQo@DnpJ4OuJonAEEJoU/DuXdNA0bMmviDQmdb83muVebHPFkyKSjZ5hhKiRrmEIvYbtK@er8r@ytsh1la0@wd8JB@9j8HH1cfNx93Hw8dIR5lABhACpAAxQA4QBCQBUUCW1Cz1Cw "Common Lisp ‚Äì Try It Online")
[Answer]
## C++ ( MSVC, mainly )
### Normal version : 40 bytes
```
int a(int n){return n?n-a(a(a(n-1))):0;}
```
### Template meta programming version : 130 bytes
```
#define C {constexpr static int a(){return
template<int N>struct H C N-H<H<H<N-1>::a()>::a()>::a();}};template<>struct H<0>C 0;}};
```
Usage : 
```
std::cout << a(20) << '\n';       // Normal version
std::cout << H<20>::a() << '\n';  // Template version
```
The template version is the fastest code, since there's nothing faster than moving a value into a register => with optimization, `H<20>::a()` compile as :
```
mov esi, 14
```
For 10000, the recursive version crashes due to a stack overflow error, and the template version crashes at compile time due to template instantiation depth. GCC goes to 900 ( 614 )
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 7 bytes
```
¬©a√ü√ü√üU√â
```
[Try it](https://ethproductions.github.io/japt/?v=1.4.6&code=qWHf399VyQ==&input=OA==) or [run all test cases](https://ethproductions.github.io/japt/?v=1.4.6&code=qWHf399VyQ==&input=MjEKLW0=) (throws an overflow error for 10000)
[Answer]
# [D](https://dlang.org/), 36 bytes
```
T a(T)(T n){return n?n---n.a.a.a:0;}
```
[Try it online!](https://tio.run/##FcMxDoAgDADAWV7RsR0wxFEGP8EHSGBoosUg6kB8e9VcLqkGiBgIAwj1mttZBWQRa62M8Tc7/@hVOMEWWZCgm4G3vdQGR0vjl4s3w1255VUw4uSIvHn0BQ "D ‚Äì Try It Online")
[Answer]
# Python 3, 72 bytes
```
def f(n):
    a=[0];i=0
    while n:i+=1;a+=[i-a[a[a[i-i]]]];n-=1
    return a[i]
```
[Ideone it!](http://ideone.com/Q32qge)
[Answer]
## PowerShell v2+, 56 bytes
```
$a={$n=$args[0];if($n){$n-(&$a(&$a(&$a($n-1))))}else{0}}
```
The PowerShell equivalent of a lambda to form the recursive definition. Execute it via the `&` call operator, e.g. `&$a(5)`. Takes a *long* time to execute -- even `50` on my machine (a recent i5 with 8GB RAM) takes around 90 seconds.
### Faster iterative solution, 59 bytes
```
param($n)$o=,0;1..$n|%{$o+=$_-$o[$o[$o[$_-1]]]};$o[-1]*!!$n
```
Longer only because we need to account for input `0` (that's the `*!!$n` at the end). Otherwise we just iteratively construct the array up to `$n`, adding a new element each time, and output the last one at the end `$o[-1]`. Super-speedy -- calculating `10000` on my machine takes about 5 seconds.
]