29
\$\begingroup\$

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 , 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
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Suggested test cases: [1, 2, 2] -> 3, [2, 3, 4, 7] -> 4. \$\endgroup\$
    – Neil
    Feb 28 at 0:17
  • \$\begingroup\$ Related. \$\endgroup\$
    – alephalpha
    Feb 28 at 10:23

16 Answers 16

8
\$\begingroup\$

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!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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! \$\endgroup\$
    – Giuseppe
    Feb 28 at 17:06
  • \$\begingroup\$ @Giuseppe - Thanks! \$\endgroup\$ Feb 28 at 21:12
  • \$\begingroup\$ 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 \$\endgroup\$ Mar 1 at 12:46
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ Mar 1 at 13:29
  • \$\begingroup\$ 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. \$\endgroup\$
    – qwr
    Mar 3 at 4:47
6
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

Vyxal, 14 bytes

λ?$lƛṫ$∑=;A;ṅ‹

Try it Online!

Explained

λ?$lƛṫ$∑=;A;ṅ‹
λ          ;ṅ  # Get the first positive integer n where:
 ?$lƛ    ;A    #   all overlapping windows of size of n:
     ṫ$∑       #     have the sum of every item but the last
        =      #     equal to the last item
             ‹ # decrement n
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

Dyalog APL, 15 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
\$\endgroup\$
1
  • \$\begingroup\$ I independently came up with a similar solution, but mine is 17 bytes because I'm silly :P ⊃∘⍸⍳∘≢(⊃⊢⍷↑,+⌿)¨⊂ \$\endgroup\$
    – RGS
    Feb 28 at 11:02
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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!

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

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!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 23 bytes

I⌕E⊕Lθ⬤θ∨‹μι⁼Σ✂θ⁻μιμ¹λ¹

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
              ✂     ¹   Every element from
                 μ      Current index
                ⁻       Minus
                  ι     Outer value
                   μ    To current index
             Σ          Take the sum
            ⁼           Equals
                     λ  Current element
 ⌕                      Find first index of
                      ¹ 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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.