How-many-bonacci-like is this sequence?

Question

Inspired by @emanresu A's Is it a fibonacci-like sequence? Make sure to upvote that challenge as well!

We say a sequence is Fibonacci-like, if, starting from the third term (\$1\$-indexed), each term is the sum of the previous two terms. For example, \$3, 4, 7, 11, 18, 29, 47, 76, 123, 199\cdots\$ is a Fibonacci-like sequence that starts with \$3, 4\$.

Similarly, for any positive integer \$n\$, we say a sequence is \$n\$-bonacci-like, if, starting from the \$n+1\$ term (\$1\$-indexed), each term is the sum of the previous \$n\$ terms. For example, \$2, 4, 5, 11, 20, 36, 67, 123, 226, 416\cdots\$ is a \$3\$-bonacci-like sequence that starts with \$2, 4, 5\$, while \$1, 2, 4, 7, 8, 22, 43, 84, 164, 321\cdots\$ is a \$5\$-bonacci-like sequence that starts with \$1, 2, 4, 7, 8\$.

In particular, constant sequences (sequences where every item are the same) are \$1\$-bonacci-like.

Task

Given a non-empty list of positive integers, output the smallest \$n\$ such that it could be part of some \$n\$-bonacci-like sequence. You may assume that the input is (non-strictly) increasing.

Note that a list with length \$n\$ is always a part of some \$n\$-bonacci-like sequence.

This is code-golf, so the shortest code in bytes wins.

Testcases

[3] -> 1
[2, 2, 2] -> 1
[1, 2, 2] -> 3
[2, 3, 4, 7] -> 4
[1, 3, 4, 7, 11, 18] -> 2
[1, 1, 1, 1, 1, 1, 6] -> 6
[2, 4, 5, 11, 20, 36, 67, 123, 226, 416] -> 3
[1, 2, 4, 7, 8, 22, 43, 84, 164, 321] -> 5
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] -> 10

Answer 1

R, 91 78 77 bytes

Edit: -1 byte thanks to Giuseppe

function(x){while(any((rowSums(matrix(c(0,x),sum(x|1),T))-x)[0:-T]))T=T+1;+T}

Try it online!

Answer 2

Vyxal, 14 12 10 bytes

?lṠṪ?nȯ⁼)ṅ

Try it Online!

Man this new "lambda to newline" thing is cool.

-2 thanks to @emanresuA

Explained

?lṠṪ?nȯ⁼)ṅ
        )ṅ   # Get the first positive integer n where:
  Ṡ          #   the sums of all
?l           #   overlapping windows of the input of length n
   Ṫ         #   with the tail removed
       ⁼     #   exactly equals
    ?nȯ      #   input[n:]

Answer 3

MATL, 25 bytes

f"G1@&l2&Y+3L)G@QJh)=A?@.

Try it online!

Generalization of the convolution method from my fibonacci-like sequence answer.

---

Previous

MATL, 30 bytes

f"Gn@XH-t:"G@@H+&:)J&)s=-]~?@.

Try it online!

Answer 4

Python3, 102 bytes:

lambda x,c=0:(v(x,c)and c)or(x and f(x,c+1))
v=lambda x,i:len(x)<=i or(sum(x[:i])==x[i]and v(x[1:],i))

Try it online!

Answer 5

Dyalog APL, 15 13 bytes

-2 thanks to @FrownyFrog. (Since the input is non-decreasing, ⍋ can be used instead of ⍳∘≢ to save 2 bytes.)

⊃∘⍸⍋(⊃↓⍷+/)¨⊂

Try it online!

Taking the sequence 1 1 2 3 5 as an example:

   ⍋(     )¨⊂  For each n from 1 to the length of the sequence,  1           2        ...
      ↓        is the sequence with the first n terms removed    1 2 3 5     2 3 5    ...
       ⍷       a subsequence of
        +/     the sums of each n-sized window in the sequence   1 1 2 3 5   2 3 5 8  ...
     ⊃         at the first position?                            no          yes      ...
⊃∘⍸            What is the first index where this is true?       2

Answer 6

Factor + lists.lazy math.unicode, 68 bytes

[ 1 lfrom [ dupd clump [ Σ ] map 1 head* tail? ] with lfilter car ]

Try it online!

Explanation

Find the first positive integer whose sums of clumps of the input, sans the last element, is the tail end of the input.

1 lfrom [ ... ] with lfilter car Find the first positive integer where...

           ! { 2 4 5 11 20 36 67 123 226 416 } 3      (for example)
