29
\$\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, 2016 at 15:25
  • 2
    \$\begingroup\$ Can we return True in languages where it can be used as 1? \$\endgroup\$
    – Dennis
    Jul 29, 2016 at 15:53
  • 1
    \$\begingroup\$ @Dennis If in that language true is equivalent to 1 then yes. \$\endgroup\$
    – Leaky Nun
    Jul 29, 2016 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, 2016 at 16:16
  • 1
    \$\begingroup\$ Completing the list of GEB-related sequence challenges. \$\endgroup\$ Jul 29, 2016 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, 2016 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, 2017 at 9:50
  • \$\begingroup\$ @Qwerp-Derp ohh, thanks. I'll fix that when I get on my laptop. \$\endgroup\$ Feb 16, 2017 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, 2017 at 9:27
  • \$\begingroup\$ I'm sorry I don't quite understand you. What do you mean by successor? \$\endgroup\$
    – Andrakis
    Feb 16, 2017 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, 2017 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, 2017 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, 2017 at 9:49
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.