Reverse-Engineer the N-Bonacci sequence[s]

Question

EDIT: I will be accepting an answer Monday, 2/15/2016. May the bytes be ever in your favor!

In his "Print the N-Bonacci Sequence" challenge, @DJMcGoathem describes the N-bonacci sequences, wherein the previous N numbers are summed, instead of the traditional 2 of the Fibonacci sequence (said to be the "duonacci sequence"). He then asked to take two inputs, X and N, then output the Xth N-nacci number.

I propose the opposite.
Given a sequence, output which N-nacci sequence it is a subset of. I say "subset of" because:

• A) these sequences are infinite
• B) if given the start of the sequence, you could just count the number of leading 1s

In the case that it could belong to multiple N-nacci sequences, chose the lowest one.
In the case that it does not belong to any N-nacci sequence, then your program may do anything other than print something that could be mistaken for output. These behaviors include (but are not limited to): infinite loop, error, crash, delete itself (*cough cough* vigil *cough cough*), or create a black hole (as long as this black hole does not produce anything that could be mistaken for valid output).
For the sake of this challenge, these sequences start with 1. This means any N-nacci sequence starts with N ones. Furthermore, N must be a positive integer. So no -1-nacci, etc.

Test cases:

1,1,1 -> 1
49, 97 -> 7
55, 89, 144 -> 2
1 -> 1
6765 -> 2
12, 23, 45, 89 -> 12
100, 199 -> 100

Answer 1

Ruby, 94

I'm quite surprised how far I've been able to golf this within the same algorithm! I started with over 200!

->a{1.step.find{|s|x=[1]*(s+z=a.size)
x<<x[-s,s].inject(:+)while x.max<a.max&&s>1
x[-z,z]==a}}

Ungolfed:

l=->a{
    # ooh! a built-in infinite incrementer!
    1.step.find{|s|
        # if n == 1, z is important, otherwise s.
        x=[1]*(s+z=a.size)
        ## add the next nacci number until we hit or overshot max. 
        ## if s == 1, we don't increment, so don't bother
        x<<x[-s,s].inject(:+)while x.max<g&&s>1
        # eval to true if there's a match, false if not
        x[-z,z]==a
    }
}

Answer 2

APL (Dyalog Unicode), 46 bytes

{∧/0<⍵:⊃⊃⍸A⍷↑{⍵((+/↑),⊢)⍣{</+/¨A⍵}⍵⍴1}¨⍳⊃A←⌽⍵}

Try it online!

Anonymous prefix function, taking a vector of integers.

How?

∧/0<⍵:   ⍝ If the given sequence contains any non-positive integers, then return nothing. Otherwise...
A←⌽⍵     ⍝ Set A to be the reverse of the given sequence
{...}¨⍳⊃ ⍝ For each n in 1 to last element of given sequence, we generate the n-bonacci sequence in reverse order:
 ⍵⍴1       ⍝ Initialize a vector of n 1s (first n terms of the n-bonacci sequence)
 ⍣         ⍝ Do:
 ⍵((+/↑),⊢)  ⍝ Prepend the sum of the most-recent (first) n elements of the vector to the rest of the vector
           ⍝ While
 {</+/¨A⍵}   ⍝ the sum of the n-bonacci sequence generated so far is less than the sum of A
               ⍝ (this doesn't terminate prematurely because:
               ⍝   For n=1, this produces k+2 1s if A consists of k 1s
               ⍝     Otherwise, worst-case is that A has 1 element
               ⍝   For n=2, F_0+F_1+F_2 ... + F_{k-2} = F_k (identity)
               ⍝     F_0 + ... F_{k-1} > F_k, and APL terminates the ⍣-loop in the next step,
               ⍝     after F_k generated
               ⍝   For n>2, F_0+F_1+F_2 ... + F_{k-2} < F_k, so an excess of terms are generated
               ⍝ )
↑        ⍝ Mix to form a matrix, where the n-th row is the n-bonacci sequence
⍸A⍷      ⍝ Find the (row, column) positions of A in the matrix
⊃⊃       ⍝ Take the row of the first one (which would have minimum n)

Answer 3

Python 2, 176 bytes

