# How-many-bonacci-like is this sequence?

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.

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

• Suggested test cases: [1, 2, 2] -> 3, [2, 3, 4, 7] -> 4.
– Neil
Feb 28, 2022 at 0:17
• Feb 28, 2022 at 10:23

# R, 9178 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!

• 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! Feb 28, 2022 at 17:06
• @Giuseppe - Thanks! Feb 28, 2022 at 21:12
• 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 Mar 1, 2022 at 12:46
• @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. Mar 1, 2022 at 13:29
• 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.
– qwr
Mar 3, 2022 at 4:47

# Vyxal, 1412 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:]

• 10 Jan 19, 2023 at 23:38

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

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

# 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

• I independently came up with a similar solution, but mine is 17 bytes because I'm silly :P ⊃∘⍸⍳∘≢(⊃⊢⍷↑,+⌿)¨⊂
– RGS
Feb 28, 2022 at 11:02
• use grade instead of ⍳∘≢ Dec 1, 2023 at 20:21
• Thank you very much! Dec 3, 2023 at 1:04

# 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


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

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

• f=(a,w)=>a.every((v,i)=>s=i<w|s==v&&s+v-~~a[i-w],s=0)?w:f(a,-~w)
– tsh
Feb 28, 2022 at 3:14

# 05AB1E, 12 bytes

ā.Δ„üÿ.VO¨Å¿


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

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)


# 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! # 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. # Nibbles, 12.5 bytes /|,~==<*~$.'.,$>$_+$>@_  /|,~==<*~$.'.,$>$_+$>@_ /|,~ 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  # 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?  # 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. # 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  # 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  # 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. # 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  # 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 # 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.

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

• 120 bytes May 1, 2023 at 1:25