28
\$\begingroup\$

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

\$\endgroup\$
10
  • \$\begingroup\$ Related. \$\endgroup\$
    – Leaky Nun
    Jul 29 '16 at 15:25
  • 2
    \$\begingroup\$ Can we return True in languages where it can be used as 1? \$\endgroup\$
    – Dennis
    Jul 29 '16 at 15:53
  • 1
    \$\begingroup\$ @Dennis If in that language true is equivalent to 1 then yes. \$\endgroup\$
    – Leaky Nun
    Jul 29 '16 at 15:54
  • 4
    \$\begingroup\$ Apart from the OEIS link it might be good to reference GEB where the sequence first appeared. \$\endgroup\$ Jul 29 '16 at 16:16
  • 1
    \$\begingroup\$ Completing the list of GEB-related sequence challenges. \$\endgroup\$ Jul 29 '16 at 17:39

38 Answers 38

10
\$\begingroup\$

Haskell, 35 33 bytes

a n|n<3=1|b<-a.(-)n=b(b 1)+b(b 2)

Defines a function a.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Nice trick with the bind! Wouldn't something like (b.b)1+(b.b)2 be shorter than the sum? \$\endgroup\$
    – xnor
    Jul 29 '16 at 21:34
  • \$\begingroup\$ Why yes, thanks @xnor. \$\endgroup\$ Jul 29 '16 at 22:19
9
+200
\$\begingroup\$

Retina, 84 83 79 74 bytes

Byte count assumes ISO 8859-1 encoding.

.+
$*;1¶1¶
+`;(?=(1)+¶(1)+)(?=(?<-1>(1+)¶)+)(?=(?<-2>(1+)¶)+)
$3$4¶
G3=`
1

Try it online! (The first line enables a linefeed-separated test suite.)

I'll have to golf this some more later.

\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

Sesos, 54 bytes

0000000: eefb5b 04f83a a75dc2 36f8d7 cf6dd0 af7b3b 3ef8d7  ..[..:.].6...m..{;>..
0000015: cfed12 f661f0 ae9d83 ee63e6 065df7 ce6183 af7383  ....a.....c..]..a..s.
000002a: 76ef3c 3f6383 7eff9c b9e37f                       v.<?c.~.....

Try it online

Disassembled

set numin
set numout
add 1
fwd 1
add 1
fwd 6
get
sub 1
jmp
    jmp
        sub 1
        fwd 1
        add 1
        rwd 1
    jnz
    fwd 1
    sub 1
    rwd 2
    add 2
    jmp
        rwd 4
        jmp
            sub 1
            fwd 3
            add 1
            rwd 3
        jnz
        fwd 4
        jmp
            sub 1
            rwd 3
            add 1
            rwd 1
            add 1
            fwd 4
        jnz
        rwd 3
        jmp
            sub 1
            fwd 3
            add 1
            rwd 3
        jnz
        fwd 4
        add 2
        jmp
            rwd 5
            jmp
                rwd 1
                jmp
                    sub 1
                    fwd 2
                    add 1
                    rwd 2
                jnz
                fwd 1
                jmp
                    sub 1
                    rwd 1
                    add 1
                    fwd 1
                jnz
                rwd 1
                sub 1
            jnz
            fwd 2
            jmp
                sub 1
                rwd 1
                add 1
                rwd 1
                add 1
                fwd 2
            jnz
            fwd 1
            jmp
                rwd 2
                jmp
                    sub 1
                    fwd 1
                    add 1
                    rwd 1
                jnz
                fwd 2
                jmp
                    sub 1
                    rwd 2
                    add 1
                    fwd 2
                jnz
                fwd 1
            jnz
            fwd 3
            sub 1
        jnz
        rwd 2
        jmp
            sub 1
            rwd 3
            add 1
            fwd 3
        jnz
        fwd 1
        sub 1
    jnz
    fwd 2
jnz
rwd 7
put

Or in Brainfuck notation:

+>+>>>>>>,-[[->+<]>-<<++[<<<<[->>>+<<<]>>>>[-<<<+<+>>>>]<<<[->>>+<<<]>>>>++[<<<<<[<
[->>+<<]>[-<+>]<-]>>[-<+<+>>]>[<<[->+<]>>[-<<+>>]>]>>>-]<<[-<<<+>>>]>-]>>]<<<<<<<.
\$\endgroup\$
6
\$\begingroup\$

C, 43 42 bytes

Saved 1 byte thanks to @Dennis

Every answer is the same, I must do something different!

Try it online!

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

Explanation: it's basically a(n-a(n-2))+a(n-a(n-1)) but with swaggyundefinedbehavior (works on my phone (gcc) and ideone).

