# Print the N-bonacci sequence

This isn't very widely known, but what we call the Fibonacci sequence, AKA

1, 1, 2, 3, 5, 8, 13, 21, 34...


is actually called the Duonacci sequence. This is because to get the next number, you sum the previous 2 numbers. There is also the Tribonacci sequence,

1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201...


because the next number is the sum of the previous 3 numbers. And the Quadronacci sequence

1, 1, 1, 1, 4, 7, 13, 25, 49, 94, 181, 349, 673...


And everybody's favorite, the Pentanacci sequence:

1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129...


And the Hexanacci sequence, the Septanacci sequence, the Octonacci sequence, and so on and so forth up to the N-Bonacci sequence.

The N-bonacci sequence will always start with N 1s in a row.

# The Challenge

You must write a function or program that takes two numbers N and X, and prints out the first X N-Bonacci numbers. N will be a whole number larger than 0, and you can safely assume no N-Bonacci numbers will exceed the default number type in your language. The output can be in any human readable format, and you can take input in any reasonable manner. (Command line arguments, function arguments, STDIN, etc.)

As usual, this is Code-golf, so standard loopholes apply and the shortest answer in bytes wins!

# Sample IO

#n,  x,     output
3,  8  --> 1, 1, 1, 3, 5, 9, 17, 31
7,  13 --> 1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193
1,  20 --> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
30, 4  --> 1, 1, 1, 1       //Since the first 30 are all 1's
5,  11 --> 1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129

• Man, I had this idea a while ago and never got around to writing it up. Commented Jan 29, 2016 at 21:43
• Wouldn't 3-bonacci be 1, 1, 2, 4, 7 as the third position would be 0 + 1 + 1? ... and so one with the others? Commented Feb 8, 2019 at 17:42
• @umbrella No, the tribonacci starts with 3 1s. See my edit to clarify this point. Commented Feb 8, 2019 at 17:51
• Well then, that rules out using this approach. What a shame. Commented Apr 11, 2021 at 7:39

## Boolfuck, 6 bytes

,,[;+]


You can safely assume no N-Bonacci numbers will exceed the default number type in your language.

The default number type in Boolfuck is a bit. Assuming this also extends to the input numbers N and X, and given that N>0, there are only two possible inputs - 10 (which outputs nothing) and 11 (which outputs 1).

, reads a bit into the current memory location. N is ignored as it must be 1. If X is 0, the loop body (surrounded by []) is skipped. If X is 1, it is output and then flipped to 0 so the loop does not repeat.

• @StanStrum From before or after this answer? Commented Sep 18, 2017 at 22:25
• @StanStrum In fact, this answer is the example linked to in the initial version of that loophole. Commented Oct 15, 2023 at 4:23
• After this answer was posted, exploiting too-small number types because a standard loophole. That's what StanStrum's deleted comment was talking about. Commented Oct 17, 2023 at 10:01
• Indeed, abusing native number types is one of the loopholes that doesn't apply retroactively. I personally disagree with this policy and think it should, but I accept that consensus is against me. Commented Nov 19, 2023 at 1:17

## Python 2, 79 bytes

n,x=input()
i,f=0,[]
while i<x:v=[sum(f[i-n:]),1][i<n];f.append(v);print v;i+=1


Try it online

• Try replacing the last line with exec"v=[sum(f[i-n:]),1][i<n];f+=[v];print v;i+=1;"*x Commented Jan 30, 2016 at 5:33

g l=sum l:g(sum l:init l)
n#x|i<-1<$[1..n]=take x$i++g i


Usage example: 3 # 8-> [1,1,1,3,5,9,17,31].

How it works