dupd       ! { 2 4 5 11 20 36 67 123 226 416 } { 2 4 5 11 20 36 67 123 226 416 } 3
clump      ! { 2 4 5 11 20 36 67 123 226 416 } {
                 { 2 4 5 }
                 { 4 5 11 }
                 { 5 11 20 }
                 { 11 20 36 }
                 { 20 36 67 }
                 { 36 67 123 }
                 { 67 123 226 }
                 { 123 226 416 }
             }
[ Σ ] map  ! { 2 4 5 11 20 36 67 123 226 416 } { 11 20 36 67 123 226 416 765 }
1 head*    ! { 2 4 5 11 20 36 67 123 226 416 } { 11 20 36 67 123 226 416 }
tail?      ! t

Answer 7

Python 3.8 (pre-release), 76 bytes

f=lambda n,i=1:i*all(E==sum(n[I:I+i])for I,E in enumerate(n[i:]))or f(n,i+1)

Try it online!

This is a recursive function that increments i until the conditions are met with that i.

Answer 8

JavaScript (ES6),  65  64 bytes

Saved 1 byte thanks to @tsh

f=(a,w)=>a.every((v,i)=>s=i<w|s==v&&s+v-~~a[i-w],s=0)?w:f(a,-~w)

Try it online!

Answer 9

05AB1E, 12 bytes

ā.Δ„üÿ.VO¨Å¿

Straight-forward modification of my 5-bytes inversed approach from the related challenge.

Try it online or verify all test cases.

Explanation:

ā             # Push a list in the range [1, input-length]
 .Δ           # Pop and find the first which is truthy for:
   „üÿ        #  Push string "üÿ", where the `ÿ` is automatically replaced with
              #  the integer using string interpolation
      .V      #  Execute it as 05AB1E code
              #  (`üN` creates all overlapping lists of size `N`)
        O     #  Sum each inner overlapping list
         ¨    #  Remove the last item
          Å¿  #  Check if the (implicit) input-list ends with this sublist
              # (after which the found result is output implicitly)

Answer 10

Haskell, 58 bytes

g n(h:t)l|t==init l=n|1>0=g(n+1)t$zipWith(+)t l
f l=g 1l l

Try it online!

Answer 11

Ruby, 59 58 bytes

->l{1.step.find{|a|l.each_cons(a+1).all?{|*h,g|g==h.sum}}}

Try it online!

Let's check:

This exploits a couple of ruby-specific shortcuts to achieve the final result.

->l{1.step.find{|a|

This is easy: starting from 1, repeat until we find the right number.

l.each_cons(a+1).all?{|*h,g|

Take every possible subarray of length a+1 and check.

g==h.sum}}}

Is the last element the sum of all other elements?

So, what happens if no match is found?

After the last check, when a+1 is the length of the array, and each_cons returns the whole array, we try to get all subarray of length a+2 (length of the whole array plus 1), the list is empty, and that satisfies the all? check, so if no answer is found, the answer is the length of the array.

Answer 12

Nibbles, 12.5 bytes

/|,~==<*~$.`'.`,$>$_+$>@_

Attempt This Online! / All testcases

/|,~==<*~$.`'.`,$>$_+$>@_
/|,~                      Find first number n such that
    ==                     equals
      <*~                   take all except the last 
         $                   n items of
          .                  for each row of
           `'                 transpose
             .                 for each i in
              `,                range from 0 to (excluding)
                $                n
                 >              drop the first
                  $              i items of
                   _              input
                    +         sum of
                     $         the row
                      >     drop the first
                       @     n items of
                        _     input

Answer 13

Japt, 18 16 bytes

@ãX mx ¯J eUtX}a

Try it

Port of @lyxal's Vyxal answer.

Explanation:

@             }a  # find the first positive integer X where:
 ãX               #   all overlapped sections of length X
    mx            #   sum each
       ¯J         #   remove the last item
          e       #   is this list equal to
           UtX    #   the last X elements of the input list?

Answer 14

Uiua # Experimental!, 22 21 characters

⊢▽⤚≡(≍↘¯1≡/+⊃◫↘)+1⊃⍏¤

Try it in the pad!

Thanks to jan for -1 character!

Answer 15

Charcoal, 23 bytes

Ｉ⌕Ｅ⊕Ｌθ⬤θ∨‹μι⁼Σ✂θ⁻μιμ¹λ¹

Try it online! Link is to verbose version of code. Explanation:

     θ                  Input array
    Ｌ                   Length
   ⊕                    Incremented
  Ｅ                     Map over implicit range
       θ                Input array
      ⬤                 All elements satisfy
          μ             Current index
         ‹              Is less than
           ι            Outer value
        ∨               Logical Or
               θ        Input array
              ✂     ¹   Every element from
                 μ      Current index
                ⁻       Minus
                  ι     Outer value
                   μ    To current index
             Σ          Take the sum
            ⁼           Equals
                     λ  Current element
 ⌕                      Find first index of
                      ¹ Literal integer `1`