\$\endgroup\$
6
  • 4
    \$\begingroup\$ 1. You should also mention the compiler; your "swag" is undefined behavior. 2. With GCC, you don't need the 1 between ? and :. \$\endgroup\$
    – Dennis
    Jul 29 '16 at 18:00
  • \$\begingroup\$ @Dennis Interestingly, that same formulation works in my iterative PowerShell answer... $b+=$b[$_-$b[$_-2]]+$b[$_---$b[$_]] \$\endgroup\$ Jul 29 '16 at 20:28
  • \$\begingroup\$ @TimmyD some compilers may compile the a(n) before the n--, and there isn't a standart (or defined) behavior for that. Thus, undefined behavior. \$\endgroup\$
    – betseg
    Jul 29 '16 at 20:56
  • \$\begingroup\$ @betseg Yep, I agree. Just pointing out that it's not necessarily unique to C. \$\endgroup\$ Jul 29 '16 at 21:01
  • \$\begingroup\$ @TimmyD Oh I misunderstood that. I just wanted to change the function that everybody uses, so mine would be different and swaggy :D \$\endgroup\$
    – betseg
    Jul 29 '16 at 21:16
5
\$\begingroup\$

Mathematica, 36 bytes

Byte count assumes ISO 8859-1 encoding and Mathematica's $CharacterEncoding set to WindowsANSI (the default on Windows; other settings might work as well, but some like UTF-8 definitely don't).

±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}]
\$\endgroup\$
5
  • \$\begingroup\$ I may give you a +200 bounty if you do it in Retina \$\endgroup\$
    – Leaky Nun
    Jul 29 '16 at 15:44
  • \$\begingroup\$ @LeakyNun okay? :) \$\endgroup\$ Jul 29 '16 at 16:13
  • \$\begingroup\$ Two days later. \$\endgroup\$
    – Leaky Nun
    Jul 29 '16 at 16:18
  • \$\begingroup\$ @LeakyNun Soon you're going to have no rep left if you give out bounties so easily. \$\endgroup\$
    – mbomb007
    Jul 29 '16 at 19:58
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ Jul 30 '16 at 14:41
4
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ I may give you a +400 bounty if you do it in Sesos. \$\endgroup\$
    – Leaky Nun
    Jul 29 '16 at 15:50
  • \$\begingroup\$ @LeakyNun There seems to be an Sesos answer. It came out one day after your comment. \$\endgroup\$
    – Yytsi
    Feb 14 '17 at 5:48
4
\$\begingroup\$

JavaScript (ES6), 45 Bytes 34 Bytes

A recursive solution in ES6. Any golfing tips much appreciated.

a=n=>n>2?a(n-a(n-1))+a(n-a(n-2)):1

Thank you to /u/ismillo for shortening even further.

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

Jelly, 14 12 11 bytes

ịḣ2S;
1Ç⁸¡2ị

This is an iterative approach.

Try it online! or verify all test cases.

How it works

1Ç¡2ị   Main link. Argument: n

1       Set the return value to 1.
 Ç¡     Call the helper link n times, updating the return value after each call.
   2ị   Extract the second element of the resulting array.


ịḣ2S;   Helper link. Argument: A (array)

ị       At-index; retrieve the elements of A at the values of A.
 ḣ2     Head 2; extract the first two results.
    S   Take the sum of the result.
     ;  Prepend the sum to A.
\$\endgroup\$
3
\$\begingroup\$

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!

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

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

\$\endgroup\$
8
  • \$\begingroup\$ Sorry, I didn't saw your solution before posting my (identical) haskell solution. However isn't the byte count 38 as the new-line has to be taken into account? \$\endgroup\$
    – Laikoni
    Jul 29 '16 at 15:49
  • \$\begingroup\$ And the guard has to be n<3 for h 2 to be 1. \$\endgroup\$
    – Laikoni
    Jul 29 '16 at 15:58
  • \$\begingroup\$ @Laikoni It's 37 according to Pythons len feature with a multiline (""") string, unless you count newline as two bytes. Yeah, I noticed the other thing it's fixed now. \$\endgroup\$
    – KarlKastor
    Jul 29 '16 at 16:05
  • \$\begingroup\$ TIL notepad++ counts newline as two character. \$\endgroup\$
    – Laikoni
    Jul 29 '16 at 16:18
  • \$\begingroup\$ @Laikoni got rid of the newline it's indisputably 37 bytes now. \$\endgroup\$
    – KarlKastor
    Jul 29 '16 at 16:18
3
\$\begingroup\$

R, 50 bytes

a=function(n)ifelse(n<3,1,a(n-a(n-1))+a(n-a(n-2)))

Usage:

> a(1)
  1
> a(20)
  12
\$\endgroup\$
3
\$\begingroup\$

CJam, 19 18 bytes

XXri{_($2$$+}*]-3=

Try it online!

Uses the iterative approach.

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