i<-1<$[1..n] -- bind i to n copies of 1 take x -- take the first x elements of i++g i -- the list starting with i followed by (g i), which is sum l: -- the sum of it's argument followed by g(sum l:init l) -- a recursive call to itself with the the first element -- of the argument list replaced by the sum  • Shouldn't that be tail l instead of init l? Commented Jan 31, 2016 at 20:49 • @proudhaskeller: it doesn't matter. we keep the last n elements int the list. There's no difference between removing from the end and adding to the front and the other way around, i.e. removing from the front and adding to the end, because the initial list is made up of only 1s. – nimi Commented Jan 31, 2016 at 21:19 • Oh, I get it. That's a nifty way to replace ++[] by :! Commented Jan 31, 2016 at 21:26 • @proudhaskeller: yes, exactly! – nimi Commented Jan 31, 2016 at 21:30 # Pyth, 13 <Qu+Gs>QGEm1Q  Test Suite Takes input newline separated, with n first. ### Explanation: <Qu+Gs>QGEm1Q ## implicit: Q = eval(input) u Em1Q ## read a line of input, and reduce that many times starting with ## Q 1s in a list, with a lambda G,H ## where G is the old value and H is the new one +G ## append to the old value s>QG ## the sum of the last Q values of the old value <Q ## discard the last Q values of this list  • Wow, that was fast. I barely had time to close my browser before you'd already posted this! Commented Jan 29, 2016 at 21:51 # Javascript ES6/ES2015, 1079785 80 Bytes Thanks to @user81655, @Neil and @ETHproductions for save some bytes (i,n)=>eval("for(l=Array(i).fill(1);n-->i;)l.push(eval(l.slice(-i).join+));l")  try it online Test cases: console.log(f(3, 8))// 1, 1, 1, 3, 5, 9, 17, 31 console.log(f(7, 13))// 1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193 console.log(f(5, 11))// 1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129  • Nice. A couple of golfing tips: for is always better than while, x.split('') -> [...x], ~~a -> +a, n-=1 -> n--, if you enclose the entire function body in an eval you don't need to write return. Also, even shorter than [...'1'.repeat(i)] is Array(i).fill(1) and you can remove the ~~ from a and b. And you're allowed to remove the f=. Commented Jan 29, 2016 at 23:51 • This is what it looks like with my tips (85 bytes): (i,n)=>eval("for(l=Array(i).fill(1);n-->i;)l.push(l.slice(-i).reduce((a,b)=>a+b));l"). I changed the order of statements, combined the n-- into n-i and removed l from the arguments to save a few extra bytes. Commented Jan 30, 2016 at 0:13 • @user81655 I don't get the eval saving; (i,n)=>{for(l=Array(i).fill(1);n-->i;)l.push(l.slice(-i).reduce((a,b)=>a+b));return l} is still 85 bytes. – Neil Commented Jan 30, 2016 at 0:17 • @Neil Looks like 86 bytes to me... Commented Jan 30, 2016 at 0:21 • l.slice(-i).reduce((a,b)=>a+b) => eval(l.slice(-i).join+) Commented Jan 30, 2016 at 0:52 ## ES6, 66 bytes (i,n)=>[...Array(n)].map((_,j,a)=>a[j]=j<i?1:j-i?s+=s-a[j+~i]:s=i)  Sadly map won't let you access the result array in the callback. • Save a byte by currying the parameters. Commented May 11, 2017 at 11:36 # Jelly, 12 bytes ḣ³S; b1Ç⁴¡Uḣ  Try it online! ### How it works b1Ç⁴¡Uḣ Main link. Left input: n. Right input: x. b1 Convert n to base 1. ¡ Call... Ç the helper link... ⁴ x times. U Reverse the resulting array. ḣ Take its first x elements. ḣ³S; Helper link. Argument: A (list) ḣ³ Take the first n elements of A. S Compute their sum. ; Prepend the sum to A.  ## Python 2, 55 bytes def f(x,n):l=[1]*n;exec"print l[0];l=l[1:]+[sum(l)];"*x  Tracks a length-n window of the sequence in the list l, updated by appending the sum and removing the first element. Prints the first element each iteration for x iterations. A different approach of storing all the elements and summing the last n values gave the same length (55). def f(x,n):l=[1]*n;exec"l+=sum(l[-n:]),;"*x;print l[:x]  # Haskell, 47 bytes q(h:t)=h:q(t++[h+sum t]) n?x=take x$q$1<$[1..n]


Try it online!

<$ might have been introduced into Prelude after this challenge was posted. Haskell, 53 bytes n%i|i>n=sum$map(n%)[i-n..i-1]|0<1=1
n?x=map(n%)[1..x]


Try it online!

Defines the binary function ?, used like 3?8 == [1,1,1,3,5,9,17,31].

The auxiliary function % recursively finds the ith element of the n-bonacci sequence by summing the previous n values. Then, the function ? tabulates the first x values of %.