Ｉ                       Cast to string
                        Implicitly print

In Charcoal, the Sum of an empty list is None, so the test for a 0-binacci-like sequence always fails.

Answer 16

Jelly, 13 bytes

+⁹\Ṗ;@ḣʋƑⱮJTḢ

Try it online! Or see the test-suite.

How?

+⁹\Ṗ;@ḣʋƑⱮJTḢ - Link: list of integers, A
          J   - range of length of A -> [1,2,3,...,length(A)]
         Ɱ    - map (for L in [1,2,3,...,length(A)]) with:
        Ƒ     -   is A invariant under?:
       ʋ      -     last four links as a dyad - f(A, L)
 ⁹\           -       L-wise overlapping cumulative reduce A with:
+             -         addition
   Ṗ          -       remove the final value
      ḣ       -       head A to index L
    ;@        -       concatenate -> first L terms of A then summed terms
           T  - truthy (1-indexed) indices
            Ḣ - head

Answer 17

Husk, 13 bytes

|L¹V€ṫ¹mhTm∫ṫ

Try it online!

          m ṫ  # for each of the tails of the input
           ∫   # get the cumulative sums,
         T     # transpose this list-of-lists,
       mh      # and remove the last element of each;
   V€          # now check if this is one of
     ṫ¹        # the tails of the input
               # (and output the index if it is)
|L¹            # otherwise, output the length of the input

Answer 18

Wolfram Language (Mathematica), 42 bytes

1//.a_/;MovingMap[Tr,#,a]!=2#~Drop~a:>a+1&

Try it online!

Uses the check from this answer to the challenge that inspired this one.

Answer 19

Pyth, 11 bytes

fqsM.:PQT>Q

Try it online!

Explanation

fqsM.:PQT>QT    # implicitly add T
                # implicitly assign Q = eval(input())
f               # return the first integer which satisfies lambda T
         >QT    # all but the first T elements of Q
 q              # is equal to
  sM            # map to their sums
    .:  T       # all sublists of length T of
      PQ        # all but the last element of Q

Answer 20

Uiua, 21 bytes

⍢(+1|¬≍↘¯1≡/+:⊙◫↘,,)1

Try it!

Starting with n = 1, increment until

• there is no match of
  • dropping the last of
    • the row-wise sums of
      • the n-wise windows of the input
  • and dropping the first n rows of the input

Answer 21

Uiua, 21 characters

⊢⊚⇌⊂1≡(≍/+:°⊂⇌◫)+1⊃⍏¤

Try it here! This Generates the Range from 1 to len with the "rise is range len for monotonically increasing lists" trick taken from the APL solution. It also takes inspiration from seeing that match ≍ even exists in the competition.

Answer 22

Julia 1.0, 56 bytes

\(L,l=[0L])=sum(l)!=L&&1+L[2:end]\(l=[l;[L]];pop!.(l);l)

Try it online!

recursive function. At step n, l stores the n first sub-lists of length length(L)-n and L is the last one. We iterate until sum(l)==L

Answer 23

Raku, 53 bytes

{first {none .rotor($^n+1=>-$n).map:{[R-] $_}},1..$_}

Try it online!

• first { ... }, 1 .. $_ returns the first number from 1 up to the size of the input list for which the brace-delimited anonymous function returns a true result. Within that function, $^n/$n is the number being tested. $_ continues to refer to the input parameter to the outer function.
• .rotor($^n + 1 => -$n) produces a moving window of size $n + 1 across the input list. For example, if the input list is 1, 3, 4, 7, 11, 18 and we're testing whether the list is 2-bonacci-like, the rotor method returns a list of the lists 1, 3, 4, 3, 4, 7, 4, 7, 11, and 7, 11, 18.
• .map: { [R-] $_ } reduces each of those lists with the reversed subtraction operator R-. (a R- b means b - a.) Because the regular subtraction operator - is left-associative, the reversed subtraction operator is right-associative, and so to continue the above example, it produces the numbers 4 - 3 - 1, 7 - 4 - 3, 11 - 7 - 4, and 18 - 11 - 7.
• Finally, none returns a truthy result if none of the reduced lists has a truthy value; that is, if all of them are zero.

Answer 24

C (gcc), 123 bytes

The function takes an array of ints for a and its length for z.

B(a,z,M,b,v,t,L)int*a;{int*c,*p;for(M=b=z;--b;M=v?M:b)for(c=a+z,v=0;c-b-a;v|=t)for(t=*--c,p=c-1,L=b;L--;)t-=*p--;return M;}

Try it online!