C#, 51 44 bytes

int a(int n)=>n<3?1:a(n-a(n-1))+a(n-a(n-2));

i wonder if this can be shortened by making it anonymous thanks pinkfloydx33!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ c# 6 expression bodied function int a(int n)=>n<3?1:a(n-a(n-a))+a(n-a(n-2)); \$\endgroup\$ Jul 29 '16 at 18:57
  • \$\begingroup\$ Seems I typod while typing that on my phone. The inner most -a in the first set of parens should be -1 \$\endgroup\$ Jul 30 '16 at 10:16
  • \$\begingroup\$ I didn't notice it either, ill fix it rq \$\endgroup\$ Jul 30 '16 at 10:27
2
\$\begingroup\$

Golfscript, 29 bytes

~[1 1]{..0=(=\..1=(=@+\+}@*2=

Try it online!

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

05AB1E, 29 bytes

An iterative solution.

XˆXˆÍL>v¯¤ys-è¯y¯yÍè-è+ˆ}¯¹<è

Try it online

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

APL, 20 bytes

{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}

Explanation:

{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}
 ⍵≤2:1               If argument is 2 or less, return 1
      ⋄              Otherwise:
               ⍵-⍳2  Subtract [1, 2] from the argument
             ∇¨      Recursive call on both
           ⍵-        Subtract both results from the argument     
         ∇¨          Recursive call on both again
       +/            Sum          
\$\endgroup\$
2
\$\begingroup\$

VBA Excel 87 bytes

Non-recursive, since I want this to work for n=100000, say:

Function A(N):ReDim B(N):For i=3 To N:B(i)=B(i-B(i-1)-1)+B(i-B(i-2)-1)+1:Next:A=B(N)+1

... and press return (byte #87) at the end of the line to get the End Function statement for "free". Note that B values are offset by -1 to avoid initializing for n=1 and 2.

Invoke in spreadsheet as normal, eg =A(100000) to get 48157

The recursive version, 61 bytes,

Function Y(N):If N<3 Then Y=1 Else Y=Y(N-Y(N-1))+Y(N-Y(N-2))

starts to get unreasonably slow for n>30, and couldn't be said to work at all for n>40.

\$\endgroup\$
2
  • \$\begingroup\$ We don't care about performance. We care about code length. You should move your shorter solution to the top of your answer. \$\endgroup\$
    – mbomb007
    Aug 1 '16 at 16:36
  • 1
    \$\begingroup\$ @mbomb007 Since I'm nowhere near winning the golf, I'll make my own choices on what constitutes a working program. Not able to handle even single byte integers is not good enough as far as I'm concerned, when there is a solution which can do so easily. \$\endgroup\$
    – Joffan
    Aug 1 '16 at 16:57
2
\$\begingroup\$

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]]}
\$\endgroup\$
2
  • \$\begingroup\$ Afaik, you can get rid of the a=. If you post it here, it suffices when your code starts with the ->. It counts as an anonymous function then. \$\endgroup\$
    – Seims
    Aug 3 '16 at 10:08
  • \$\begingroup\$ @Seims Unfortunately, as the function calls itself with a[n-1] and such, the function needs to be named. \$\endgroup\$
    – Sherlock9
    Aug 3 '16 at 11:04
2
\$\begingroup\$

Java 7, 68 61 51 bytes

17 saved thanks to Leaky Nun.

int a(int n){return n<3?1:a(n-a(n-1))+a(n-a(n-2));}
\$\endgroup\$
4
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ Jul 29 '16 at 17:45
  • \$\begingroup\$ Welcome to PPCG! You might like Tips for Golfing in Java. An alternate form would be: int a(int n){return n<3?1:a(n-a(n-2))+a(n---a(n));}, but unfortunately it uses the same amount of bytes as the answer you already have.. Also, I would specify that your answer is in Java 7, since the Java 8 answer would be shorter: n->return n<3?1:a(n-a(n-1))+a(n-a(n-2)) (39 bytes). \$\endgroup\$ Aug 3 '16 at 12:44
  • \$\begingroup\$ Thanks for the welcomes guys, and thanks for the tip on Java8 - I didn't realize lambdas were allowed like that - although they're allowed like that in Python, so I guess I just never thought about it. Does the lambda need a semi-colon? \$\endgroup\$
    – Justin
    Aug 3 '16 at 12:46
  • \$\begingroup\$ @JustinTervay I don't use Java 8 a lot, but from what I've heard the semi-colon isn't counted on single-line expressions, according to a comment by @DavidConrad and @CAD97 in one of my own Java answers. \$\endgroup\$ Aug 3 '16 at 12:50
2
\$\begingroup\$

Oasis, 9 7 5 bytes

Non-competing, since the language postdates the challenge. Thanks to Kenny Lau for saving 4 bytes. Code:

ece+V

Expanded form (V is short for 11):

a(n) = ece+
a(0) = 1
a(1) = 1

Code:

e        # Stack is empty, so a(n - 1) is used, and it calculates a(n - a(n - 1))
 c       # Calculate a(n - 2)
  e      # Calculate a(n - a(n - 2))
   +     # Add up

Try it online!. Calculates n = 1000 in 0.1 seconds.

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

PowerShell v2+, 85 79 69 bytes

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

Takes input $n, sets $b to be an array of @(1, 1), then enters a loop from 2 .. $n. Each iteration we tack onto $b the latest calculation in the sequence with a simple += and the definition of the sequence. We then output the appropriate number from $b (with a -1 because arrays in PowerShell are zero-indexed). This works if $n is 1 or 2 because both of those values are pre-populated into the lower indices of $b from the start, so even if the loop tacks on junk, it's ignored anyway.


Recursive solution 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. Nope, the iterative solution is indeed shorter (see above).

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

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

JavaScript (ES6), 66 bytes

n=>[...Array(n+1)].reduce((p,_,i,a)=>a[i]=i<3||a[i-p]+a[i-a[i-2]])

Non-recursive version for speed; recursive version is probably shorter but I'll leave it for someone else to write. I always like it when I get to use reduce. Note: 1 byte saved by returning true (which casts to 1 when used in an integer context) for of a(1) and a(2).

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

Pyth, 16 bytes

L|<b3smy-bytdtBb

L                  def y(b):
 |<b3                b < 3 or …
      m      tBb       map for d in [b - 1, b]:
       y-bytd            y(b - y(d - 1))
     s                 sum

Defines a function y.

Try it online (added yMS20 to print the first 20 values)

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

Forth, 76 bytes

I finally got it working!

: Q recursive dup dup 3 < if - 1+ else 2dup 2 - Q - Q -rot 1- Q - Q + then ;

Try it online

Explanation:

: Q recursive                           \ Define a recursive function Q
    dup dup 3 <                         \ I moved a dup here to golf 2 bytes
    if                                  \ If n < 3, return 1
        - 1                             \ Golf: n-n is zero, add one. Same as 2drop 1+
    else
        2dup 2 - Q - Q                  \ Copy n until 4 on stack, find Q(n-Q(n-2))
        -rot                            \ Move the result below 2 copies of n
        1- Q - Q +                      \ Find Q(n-Q(n-2)), then add to previous ^
    then ;

Try it online (slightly un-golfed from above)

Unfortunately, mutual recursion is a bit too wordy to use for golfing.

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

Lua, 59 bytes

function a(n)return n<3 and 1 or a(n-a(n-1))+a(n-a(n-2))end
\$\endgroup\$
1
\$\begingroup\$

Maple, 43 41 bytes

a:=n->`if`(n>2,a(n-a(n-1))+a(n-a(n-2)),1)

Usage:

> a(1);
  1
> a(20);
  12

This problem is certainly a good candidate for memoization. Using option cache, the run times are cut down significantly:

aC := proc(n) 
      option cache; 
      ifelse( n > 2, aC( n - aC(n-1) ) + aC( n - aC(n-2) ), 1 ); 
end proc:

This can be seen using:

CodeTools:-Usage( aC(50) );
\$\endgroup\$
1
\$\begingroup\$

Husk, 17 bytes

!¡λṁ!¹m≠→L¹↑_2)ḋ3

Try it online!

Feels too long. I'll post something with fix soon.

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

Japt, 20 bytes

No big shenanigans, just recursively calculates the result.

§2?1:ßU-ßUÉ)+ßU-ßU-2 
§2                   // If the input is less than or equal to 2
  ?1                 // return 1,
    :                // otherwise
     ß               // recursively recall with
      U-ßUÉ          // input minus recursive recall input minus one
           )+        // plus
             ßU-ßU-2 // same with input minus two.

Try it here.

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

J, 29 28 bytes

1:`(+&$:/@:-$:@-&1 2)@.(2&<)

Uses the recursive definition.

Usage

Extra commands are used for formatting multiple input/output.

   f =: 1:`(+&$:/@:-$:@-&1 2)@.(2&<)
   (,:f"0) >: i. 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 2 3 3 4 5 5 6  6  6  8  8  8 10  9 10 11 11 12

Explanation

1:`(+&$:/@:-$:@-&1 2)@.(2&<)  Input: n
                        2&<   If n < 2
1:                              Return 1
                              Else
               -&1 2            Subtract [1, 2] from n to get [n-1, n-2]
            $:@                 Call recursively on n-1 and n-2
           -                    Subtract each of the results from n
        /@:                     Reduce using
      $:                          A recursive call on each
    +&                            Then summation
                                Return that value as the result
\$\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.