• Old answer, but do you mean "The auxiliary function %"? Commented Nov 26, 2018 at 1:02
• Switching the guards will turn i<=n into i>n. Commented Nov 26, 2018 at 2:38
• @ØrjanJohansen I noticed that too when editing, though looking back the whole method seems bad, so I might just re-do the whole golf.
– xnor
Commented Nov 26, 2018 at 2:42

# Husk, 9 bytes

↑§¡ȯΣ↑_B1


Try it online!

Starts from the Base-1 representation of N (simply a list of N ones) and ¡teratively sums (Σ) the last (↑_) N elements and appends the result to the list. Finally, takes (↑) the first X numbers in this list and returns them.

# C#, 109 bytes

(n,x)=>{int i,j,k;var y=new int[x];for(i=-1;++i<x;y[i]=i<n?1:k){k=0;for(j=i-n;j>-1&j<i;)k+=y[j++];}return y;}


Try it online!

(n, x) => {
int i, j, total;
var result = new int[x];
for (i = -1; ++i < x; ) { //calculate each term one at a time
total = 0; //value of the current term
for (j = i - n; j > -1 & j < i;) //sum the last n terms
{
total += result[j++];
}
result[i] = i < n ? 1 : total; //first n terms are always 1 so ignore the total if i < n
}
return result;
}


g _ 0=[]
g(h:t)n=h:g(t++[sum$h:t])(n-1)  g.g[1]  Attempt This Online! This is based on xnor's answer but it employs 1 clever trick. The $$\n\$$-bonacci sequence always start with $$\n\$$ 1s. A more general version of this might start with just any $$\n\$$ values. And this more general version is what we implement with g. g takes a list of $$\n\$$ integers and a value $$\m\$$ and gives us a list of the first $$\m\$$ terms of this generalized $$\n\$$-bonacci sequence. The trick is then that g[1] is a cheap way to generate $$\n\$$ 1s. Since the sequence starting with [1] is just an endless stream of 1s. So we use g in two ways, and even though g might be slightly longer because it implements something a little more general, it saves bytes because it serves two purposes. • Very nice, I see you re-used g as a helper to initialize the list of n ones, which also avoids using <$.
– xnor
Commented Jun 29, 2022 at 11:03

# Java, 82 + 58 = 140 bytes

Function to find the ith n-bonacci number (82 bytes):

int f(int i,int n){if(i<=n)return 1;int s=0,q=0;while(q++<n)s+=f(i-q,n);return s;}


Function to print first k n-bonacci number (58 bytes):

(k,n)->{for(int i=0;i<k;i++){System.out.println(f(i,n));}}


# C++11, 360 bytes

Hi I just like this question. I know c++ is a very hard language to win this competition. But I'll thrown a dime any way.

#include<vector>
#include<numeric>
#include<iostream>
using namespace std;typedef vector<int>v;void p(v& i) {for(auto&v:i)cout<<v<<" ";cout<<endl;}v b(int s,int n){v r(n<s?n:s,1);r.reserve(n);for(auto i=r.begin();r.size()<n;i++){r.push_back(accumulate(i,i+s,0));}return r;}int main(int c, char** a){if(c<3)return 1;v s=b(atoi(a[1]),atoi(a[2]));p(s);return 0;}


I'll leave this as the readable explanation of the code above.

#include <vector>
#include <numeric>
#include <iostream>

using namespace std;
typedef vector<int> vi;

void p(const vi& in) {
for (auto& v : in )
cout << v << " ";
cout << endl;
}

vi bonacci(int se, int n) {
vi s(n < se? n : se, 1);
s.reserve(n);
for (auto it = s.begin(); s.size() < n; it++){
s.push_back(accumulate(it, it + se, 0));
}
return s;
}

int main (int c, char** v) {
if (c < 3) return 1;
vi s = bonacci(atoi(v[1]), atoi(v[2]));
p(s);
return 0;
}

