# 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

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

# dc, 62 bytes

?si2sa1dd2:a:a[la1+dsadd1-;a-;alad2-;a-;a+r:ali;a0=A]dsAxli;af


This solution makes use of arrays and recursion.

?si          # Take input from stdin and store it in register i'
2sa          # Initialise register a' with 2, since we'll be putting in the first
#   two values in the sequence
1dd2         # Stack contents, top-down: 2 1 1 1
:a           # Pop index, then pop value: Store 1 in a
:a           # Ditto:                     Store 1 in a
[            # Open macro definition
la 1+ dsa   # Simple counter mechanism: Increment a and keep a copy on stack

# The STACK-TRACKER(tm): Top of stack will be at top of each column, under the
#   dashed line. Read commands from left to right, wrapping around to next line.
#   This will be iteration number n.
dd   1-    ;a       -          ;a            la            d
#-----------------------------------------------------------------------
# n    n-1   a[n-1]   n-a[n-1]   a[n-a[n-1]]   n             n
# n    n     n        n          n             a[n-a[n-1]]   n
# n    n     n                                 n             a[n-a[n-1]]
#                                                            n
#

2-            ;a            -             ;a            +      r    :a
#-----------------------------------------------------------------------
# n-2           a[n-2]        n-a[n-2]      a[n-a[n-2]]   a[n]   n
# n             n             a[n-a[n-1]]   a[n-a[n-1]]   n      a[n]
# a[n-a[n-1]]   a[n-a[n-1]]   n             n
# n             n

li;a        # Load index of target element, and fetch that element's current value
#    Uninitialised values are zero
0=A         # If a[i]==0, execute A to compute next term
]dsAx        # Close macro definition, store on A' and execute
li;a         # When we've got enough terms, load target index and push value
f            # Dump stack (a[i]) to stdout

• In conclusion, if anyone is building an IDE for dc, let me know!
– Joe
Jul 29, 2016 at 22:52

# Erlang, 46 bytes

f(N)when N<3->1;f(N)->f(N-f(N-1))+f(N-f(N-2)).


# 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. Feb 16, 2017 at 9:50 • @Qwerp-Derp ohh, thanks. I'll fix that when I get on my laptop. Feb 16, 2017 at 11:21 # 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:).

# Japt-N, 14 bytes

Note that the -N flag isn't strictly necessary here as it would seem returning true instead of 1 is allowed.

§2ªCìx@ßU-ßXnU

§2ªCìx@ßU-ßXnU     :Implicit input of integer U
§2                 :Less than or equal to 2?
ª                :Logical OR with
C               :12
ì              :To digit array
@            :After passing each X through the following function
ß           :  Recursive call with argument
U-         :    U minus
ß        :      Recursive call with argument
XnU     :        U minus X


## Lithp, 70 bytes

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

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? Feb 16, 2017 at 9:27
• I'm sorry I don't quite understand you. What do you mean by successor? Feb 16, 2017 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. Feb 16, 2017 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. Feb 16, 2017 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. Feb 16, 2017 at 9:49