# 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

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

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

# Racket, 63 bytes

(define(a n)(if(> n 2)(for/sum([m'(1 2)])(a(- n(a(- n m)))))1))


# ><>, 65+2 = 67 bytes

^n;
.+]{0$v1}\ v2} @2->1[ v3}>- /:::1-1[ >4}:2)?^~~1]{0$.
/0$1[  Input neds to be present on the stack at program start, so +2 bytes for the -v flag. Try it online! More ridiculously slow recursive madness. Test case for 20 on TIO takes 20.5 seconds, so use larger inputs at your own risk # Clojure, 86 bytes (defn a[n](cond(< 0 n 3)1 1(+(a(- n(a(dec n))))(a(- n(a(- n 2)))))))  Very literal. (defn a [n] (cond (< 0 n 3) 1 ; Return 1 if n is 1 or 2 :else (+ (a (- n (a (dec n)))) ; Else, recurse 4 times and do some math (a (- n (a (- n 2))))))) (doseq [n (range 1 21)] (println 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  • I think you can get rid of the 0 in the < statement, because the challenge specs state that the input is a positive integer. – clismique Feb 16 '17 at 9:50 • @Qwerp-Derp ohh, thanks. I'll fix that when I get on my laptop. – Carcigenicate Feb 16 '17 at 11:21 ## Lithp, 70 bytes (non-competing) (def a #N::((if(<= N 2)(1)((+(a(- N(a(- N 1))))(a(- N(a(- N 2)))))))))  Warning: incredibly slow. Very recursive. Implements the exact algorithm in challenge. Non-competing because language is newer than challenge. Try it online! An alternate solution that is much faster, using caching of results: ## Lithp, 166 bytes ((def a #N::((if(<= N 2)(1)((+(b(- N(b(- N 1))))(b(- N(b(- N 2)))))))))(var C(dict)) (def b(scope #N::((if(!(dict-present C N))((dict-set C N(a N))))(dict-get C N)))))  Try it online! • Just curious, why did you make functions like (def a #N::(+ N 1)), where a is a successor? – clismique Feb 16 '17 at 9:27 • I'm sorry I don't quite understand you. What do you mean by successor? – Andrakis Feb 16 '17 at 9:39 • A successor function is a function that increments a number, but that's besides the point. I'm just curious about the way to define functions in Lithp - why did you choose to do #arg:: when defining functions? I haven't really seen that done in a Lisp-like before. – clismique Feb 16 '17 at 9:40 • Ah, thank you. Firstly, lowercase names are atoms. Names beginning with an uppercase are variables. It follow Erlang's design in this way. Next, I struggled to read most Lisp code, though I loved the elegance of it. The way I've designed my syntax is to be easy to read, and an anonymous function (format: #[Args,...] :: ( calls .. )) was easy to see what arguments are being passed. It's only sort-of Lisp-like really. I like the elegance of the braces, and it's easy to parse. – Andrakis Feb 16 '17 at 9:47 • Oh, that's how it works, thanks! I was looking at the arguments and it seemed a bit weird, but now that you've explained it I can understand why it's like that. – clismique Feb 16 '17 at 9:49 # PHP, 56 bytes function q($n){return$n<3?:q($n-q($n-1))+q($n-q(\$n-2));}


recursive function; requires PHP 5.6 or later (or replace ?: with ?1:).