• Welcome to Programming Puzzles and Code Golf. This is a good answer, however I have noticed that you have lots of whitespace, and variable and function names that are longer than 1 character long. As it stands, this is a good readable version of your code, but you should add a golfed version. When you do, I will give you an upvote, but until it is golfed I will not. Commented Jan 30, 2016 at 13:28
• @wizzwizz4 Hi, added a golfed version of the code above. I left the ungolfed code around to let people see how I did it. Besides I like to read a function bonacci that returns vi which still sounds like vibonacci. I do feel I should not make the main function shorter because the standardard mandates using int main(int, char**) as entry point of the program. Further I believe all variables are max 1 character long and all non significant whitespaces are removed. Commented Jan 30, 2016 at 14:36
• This is not code-"comply with the standards". This is code-golf. We manipulate and take advantage of our languages. If any variables are ints, remove the int. If any functions are called foo, call them f. Be brutal; ignore the standard and exploit the compiler. That is how you golf. Commented Jan 30, 2016 at 16:11
• Puns and nice code belong in the ungolfed code only. But feel free to keep them there; actually, it is recommended to. But be really, really mean to the compiler when you golf your code. Get it as small as possible no matter what. (Oh, and here's the +1 I promised!) Commented Jan 30, 2016 at 16:12
• @wizzwizz4 Is removing "int" valid? I thought implied int won't run. Commented Jan 30, 2016 at 20:18

# R, 60 bytes

function(n,m){for(i in 1:m)T[i]=if(i>n,sum(T[i-1:n]),1);T}


Try it online!

Uiua (version 0.0.7), 34 bytes

→(;;)⍥(⊂∶/+↙∶→,⇌.)∶→(-,,)[⍥.-1∶1].


# APL, 21

{⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1}


This is a function that takes n as its left argument and x as its right argument.

Explanation:

{⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1}
⍺/1  ⍝ begin state: X ones
+     ⍝ identity function (to separate it from the ⍵)
⍺{         }⍣⍵     ⍝ apply this function N times to it with X as left argument
⍵,               ⍝ result of the previous iteration, followed by...
+/              ⍝ the sum of
⍺↑            ⍝ the first X of
⌽          ⍝ the reverse of
⍵         ⍝ the previous iteration
⍵↑                    ⍝ take the first X numbers of the result


Test cases:

      ↑⍕¨ {⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1} /¨ (3 8)(7 13)(1 20)(30 4)(5 11)
1 1 1 3 5 9 17 31
1 1 1 1 1 1 1 7 13 25 49 97 193
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1
1 1 1 1 1 5 9 17 33 65 129


# Python 3, 59

Saved 20 bytes thanks to FryAmTheEggman.

Not a great solution, but it'll work for now.

def r(n,x):f=[1]*n;exec('f+=[sum(f[-n:])];'*x);return f[:x]


Also, here are test cases:

assert r(3, 8) == [1, 1, 1, 3, 5, 9, 17, 31]
assert r(7, 13) == [1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193]
assert r(30, 4) == [1, 1, 1, 1]


# C, 132 bytes

The recursive approach is shorter by a couple of bytes.

k,n;f(i,s,j){for(j=s=0;j<i&j++<n;)s+=f(i-j);return i<n?1:s;}main(_,v)int**v;{for(n=atoi(v[1]);k++<atoi(v[2]);)printf("%d ",f(k-1));}


## Ungolfed

k,n; /* loop index, n */

f(i,s,j) /* recursive function */
{
for(j=s=0;j<i && j++<n;) /* sum previous n n-bonacci values */
s+=f(i-j);
return i<n?1:s; /* return either sum or n, depending on what index we're at */
}

main(_,v) int **v;
{
for(n=atoi(v[1]);k++<atoi(v[2]);) /* print out n-bonacci numbers */
printf("%d ", f(k-1));
}


# Brain-Flak, 144124 122 bytes

-20 bytes thanks to Nitroden

This is my first Brain-Flak answer, and I'm sure it can be improved. Any help is appreciated.

(([{}]<>)<{({}(()))}{}>)<>{({}[()]<<>({<({}<({}<>)<>>())>[()]}{})({}<><({({}<>)<>}<>)>)<>>)}{}<>{({}<{}>())}{}{({}<>)<>}<>


Try it online!

# Pari/GP, 46 bytes

The generating function of the sequence is:

$$\frac{(n-1)x^n}{x^{n+1}-2x+1}-\frac{1}{x-1}$$

(n,m)->Vec(n--/(x-(2-1/x)/x^n)-1/(x-1)+O(x^m))


Try it online!

# Vyxal , 8 bytes

1ẋ?‡W∑*Ḟ


Try it Online!

1ẋ       # [1] * input
‡W∑   # Function summing its inputs
?   *  # Set the arity to the input
Ḟ # Generate an infinite list from the function and the vector of 1s.


# Julia, 78 bytes

f(n,x)=(z=ones(Int,n);while endof(z)<x push!(z,sum(z[end-n+1:end]))end;z[1:x])


This is a function that accepts two integers and returns an integer array. The approach is simple: Generate an array of ones of length n, then grow the array by adding the sum of the previous n elements until the array has length x.

Ungolfed:

function f(n, x)
z = ones(Int, n)
while endof(z) < x
push!(z, sum(z[end-n+1:end]))
end
return z[1:x]
end


## Perl 6, 52~72 47~67 bytes

sub a($n,$x){EVAL("1,"x$n~"+*"x$n~"...*")[^$x]}  Requires the module MONKEY-SEE-NO-EVAL, because of the following error: ===SORRY!=== Error while compiling -e EVAL is a very dangerous function!!! (use MONKEY-SEE-NO-EVAL to override, but only if you're VERY sure your data contains no injection attacks) at -e:1 $ perl6 -MMONKEY-SEE-NO-EVAL -e'a(3,8).say;sub a($n,$x){EVAL("1,"x$n~"+*"x$n~"...*")[^\$x]}'
(1 1 1 3 5 9 17 31)

• Anyone know of a way to turn off strict mode, etc? Commented Jan 29, 2016 at 23:34
• I think if you use a pre-christmas 2015 Perl 6 release, it doesn't enforce monkey-see-no-eval. Commented Jan 30, 2016 at 17:29

# MATL, 22 26 bytes

1tiXIX"i:XK"tPI:)sh]K)


