Hofstadter H-sequence

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
• OEIS A005374

Answer 1

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 for a byte!

Answer 2

Jelly, 8 bytes

’ßßßạµṠ¡

Try it online! or verify the smaller test cases.

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 3

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

Answer 4

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 5

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.

Answer 6

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 7

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 8

Retina, 49 43 bytes

.+
$*1:
{`^1(1*):
$1:::-1$1
}`^:*(1*)-\1

1

Try it online!

Answer 9

CJam, 13 12 bytes

Thanks to Dennis for saving 1 byte.

ri0{_(jjj-}j

Test it here.

Answer 10

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 11

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!

Answer 12

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 13

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

Answer 14

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 15

Common Lisp, 44 bytes

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

Try it online!

Answer 16

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 17

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

Answer 18

D, 36 bytes

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

Try it online!

Answer 19

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!

Answer 20

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

Answer 21

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 22

C#, 35 bytes

int a(int n)=>n>0?n-a(a(a(n-1))):0;

Answer 23

Golfscript, 26 25 bytes

~[0]{....,(===\.,@-+}@*)\;
~[0]{...)\;==\.,@-+}@*)\;

Try it online!

Locally 10000 takes less than half a second.

Answer 24

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 25

Javascript ES6, 22 bytes

a=n=>n&&n-a(a(a(n-1)))

I'll be boring and do the recursive version :P

Answer 26

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 27

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

Answer 28

Clojure, 44 42 bytes

(fn f[n](if(= 0 n)0(- n(f(f(f(dec n)))))))

So sad this is sorter than (fn f[n](if(= 0 n)0(- n((comp f f f dec)n)))).

Answer 29

Japt, 7 bytes

©aßßßUÉ

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

Answer 30

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!

Answer 31

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.

Answer 32

><>, 55+2 = 57 bytes

^~n;
.~-]{:0$
v>1-}32[
v/  /:1-32[
>$:?/$~]{:0$.
/30@2[

The input is expected to be present on the stack at program start, so +2 bytes for the -v flag. Try it online!

This is hecka slow, as it uses recursion to calculate the result. Using TIO, h(50) takes over a minute. It returns the correct results <= 30, so I'm confident it would work for h(10000), I just haven't run it to find out!

Answer 33

RETURN, 17 bytes

[$[$1-aaa-][]?]=a

Try it here!

Recursive operator that leaves result on the stack. Example usage:

[$[$1-aaa-][]?]=a 4a

Answer 34

Python 2, 54 53 bytes

a=r,=0,
exec'r=len(a)-a[a[r]];a+=r,;'*input()
print r

Not even close to the recursive solution, but at least it's fast.

Test it on Ideone.

Answer 35

C#, 156 bytes

Mine is going to be a bit longer than the other C# answer, but my version can compute up to 10,000 (and higher) without a stack overflow, and can do all integers from 0 to 10,000 in a fraction of a second due to addition of a dictionary. Most of the answers here can take hours to do integers in the thousands, so my extra bytes also lead to massive speed increases.

Golfed

Dictionary<int,int> l=new Dictionary<int,int>();int H(int n){int v;if(n==0)return 0;if(l.TryGetValue(n,out v)){}else{v=n-H(H(H(n-1)));l.Add(n,v);}return v;}

Ungolfed (with test program)

using System;
using System.Collections.Generic;

namespace HH
{
    class Program
    {
        static Dictionary<int, int> l = new Dictionary<int, int>();

        static int H(int n)
        {
            int v;
            if (n == 0)
                return 0;
            if (l.TryGetValue(n, out v))
            { }
            else
            {
                v = n - H(H(H(n - 1)));
                l.Add(n, v);
            }
            return v;
        }

        static void Main(string[] args)
        {
            for(int i = 0; i <= 10000; i++)
                Console.WriteLine("{0}: {1}", i, H(i));
            Console.ReadLine();
        }
    }
}

Edit: The other C# answer can't compute H(10,000) without a stack overflow, mine can print all numbers from H(1) to H(1,000,000) in a few seconds. H(1,000,000) is 682,328 if anyone was wondering :P