11
\$\begingroup\$

The N-bonacci sequence, originally invented by @DJMcMayhem in this question, is a sequence generated by starting with the integers 0 and 1, and then adding the previous N numbers to generate the next number. The special N-bonacci sequence is an N-bonacci sequence beginning with a pair of numbers other than 0 and 1, which will be named X and Y. If N is greater than the number of terms already in the sequence, simply add all available terms.

So for example the normal fibonacci sequence has an N of 2 (takes the previous two items), and an X and Y of 0 and 1, or 1 and 1, depending on who you ask.

Your Task:

You are to write a program or function that checks whether an inputted integer (A) is part of the special N-bonacci sequence generated by the next three integers (using the second input as N, and the third and fourth as X and Y). Ensure that you handle the special case of N=1.

Input:

Four non-negative integers, A, N, X, and Y.

Output:

A truthy/falsy value that indicates whether A is part of the N-bonacci sequence generated by the N, X, and Y inputs.

Test Cases:

Input:    Output:
13,2,0,1->truthy
12,3,1,4->falsy
4,5,0,1-->truthy
8,1,8,9-->truthy
9,1,8,9-->truthy

12,5,0,1->falsy  [0,1]>[0,1,1]>[0,1,1,2]>[0,1,1,2,4]>[0,1,1,2,4,8]>[0,1,1,2,4,8,16]>etc.

Scoring:

This is , so the lowest score in bytes wins.

| improve this question | |
\$\endgroup\$
  • 1
    \$\begingroup\$ N==1 is such a weird case. \$\endgroup\$ – Magic Octopus Urn Jun 16 '17 at 14:43
  • \$\begingroup\$ Yep, but weird cases are what makes this fun :) \$\endgroup\$ – Gryphon Jun 16 '17 at 14:44
  • \$\begingroup\$ If you do indeed want answers to handle the case N=1, you might want to call it out in the question, since many answers (including all current answers, I think) will have a failure condition that assumes a strictly increasing series. Also, can X and Y be negative? That will probably also invalidate all existing answers. \$\endgroup\$ – apsillers Jun 16 '17 at 19:43
  • 1
    \$\begingroup\$ I think all existing answers fail to handle the non-increasing case where both X and Y are zero. Is it necessary to handle that case as well? \$\endgroup\$ – apsillers Jun 16 '17 at 23:11
  • 1
    \$\begingroup\$ I think you should add the truthy cases 8,1,8,9 and 9,1,8,9 to ensure that N=1 case handling detects the non-repeated X value as well as the Y value. (If you want to handle 0,0 cases you should add that as well.) \$\endgroup\$ – apsillers Jun 16 '17 at 23:19

10 Answers 10

Active Oldest Votes
5
\$\begingroup\$

Jelly, 12 bytes

ḣ⁴S;µṀ<⁵µ¿⁵e

A full program taking [X,Y], N, A.

Try it online!

How?

ḣ⁴S;µṀ<⁵µ¿⁵e - Main link (monadic): [X,Y]
    µ   µ¿   - while:
     Ṁ       -   maximum value of the list
       ⁵     -   5th command line argument (3rd input) = A
      <      -   less than?
             - ...do:
 ⁴           -   4th command line argument (2nd input) = N
ḣ            -   head (get the first N (or less) items from the list)
  S          -   sum
   ;         -   concatenate (add the result to the front of the list)
          ⁵  - 5th command line argument (3rd input) = A
           e - exists in the resulting list?
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Excellent. Seems to work for me, anyway. +1 \$\endgroup\$ – Gryphon Jun 16 '17 at 14:10
  • \$\begingroup\$ To instead see the reversed N-bonacci sequence up to a value greater than or equal to A just remove the ⁵e from the end; much easier to tell it will work then (noting that the order of the first two terms is of no consequence). \$\endgroup\$ – Jonathan Allan Jun 16 '17 at 14:19
  • \$\begingroup\$ Tried a bunch of test cases, so unless someone finds one it fails, it's good with me. \$\endgroup\$ – Gryphon Jun 16 '17 at 14:20
5
\$\begingroup\$

05AB1E, 18 bytes