This uses current release (10.2.1) of the language/compiler.

Try it online!

A few extra bytes :-( due to a bug in the G function (paste input; now corrected for next release)

### Explanation

1tiXIX"      % input N. Copy to clipboard I. Build row array of N ones
i:XK         % input X. Build row array [1,2,...X]. Copy to clipboard I
"            % for loop: repeat X times. Consumes array [1,2,...X]
t          % duplicate (initially array of N ones)
PI:)       % flip array and take first N elements
sh         % compute sum and append to array
]            % end
K)           % take the first X elements of array. Implicitly display


# Perl 6, 38 bytes

->\N,\X{({@_[*-N..*].sum||1}...*)[^X]} # 38 bytes

-> \N, \X {
(

{

@_[
*-N .. * # previous N values

||     # if that produces 0 or an error
1      # return 1

} ... *  # produce an infinite list of such values

)[^X]      # return the first X values produced
}


### Usage:

# give it a lexical name
my &n-bonacci = >\N,\X{…}

for ( (3,8), (7,13), (1,20), (30,4), (5,11), ) {
say n-bonacci |@_
}

(1 1 1 3 5 9 17 31)
(1 1 1 1 1 1 1 7 13 25 49 97 193)
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(1 1 1 1)
(1 1 1 1 1 5 9 17 33 65 129)


# J, 31 bytes

]{.(],[:+/[{.])^:(-@[](1#~[))


Ungolfed:

] {. (] , [: +/ [ {. ])^:(-@[](1 #~ [))


## explanation

Fun times with the power verb in its gerund form:

(-@[](1 #~ [)) NB. gerund pre-processing


Breakdown in detail:

• ] {. ... Take the first <right arg> elements from all this stuff to the right that does the work...
• <left> ^: <right> apply the verb <left> repeatedly <right> times... where <right> is specified by the middle gerund in (-@[](1 #~ [), ie, ], ie, the right arg passed into the function itself. So what is <left>? ...
• (] , [: +/ [ {. ]) The left argument to this entire phrase is first transformed by the first gerund, ie, -@[. That means the left argument to this phrase is the negative of the left argument to the overall function. This is needed so that the phrase [ {. ] takes the last elements from the return list we're building up. Those are then summed: +/. And finally appended to that same return list: ] ,.
• So how is the return list initialized? That's what the third pre-processing gerund accomplishes: (1 #~ [) -- repeat 1 "left arg" number of times.

Try it online!

# Ruby, 41 bytes

->a,b{r=[1]*a;b.times{z,*r=r<<r.sum;p z}}


Try it online!

# R, 68 bytes

function(n,x){a=1+!1:n;for(i in n+1:x){a[i]=sum(a[(i-n:1)])};a[1:x]}


Try it online!

# K (ngn/k), 26 24 bytes

{(y-x){y,+/x#y}[-x]/x#1}


Try it online!