# 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. Jun 16, 2017 at 14:43
• Yep, but weird cases are what makes this fun :) Jun 16, 2017 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. Jun 16, 2017 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? Jun 16, 2017 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.) Jun 16, 2017 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 Jun 16, 2017 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). Jun 16, 2017 at 14:19
• Tried a bunch of test cases, so unless someone finds one it fails, it's good with me. Jun 16, 2017 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. Jun 16, 2017 at 15:14
• Here are 2 bytes golfed off. Jun 16, 2017 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. Jun 16, 2017 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? Jun 16, 2017 at 23:20
• Ok, now I see the question has been changed, I have updated my answer. Jun 16, 2017 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. Jun 16, 2017 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. Jun 16, 2017 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 Jun 16, 2017 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]