[DR²£O©‚˜³®>‹#]³QZ

Try it online!

Uses: [X,Y], N, A

I feel like some unintended functionality made that harder than it needed to be.

There's no greater-than-or-equal-to, never noticed that before.

And #³ didn't work, and required a ], for +1 bytes #]³.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Python 2, 59 56 bytes

a,n,l=input()
while l[0]<a:l=[sum(l[:n])]+l
print a in l

Try it online!

Takes input as A,N,[X,Y]

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Here is a wrapper for all test cases if you like it. \$\endgroup\$ – Leaky Nun Jun 16 '17 at 15:14
  • \$\begingroup\$ Here are 2 bytes golfed off. \$\endgroup\$ – Leaky Nun Jun 16 '17 at 15:15
3
\$\begingroup\$

Perl 6, 47 bytes

->\A,\N,\X,\Y{A∈(X,Y,{[+] @_.tail(N)}...*>A)}

test it

Expanded:

->
  \A,
  \N,
  \X, \Y
{
    A          # is ｢A｣

  ∈            # an element of

    (          # this Sequence

      X, Y,        # seed values of sequence

      {            # generate the rest of the Seq using this code block

        [+]        # reduce by addition

          @_       # of all previously generated values
          .tail(N) # only use the last ｢N｣ of them
      }

      ...          # keep generating values until

      * > A        # it is greater than ｢A｣

    )
}
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Python 2, 50 bytes

a,n,l=input()
while[a]>l:l=[sum(l[:n])]+l
a in l>x

Takes input as A,N,[Y,X]. Outputs via exit code.

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

R, 69 60 bytes

function(a,n,l){while(l<a)l=c(sum(l[1:n],na.rm=T),l)
a%in%l}

Try it online!

Returns an anonymous function, taking a,n and a vector l=c(y,x). Constructs the N-bonacci sequence backwards (i.e., smaller index is further in the sequence), since while(l<a) only checks the first element of l.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Common Lisp, 164 bytes

(defun f(a n x y &aux(l(list y x)))(if(= n 1)(or(= a x)(= a y))(loop(if(<= a(car l))(return(member a l))(setf l(cons(reduce'+ l)(if(<(length l)n)l(butlast l))))))))

This function returns NIL for false, non-NIL for true (according to the definition of generalized boolean of Common Lisp).

(defun f(a n x y &aux (l (list y x)))    ; initialize a list l for the N values
  (if (= n 1)                            ; special case for N = 1
      (or (= a x) (= a y))               ;    true only if A = X or A = Y
      (loop
        (if (<= a (car l))               ; when the last number generated is greater than A
            (return (member a l))        ; return true if A is in the list
            (setf l (cons (reduce '+ l)  ; otherwise compute the sum of l
                          (if (< (length l) n)   ; and push it to l (truncating the list at 
                              l                  ; end if it has already size = N)
                              (butlast l))))))))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Does you special-case handling for N=1 detect an A of, e.g., both 1 and/or 2 when X=1 Y=2? My Lisp-reading skills are not great, but it looks like you might only compare A to one of the two initial values. \$\endgroup\$ – apsillers Jun 16 '17 at 23:16
  • \$\begingroup\$ @apsillers , when N=1 I compare A only with X and not with Y. should I compare it with both returning true if it is equal to one of them? Maybe the sequence is not well defined for this case? \$\endgroup\$ – Renzo Jun 16 '17 at 23:20
  • \$\begingroup\$ Ok, now I see the question has been changed, I have updated my answer. \$\endgroup\$ – Renzo Jun 16 '17 at 23:24
0
\$\begingroup\$

k, 29 bytes

{x=*(*x>){(x=#y)_y,+/y}[y]/z}

Try it online! 1 is truthy, 0 is falsey. Input is [A;N;X,Y].

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I ran it on all examples that I saw. 1 is truthy, 0 is falsey. \$\endgroup\$ – zgrep Jun 16 '17 at 14:10
  • \$\begingroup\$ @Gryphon I moved the input over to the footer instead of the body, but I'm not certain what you want me to change. It both is and was the same function. \$\endgroup\$ – zgrep Jun 16 '17 at 14:21
  • \$\begingroup\$ Oh, I see now. I thought you weren't taking any input, but you were taking it in the code. Makes much more sense now. I don't know k, so I assumed you'd missinterpreted the question, as all it would do was output 1 0 1 1 \$\endgroup\$ – Gryphon Jun 16 '17 at 14:23
0
\$\begingroup\$

PHP>=7.1, 103 Bytes

for([,$n,$d,$s,$e]=$argv,$f=[$s,$e];$x<$n;)$x=$f[]=array_sum(array_slice($f,-$d));echo+in_array($n,$f);

Testcases

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 94 bytes

(s={#3,#4};t=1;While[t<#2-1,s~AppendTo~Tr@s;t++];!LinearRecurrence[1~Table~#2,s,#^2]~FreeQ~#)&


input format

[A,N,X,Y]

| improve this answer | |
\$\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.