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

38 Answers 38

1
2
0
\$\begingroup\$

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[2]
:a           # Ditto:                     Store 1 in a[1]
[            # 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
\$\endgroup\$
1
  • \$\begingroup\$ In conclusion, if anyone is building an IDE for dc, let me know! \$\endgroup\$ – Joe Jul 29 '16 at 22:52
0
\$\begingroup\$

Erlang, 46 bytes

f(N)when N<3->1;f(N)->f(N-f(N-1))+f(N-f(N-2)).
\$\endgroup\$
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\$
2
  • \$\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\$

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\$
0
\$\begingroup\$

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

Try it or run all test cases

§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
     x             :Reduce by addition
      @            :After passing each X through the following function
       ß           :  Recursive call with argument
        U-         :    U minus
          ß        :      Recursive call with argument
           XnU     :        U minus X
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\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
1
2

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.