# Definition

• $$\a(0) = 0\$$
• $$\a(n) = n-a(a(a(n-1)))\$$ for integer $$\n > 0\$$

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

• Related challenges about Hofstadter sequences: 1, 2, 3 Aug 2, 2016 at 6:43
• And I still think you should reference GEB... Aug 2, 2016 at 6:43
• How is number-theory relevant here? Aug 2, 2016 at 9:56
• @flawr facepalm Let me try that again: Gödel, Escher, Bach: An Eternal Golden Braid Aug 2, 2016 at 10:18
• @StigHemmer Actually facepalm has its own Emoji now: 🤦 Aug 3, 2016 at 11:50

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 for a byte! • (f$f$f$n-1) = f(f$f$n-1) saves a byte. Aug 3, 2016 at 2:57

# Jelly, 8 bytes

’ßßßạµṠ¡


### 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.

• Can the Jelly parser even handle programs larger than 10 bytes? Aug 2, 2016 at 14:31

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 ±. • Would you explain what ± does or how it works? Btw, congrats on 100k. Aug 2, 2016 at 7:21 • @DavidC Thanks. :) It's just a built-in operator which is shorthand for the unused function PlusMinus. See this post for details. Aug 2, 2016 at 7:28 • Very interesting. Dispenses with the @ or [ ] too. Aug 2, 2016 at 8:13 # J, 14 12 bytes -$:^:3@<:^:*


Saved 2 bytes thanks to @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.

## 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

• I don't think the parentheses are needed. Aug 2, 2016 at 8:12

# Julia, 16 bytes

!n=n>0&&n-!!!~-n


Try it online!

### 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.

• Mind adding an explanation? I have no idea what is going on with -!!~- ._. Aug 2, 2016 at 5:49
• Nothing fancy. ! is simply the function's name. Aug 2, 2016 at 5:52

# 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).

## 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!

## Retina, 49 43 bytes

.+
$*1: {^1(1*):$1:::-1$1 }^:*(1*)-\1 1  Try it online! ## CJam, 13 12 bytes Thanks to Dennis for saving 1 byte. ri0{_(jjj-}j  Test it here. • That works for surprisingly high values. I think you don't need the a. Aug 2, 2016 at 6:55 • @Dennis Oh, that's good to know, thanks. Aug 2, 2016 at 6:55 # 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. • You should be able to lose a byte (and a number of errors w/ bad inputs) if you change your condition to n<1. As its a sequence, it is only really defined for non-negative integers anyhow. Aug 18, 2016 at 17:18 • a=function(n)"if"(n,n-a(a(a(n-1))),0) will work for several bytes off. Oct 10, 2017 at 20:24 # 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! # APL (Dyalog Unicode), 18 17 bytes {⍵=0:0⋄⍵-∇⍣3⊢⍵-1}  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ý. • {⍵=0:0⋄⍵-∇⍣3⊢⍵-1} Nov 10, 2018 at 15:10 • {×⍵:⍵-∇⍣3⊢⍵-1⋄0} for 16. Sep 17, 2020 at 1:48 # 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! 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  # 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. # Java 7, 42 bytes int c(int n){return n>0?n-c(c(c(n-1))):0;}  Ungolfed & test cases: Try it here. 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..)  # 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]}  ## C#, 35 bytes int a(int n)=>n>0?n-a(a(a(n-1))):0;  # Golfscript, 26 25 bytes ~[0]{....,(===\.,@-+}@*)\; ~[0]{...)\;==\.,@-+}@*)\;  Try it online! Locally 10000 takes less than half a second. # 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! • In C you can use an integer directly as a conditional, giving a three-byte saving: a(n){return n?n-a(a(a(n-1))):0;} Aug 2, 2016 at 7:19 • @betseg - You have an erroneous : in your code too. You should take out the one after ?. Aug 2, 2016 at 13:03 # Javascript ES6, 22 bytes a=n=>n&&n-a(a(a(n-1)))  I'll be boring and do the recursive version :P ## 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. # Pyth, 10 bytes L-WbbyFtb3  Defines a function y. Try it online: Demonstration 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  # 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  # 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.

# Common Lisp, 44 bytes

(defun f(x)(if(= x 0)0(- x(f(f(f(1- x)))))))


Try it online!

## 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 )

• I think you don't need the space between C and { in the template meta programming version Sep 23, 2018 at 20:38
• @Zacharý MSVC refuses to compile without that space Nov 10, 2018 at 16:28
• Ahh, I see now why that seems to keep happening Nov 10, 2018 at 19:05
• @Zacharý It depends on the type of macro. If it has parameters, then i can remove the space, but here it doesn't Nov 10, 2018 at 19:12

# Japt, 7 bytes

©aßßßUÉ


Try it or run all test cases (throws an overflow error for 10000)

# D, 36 bytes

T a(T)(T n){return n?n---n.a.a.a:0;}


Try it online!

# 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!

## 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.