Print the N-bonacci sequence

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

Haskell, 56 bytes

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

Answer 5

Javascript ES6/ES2015, 107 97 85 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

Answer 6

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.

Answer 7

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]

Answer 8

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.

Answer 9

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

Answer 10

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;
}

Answer 11

Brain-Flak, 144 124 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!

Answer 12

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.

Answer 13

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!

Answer 14

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]

Answer 15

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              

Answer 16

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));}}

Answer 17

Ruby, 41 bytes

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

Try it online!

Answer 18

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!

Answer 19

K (ngn/k), 26 24 bytes

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

Try it online!

Answer 20

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

Answer 21

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

Answer 22

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)

Answer 23

Perl 6, 38 bytes

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

-> \N, \X {
  (

    {

      @_[
        *-N .. * # previous N values
      ].sum      # added together

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

Answer 24

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));
}

Answer 25

PHP, 78 bytes

for(list(,$n,$x)=$argv;$i<$x;print${$i++}." ")$s+=$$i=$i<$n?1:$$d+$s-=${$d++};

Try it online!

-4 Bytes using PHP>=7.1 [,$n,$x] instead of list(,$n,$x)

Answer 26

Jq 1.5, 67 bytes

def C:if length>X then.[:X]else.+=[.[-N:]|add]|C end;[range(N)|1]|C

Assumes input provided by N and X e.g.

def N: 5;
def X: 11;

Expanded

def C:                        # . is current array
    if length>X               # stop when array is as long as X
    then .[:X]                # return first X elements
    else .+=[.[-N:]|add] | C  # recursively add sum of last N elements to array
    end
;
  [range(N)|1]                # initial state
| C

Try it online!

Answer 27

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!

Answer 28

Mathematica, 59 bytes

((f@#=1)&/@Range@#;f@n_:=Tr[f[n-#]&/@Range@#];f/@Range@#2)&

You'll probably want to Clear@f between function calls. Arguments are n,x, just like the test cases.

Answer 29

Tidy, 36 bytes

{x,n:n^recur(*tile(x,c(1)),sum@c,x)}

Try it online!

Explanation

{x,n:n^recur(*tile(x,c(1)),sum@c,x)}
{x,n:                              }   lambda taking parameters `x` and `n`
     n^                                take the first `n` terms of...
       recur(                     )        a recursive function
             *tile(x,c(1)),                whose seed is `x` `1`s
                           sum@c,          taking the sum of each window
                                 x         with a window size of `x`

Answer 30

Japt, 18 bytes

@ZsVn)x}gK=Vì1;K¯U

Try it online!

Explanation:

         K=Vì1        :Start with n 1s in an array K
@      }gK            :Extend K to at least x elements by setting each new element to:
      x               : The sum of
 ZsVn                 : The previous n elements
              ;       :Then
               K¯U    :Return the first n elements of K

Answer 31

MathGolf, 10 bytes

ª*kÆ_Σ▐├p;

Try it online!

Explanation

ª            push [1]
 *           pop a, b : push(a*b)
  k          read integer from input
   Æ         start block of length 5
    _        duplicate TOS
     Σ       sum(list), digit sum(int)
      ▐      append to end of list
       ├     pop from left of string/array
        p    print with newline
         ;   discard TOS

Answer 32

Japt, 16 12 bytes

@ZÔ¯V x}hVÆ1

Try it

@ZÔ¯V x}hVÆ1     :Implicit input of integers U=X & V=N
         VÆ1     :Map the range [0,V) returning 1 for each element
        h        :Push the result of the following to the array and repeat until its length equals U
@                :  Pass the array through the following function as Z
 ZÔ              :    Reverse Z
   ¯V            :    Slice to the Vth element
      x          :    Reduce by addition
       }         :  End function

Answer 33

C# (.NET Core), 130 bytes

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

Try it online!

Answer 34

C (gcc), 94 bytes

a(c,C,i){for(int Q[C+c],*q=Q;C--;printf("%d ",*q++))for(*q=Q-q>(i=-c);Q-q<=i&i<0;)*q+=q[i++];}

Try it online!

Answer 35

krrp, 72 bytes

^nx:\L[take]x,^nl:?nL#!fl@-n1#!r[append]lL[sum]lEl.x[map]^_:1.[range]0n.

Try it online!

---

Explanation

^nx:              ~ lambda expression in two parameters
 \L               ~  import list module
 [take]x          ~  the first x elements of
  ,^nl:           ~   extend the initial list of n ones
    ?n            ~    if n is non-zero
     L #!fl       ~     keep the first element
      @-n1        ~     recur
       #!r        ~     separate the first element
        [append]l ~      append an additional element,
         L[sum]lE ~      namely the sum of the previous elements
     l            ~    if n is zero, yield l
   . x            ~ extend x elements, yielding in a list of n+x elements
   [map]^_:1.     ~   map a constant function
   [range]0n.     ~   onto a list of n elements

Try it online!