25
\$\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\$
  • \$\begingroup\$ Related. \$\endgroup\$ – Leaky Nun Jul 29 '16 at 15:25
  • 1
    \$\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\$ – Martin Ender Jul 29 '16 at 16:16
  • 1
    \$\begingroup\$ Completing the list of GEB-related sequence challenges. \$\endgroup\$ – Martin Ender Jul 29 '16 at 17:39

35 Answers 35

0
\$\begingroup\$

Racket, 63 bytes

(define(a n)(if(> n 2)(for/sum([m'(1 2)])(a(- n(a(- n m)))))1))
\$\endgroup\$
0
\$\begingroup\$

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

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

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
\$\endgroup\$
  • \$\begingroup\$ I think you can get rid of the 0 in the < statement, because the challenge specs state that the input is a positive integer. \$\endgroup\$ – clismique Feb 16 '17 at 9:50
  • \$\begingroup\$ @Qwerp-Derp ohh, thanks. I'll fix that when I get on my laptop. \$\endgroup\$ – Carcigenicate Feb 16 '17 at 11:21
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Just curious, why did you make functions like (def a #N::(+ N 1)), where a is a successor? \$\endgroup\$ – clismique Feb 16 '17 at 9:27
  • \$\begingroup\$ I'm sorry I don't quite understand you. What do you mean by successor? \$\endgroup\$ – Andrakis Feb 16 '17 at 9:39
  • \$\begingroup\$ 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. \$\endgroup\$ – clismique Feb 16 '17 at 9:40
  • \$\begingroup\$ 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. \$\endgroup\$ – Andrakis Feb 16 '17 at 9:47
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – clismique Feb 16 '17 at 9:49
0
\$\begingroup\$

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

\$\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.