Hofstadter Q-sequence

Definition

  1. a(1) = 1
  2. a(2) = 1
  3. a(n) = a(n-a(n-1)) + a(n-a(n-2)) for n > 2 where n is an integer

Task

Given positive integer n, generate a(n).

Testcases

n  a(n) 1  1 2  1 3  2 4  3 5  3 6  4 7  5 8  5 9  6 10 6 11 6 12 8 13 8 14 8 15 10 16 9 17 10 18 11 19 11 20 12 

Reference

Replay

Retina, 84 bytes

.+
<$&$*1>
{+`(<(1+)11)>
{$1-<1$2>>,$1-<$2>>}
<1+>
1
+`1-1
-
->
>
}T`1p`1_`{1+,1+}
.

Try it online!

I'll have to golf this some more later. I'm sure some of those {} or <> markers are unnecessary.

Python, 45 40 bytes

a=lambda n:n<3or a(n-a(n-1))+a(n-a(n-2))

Simple naïve interpretation of the challenge.

Saved 5 bytes thanks to @LeakyNun!

Julia, 29 bytes

!n=n<3||!(n-!~-n)+!(n-!~-~-n)

Try it online!

How it works

We redefine the unary operator ! for our purposes.

If n is 1 or 2, n<3 returns true and this is our return value.

If n larger than 2, n<3 returns false and the || branch gets executed. This is a straightforward implementation of the definition, where ~-n yields n - 1 and ~-~-n yields n - 2.

C#, 51 bytes

int a(int n){return n<3?1:a(n-a(n-1))+a(n-a(n-2));}

i wonder if this can be shortened by making it anonymous

Mathematica, 36 bytes

Byte count assumes ISO 8859-1 encoding.

±1=±2=1
±n_:=±(n-±(n-1))+±(n-±(n-2))

Defines ± as a unary operator.

I tried getting rid of the duplication, but ended up with the same byte count:

±1=±2=1
±n_:=Tr[±(n-±(n-#))&/@{1,2}]

C, 43 bytes

a(n){return n<3?1:a(n-a(n-1))+a(n-a(n-2));}

Haskell, 39 37 Bytes

h n|n<3=1|n>2=h(n-h(n-1))+h(n-h(n-2))

exactly like described in the challenge, using guards

PowerShell v2+, 78 76 bytes

$a={param($k)if($k-lt3){1}else{(&$a($k-(&$a($k-1))))+(&$a($k-(&$a($k-2))))}}

First time I've used the equivalent of a lambda as the answer, as usually an iterative solution is shorter (as you can see from all the nested parens). But, in this case, the nested parens are almost duplicated in the iterative solution with the nested array calls, so the recursive solution is shorter.

Call it via the execution-operator, like &$a 20. Just a straight-up recursive call.

Iterative solution, 85 79 bytes

param($n)$b=1,1;if($n-gt2){2..$n|%{$b+=$b[$_-$b[$_-1]]+$b[$_-$b[$_-2]]}};$b[-1]

Uses the array $b as the holder of values as it loops from 2 to input $n, each iteration tacking that number onto $b. The loop only happens if the input is greater than 2. Once the loop finishes, outputs the last element in the array.

Jelly, 15 14 bytes

2Rạ⁸߀$⁺Sµ1>?2

Try it online! or verify all test cases (takes a few seconds).

How it works

2Rạ⁸߀$⁺Sµ1>?2  Main link. Argument: n (integer)

2R              Yield [1, 2].
      $         Combine the previous three links into a monadic chain.
   ⁸                Yield n.
  ạ                 Take the absolute difference of the return value and n.
    ߀              Recursively call the main link on each result.
       ⁺            Duplicate the chain.
                    The first copy maps [1, 2] to [a(n - 1), a(n - 2)].
                    The second copy maps [a(n - 1), a(n - 2)] to
                    [a(n - a(n - 1)), a(n - a(n - 2))].
        S           Take the sum.
         µ          Combine all links to the left into a chain.
            ?       If...
           > 2          n is greater than 2, call the chain.
          1         Else, return 1.

Ruby, 36 bytes

A direct implementation. Any golfing suggestions are welcome.

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

Category: code golf Time: 2016-07-29 Views: 2

Related post

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development

search

Front-end development

Database

development tools

Open Platform

Javascript development

.NET development

cloud computing

server

Copyright (C) avrocks.com, All Rights Reserved.

processed in 0.212 (s). 12 q(s)