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

• Neil: Suggested test cases: [1, 2, 2] -> 3, [2, 3, 4, 7] -> 4.
• alephalpha: Related.
• noodle person: May we output zero-indexed?
• alephalpha: @noodleperson Do you mean outputting \$n-1\$ for \$n$-bonacci-like sequences? There are already so many answers. Changing the rule now might be unfair to them.

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!

• Giuseppe: Use 0:-T to save a byte. The offset with c(0,x) to index exactly once and avoid any of the usual matrix exceptions with [...,drop=T] is quite clever!
• Dominic van Essen: @Giuseppe - Thanks!
• Chechy Levas: just curious about something: why don't I see R solutions using the shorter \(x)... syntax for functions? EDIT: I don't think TIO supports the new syntax
• Dominic van Essen: @ChechyLevas - your EDIT is correct. If the only gain is by saving 7 bytes (function > \) it seems boring, and not worth the annoyance of losing TIO support (although you can still use rdrr.io). Here there's only one function definition so I didn't bother... Sometimes, though, it can make a non-trivial difference: for instance, it can encourage approaches with more-than-one function definition, that could be prohibitively long with R v≤4.0, but golfy in R ≥v4.1.
• qwr: The issue is TIO not being updated, not anything wrong with R. github.com/TryItOnline/tryitonline There was a meta post about it, can't find it now. I personally use a local copy of R.

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:]

• emanresu A: 10

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

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 6

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

• RGS: I independently came up with a similar solution, but mine is 17 bytes because I'm silly :P ⊃∘⍸⍳∘≢(⊃⊢⍷↑,+⌿)¨⊂
• FrownyFrog: use grade instead of ⍳∘≢
• rabbitgrowth: Thank you very much!

Answer 7

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 8

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 9

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!

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

Answer 10

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

Uiua, (削除) 22 (削除ここまで) 21 characters

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

Try it in the pad!

Thanks to jan for -1 character!

• jan: +1⊃⍏¤ is one better than ⊙¤+1°⊏, even though unselect is a cool function.

Answer 14

Jelly, 13 bytes

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

Try it online! Or see the test-suite.

How?

+9\Ṗ;@ḣʋƑⱮ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)
 9\ - 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 15

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 16

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 17

Uiua, (削除) 21 (削除ここまで) 16 bytes

⍢+1(¬≍↘ ̄1⊃⧈/+↘)1

Try it!

• ⍢+1(...)1 Starting with 1, increment until:
  • ¬≍ there is no match between
    • ↘ ̄1 dropping the last of
      • ⧈/+ the sums of the n-wise windows of the input
    • ↘ and dropping the first n rows of the input

Answer 18

Jelly, 9 bytes

UμṡJ§Ḋ€oi

Try it online!

This started as an attempt at suggesting a minor golf to Jonathan Allan's solution out of frustration at +9\ actually making sense to use over ṡ§ (being one fewer link to group), but by the time it was even close to saving anything it was barely recognizable!

U Reverse the input.
 J For each [1 .. length],
 ṡ take all overlapping slices of that length
 § and sum the elements in each slice.
 Ḋ€ Remove the first sum at each length,
 o element-wise logical OR each list of remaining sums with
Uμ the input reversed,
Uμ i and return the first index of the reversed input.

Relies on the guarantee of strictly positive input in order to use o for is-prefix checking, by exploiting Jelly's handling of mismatched lengths for dyadic operations: all elements of the longer element past the end of the shorter element are left unchanged, so for lists of truthy values x and y, x o y is equal to y iff x is a prefix of y. Hence, the input is reversed to transform suffix-checking into prefix-checking.

A late Ḋ€ after § is necessary rather than Ḋ before ṡ in order to handle length-1 inputs appropriately. There are no possible slices of any length greater than the length of the argument to ṡ, so it produces an empty list in such cases. § vectorizes "at depth 1" in Jelly's dynamic nested ragged lists model, meaning it recurs on each element of its argument until it's called on a list with only scalar elements and sums that, so when it reaches that empty list it sums that to a flat 0. This is entirely unproblematic for input lengths greater than 1, because when that 0 is at the end of a list of lists of slice sums, the list has a greater depth than the (reversed) input, so o broadcasts over the entire list and subsequently broadcasts the 0 as a scalar to o with each element (and replace by that element, since it's falsy)... but with a length-1 input, removing its first element before slicing such that we attempt to get length-1 slices of an empty string, the entire list of lists of slice sums is just [0] which has the same depth as the input and zips with it with no broadcasting, producing the exact value of the input which is not contained within itself and thus gives a faulty index of 0. So, on that token, UμḊṡJ§o€i works equally well (and is arguably just overall sounder in principle) by replacing the unreliable broadcast with an explicit map, but then this explanation would feel even more gratuitous :P

Answer 19

Charcoal, 23 bytes

I⌕E⊕Lθ⬤θ∨‹μι=Σ✂θ−μιμ1λ1

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

 θ Input array
 L Length
 ⊕ Incremented
 E Map over implicit range
 θ Input array
 ⬤ All elements satisfy
 μ Current index
 ‹ Is less than
 ι Outer value
 ∨ Logical Or
 θ Input array
 ✂ 1 Every element from
 μ Current index
 − Minus
 ι Outer value
 μ To current index
 Σ Take the sum
 = Equals
 λ Current element
 ⌕ Find first index of
 1 Literal integer `1`
I 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 20

Husk, 13 bytes

|L1V€ṫ1mhTm∫ṫ

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
 ṫ1 # the tails of the input
 # (and output the index if it is)
|L1 # otherwise, output the length of the input

Answer 21

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 22

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 23

☾, 25 chars

code

󰲡1+←x⭥󰑅󷺻xᙧ0󰄎􍪴ᙧ⭥2ꟿ󷺹⨁≡⟝􍨄󷺿→⋀

Test the code here. Yes, I do know I already answered with Uiua, but I love this language so much that I couldn't resist.

Explanation

explanation

Answer 24

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 25

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 26

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!

• ceilingcat: 120 bytes