# Am I a Special N-bonacci Number?

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.

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.

• N==1 is such a weird case. – Magic Octopus Urn Jun 16 '17 at 14:43
• Yep, but weird cases are what makes this fun :) – Gryphon Jun 16 '17 at 14:44
• 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. – apsillers Jun 16 '17 at 19:43
• 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? – apsillers Jun 16 '17 at 23:11
• 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.) – apsillers Jun 16 '17 at 23:19

# 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?

• Excellent. Seems to work for me, anyway. +1 – Gryphon Jun 16 '17 at 14:10
• 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). – Jonathan Allan Jun 16 '17 at 14:19
• Tried a bunch of test cases, so unless someone finds one it fails, it's good with me. – Gryphon Jun 16 '17 at 14:20

# 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 #]³.

# Python 2, 59 56 bytes

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


Try it online!

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

• Here is a wrapper for all test cases if you like it. – Leaky Nun Jun 16 '17 at 15:14
• Here are 2 bytes golfed off. – Leaky Nun Jun 16 '17 at 15:15

# 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

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

...          # keep generating values until

* > A        # it is greater than ｢A｣

)
}


# 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!

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

# 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))))))))

• 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. – apsillers Jun 16 '17 at 23:16
• @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? – Renzo Jun 16 '17 at 23:20
• Ok, now I see the question has been changed, I have updated my answer. – Renzo Jun 16 '17 at 23:24

# 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].

• I ran it on all examples that I saw. 1 is truthy, 0 is falsey. – zgrep Jun 16 '17 at 14:10
• @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. – zgrep Jun 16 '17 at 14:21
• 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 – Gryphon Jun 16 '17 at 14:23

# 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

# 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]