15
\$\begingroup\$

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

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

35 Answers 35

20
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ (f$f$f$n-1) = f(f$f$n-1) saves a byte. \$\endgroup\$ – Anders Kaseorg Aug 3 '16 at 2:57
9
\$\begingroup\$

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.
\$\endgroup\$
  • 9
    \$\begingroup\$ Can the Jelly parser even handle programs larger than 10 bytes? \$\endgroup\$ – steenbergh Aug 2 '16 at 14:31
9
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Would you explain what ± does or how it works? Btw, congrats on 100k. \$\endgroup\$ – DavidC Aug 2 '16 at 7:21
  • 1
    \$\begingroup\$ @DavidC Thanks. :) It's just a built-in operator which is shorthand for the unused function PlusMinus. See this post for details. \$\endgroup\$ – Martin Ender Aug 2 '16 at 7:28
  • 1
    \$\begingroup\$ Very interesting. Dispenses with the @ or [ ] too. \$\endgroup\$ – DavidC Aug 2 '16 at 8:13
9
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I don't think the parentheses are needed. \$\endgroup\$ – Leaky Nun Aug 2 '16 at 8:12
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Mind adding an explanation? I have no idea what is going on with -!!~- ._. \$\endgroup\$ – Downgoat Aug 2 '16 at 5:49
  • 1
    \$\begingroup\$ Nothing fancy. ! is simply the function's name. \$\endgroup\$ – Dennis Aug 2 '16 at 5:52
5
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

Retina, 49 43 bytes

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

1

Try it online!

\$\endgroup\$
3
\$\begingroup\$

CJam, 13 12 bytes

Thanks to Dennis for saving 1 byte.

ri0{_(jjj-}j

Test it here.

\$\endgroup\$
  • \$\begingroup\$ That works for surprisingly high values. I think you don't need the a. \$\endgroup\$ – Dennis Aug 2 '16 at 6:55
  • \$\begingroup\$ @Dennis Oh, that's good to know, thanks. \$\endgroup\$ – Martin Ender Aug 2 '16 at 6:55
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user5957401 Aug 18 '16 at 17:18
  • \$\begingroup\$ a=function(n)"if"(n,n-a(a(a(n-1))),0) will work for several bytes off. \$\endgroup\$ – Giuseppe Oct 10 '17 at 20:24
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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..)
\$\endgroup\$
1
\$\begingroup\$

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]}
\$\endgroup\$
1
\$\begingroup\$

C#, 35 bytes

int a(int n)=>n>0?n-a(a(a(n-1))):0;
\$\endgroup\$
1
\$\begingroup\$

Golfscript, 26 25 bytes

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

Try it online!

Locally 10000 takes less than half a second.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ 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;} \$\endgroup\$ – Peter Taylor Aug 2 '16 at 7:19
  • 1
    \$\begingroup\$ @betseg - You have an erroneous : in your code too. You should take out the one after ?. \$\endgroup\$ – owacoder Aug 2 '16 at 13:03
1
\$\begingroup\$

Javascript ES6, 22 bytes

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

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Common Lisp, 44 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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 )

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

D, 36 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ {⍵=0:0⋄⍵-∇⍣3⊢⍵-1} \$\endgroup\$ – Zacharý Nov 10 '18 at 15:10
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.