def r(n,x):i,f=n,[1]*n;exec"f+=sum(f[i-n:]),;i+=1;"*(x-n);return f
l=input()
m=max(l)+len(l)
for i in range(1,m):
 if any(l==r(i,m)[b:b+len(l)]for b in range(m)):print i;break;

Note that this requires input in this format:

[1, 1, 2, 3...]

rather than

1, 1, 2, 3...

Fairly straightforward solution, just to get things rolling. I'll work more on golfing it down once somebody else answers. This uses a slightly modified version of the N-Bonnaci generator from @Data's answer, so props to him. Then for each N-Bonnaci in range of the input, checks if the input is a subsequence of it.

Answer 4

Lua, 324 323 Bytes

When I see other submission, I feel like there's something wrong with my code... But then, I remember that's Lua, and there's isn't all these fancy functionnalities :'(

It was a lot of fun, took me some time actually.

Edit: Saved 1 byte with a simple trick: using a ::label::+goto label instead a infinite loop done with while''.

function f(l)c=2 y,z=table.remove,os.exit while(l[1]<2)do y(l,1)if(#l<1)then print(1)z()end end ::q:: a={}for i=1,c do a[i]=1 end b={}for i=1,#l do b[i]=l[i]end while(a[#a]<b[1])do x=0 for i=(#a-c+1>0 and #a-c+1 or 1),#a do x=x+a[i]end a[#a+1]=x if a[#a]==b[1]then y(b,1)end if #b<1 then print(c)z()end end c=c+1 goto q end

Ungolfed and Explanations

Lua has no way to define a set, subset, or even check if an array/table contains a value without using its index/key. That's why i've decided to remove elements from the array I take as a parameter. that's how I keep record of which elements has already been computed, and if it matched.

  function f(l)
  c=2
  y,z=table.remove,os.exit           -- Create pointers on table.remove and os.exit
                                     -- saves a total of 9 bytes
  while(l[1]<2)                      -- loop used to remove leading 1
  do 
    y(l,1)
    if(#l<1)                         -- we also check if it was a 1-only array
    then 
      print(1)                       -- if so, we print 1 and exit
      z()
    end 
  end

  ::q::                              -- label q, start of the infinite loop
    a={}for i=1,c do a[i]=1 end      -- fill an array with c 1s
    b={}for i=1,#l do b[i]=l[i]end   -- copy the sequence array
    while(a[#a]<b[1])                -- while max(a)<min(b)
    do
      x=0 for i=(#a-c+1>0            -- iterate from index a.length-c to
                    and #a-c+1       -- to a.length
                    or 1),#a 
      do 
        x=x+a[i]                     -- summing a's elements
      end
      a[#a+1]=x                      -- append x to a
      if a[#a]==b[1]then y(b,1)end   -- if x is equal ot a member of the sequence
                                     -- remove it
      if #b<1 then print(c)z()end    -- if b is empty, it means the subset is in a
                                     -- we print c and exit
    end                              -- else we loop again
    c=c+1                            -- with c+1
  goto q                             -- return to the start of this block
end

You can try Lua online, and you can copy/paste the following code sample to run some tests. As this function exit when it founds the answer (infinite loop otherwise), you will have to change the index of test[] used (don't forget lua is 1-indexed :)).

function f(l)c=2 y,z=table.remove,os.exit while(l[1]<2)do y(l,1)if(#l<1)then print(1)z()end end ::q:: a={}for i=1,c do a[i]=1 end b={}for i=1,#l do b[i]=l[i]end while(a[#a]<b[1])do x=0 for i=(#a-c+1>0 and #a-c+1 or 1),#a do x=x+a[i]end a[#a+1]=x if a[#a]==b[1]then y(b,1)end if #b<1 then print(c)z()end end c=c+1 goto q end

test={{1,1,1},
{49, 97},
{55, 89, 144},
{1},
{6765},
{12, 23, 45, 89},
{100, 199}}

print(f(test[1]))

Answer 5

Wolfram Language (Mathematica), 71 bytes

(n=1;While[!SubsetQ[LinearRecurrence[s=1~Table~n,s,Max@l],l=#],n++];n)&

Try it online!