Is it a fibonacci-like sequence?

Question

The Fibonacci Sequence is a sequence of positive integers where the first two elements are 1 and the rest are the sum of the previous two. It begins \$1, 1, 2, 3, 5, 8, 13\$ and continues forever.

But what if you started with numbers other than \$1, 1\$? You could start with \$3, 4\$ and have the sequence go \$3, 4, 7, 11, 18, 29\cdots\$. Or you could start with \$2, 9\$ and have it go \$2, 9, 11, 20, 31, 51 \cdots\$.

Your challenge is to take a list of positive integers and determine if it could be part of some Fibonacci-like sequence. Essentially, determine if for each element but the first two, it's equal to the sum of the previous two.

Testcases

Truthy:

[1, 1, 2, 3, 5]
[6, 9, 15, 24]
[49, 71, 120, 191, 311, 502]
[3, 4, 7, 11]

Falsy:

[1, 2, 4]
[1, 1, 2, 3, 4]
[3, 4, 6, 8, 9]
[3, 9, 12, 15, 31]
[3, 4, 6, 10, 16]
[1, 1, 1, 2]

You can assume the input will be (non-strictly) increasing and have a length ≥ 3.

Answer 1

Shue, 149 bytes

=R
1,R=<,R
1<=<1
,<=*,
,*=*,
1*=i
i*=*i
,,R=t,R
it=t1
,t=T,
iT=T1
1,T=1,
T=L
L1=L
L,=L
LR
*=Xe
1t=e
1T=e
i,T=e
1e=e
ie=e
ei=e
e1=e
e,=e
,e=e
e=Xe
XeR

Try it online!

Returns "LR" for yes and "XeR" for no. Previous version didn't work for inputs like 1,1,111, so a few bytes went into fixing that.

Explanation

=R       - Right edge
1,R=<,R  - Spawn a triangle and decrement the last number
1<=<1    - Triangle passes trough the last element
,<=*,    - Triangle turns into star after last element
,*=*,    - Star passes trough commas
1*=i     - Reversibly "Decrement" the  element (i=0)
i*=*i    - Star passes trough zeros
,,R=t,R  - When done, send a test probe (t)
it=t1    - Test probe passes trough zeros, turning them to ones
,t=T,    - Upgrade test probe
iT=T1    - Still passes trough zeros
1,T=1,   - And when done, delete itself
T=L      - Or, if the left edge was reached, turn into L
L1=L     - L deletes everything to it's right
L,=L     - --||--
LR       - And finally, success
*=Xe     - Or, if the star reached the end, create error
1t=e     - Or if there weren't enough elements to delete last time, create error (b>c)
1T=e     - Same as before (a+b>c)
i,T=e    - Too many elements to delete (a+b<c) 
1e=e     - Errors propagate
ie=e     - --||--
ei=e     - --||--
e1=e     - --||--
e,=e     - --||--
,e=e     - --||--
e=Xe     - Unify error types
XeR      - Final error state

Example run:

1,1,11,
1,1,11,R
1,1,1<,R
1,1,<1,R
1,1*,1,R
1,i,1,R
1,i,<,R
1,i*,,R
1,*i,,R
1*,i,,R
i,i,,R
i,it,R
i,t1,R
iT,1,R
T1,1,R
L1,1,R
L,1,R
L1,R
L,R
LR

Example run 2

1,1,111,
1,1,111,R
1,1,11<,R
1,1,1<1,R
1,1,<11,R
1,1*,11,R
1,i,11,R
1,i,1<,R
1,i,<1,R
1,i*,1,R
1,*i,1,R
1*,i,1,R
i,i,1,R
i,i,<,R
i,i*,R
i,*i,R
i*,i,R
*i,i,R
Xe,i,R
Xei,R
Xe,R
XeR

Answer 2

R, 46 41 42 38 bytes

Edit: Bug-fix for +1 byte thanks to pajonk, but then -4 bytes by adopting Giuseppe's use of head with a negative n...

function(x)any(diff(x)[-1]-head(x,-2))

Try it online!

Function not_fiblike outputs TRUE if the input x is not a fibonacci-like sequence, FALSE if it is one.

Answer 3

Wolfram Mathematica 34 29 bytes

 2#~Drop~2==MovingMap[Tr,#,2]&

–5 bytes from @att

Try it online!

[Included the [3,4,6,10,16] and [1,1,1,2] falsey test cases from Noodle9 and DLosc, respectively.]

Answer 4

Python, 31 bytes

def f(a,*d):a+d[0]-d[1]or f(*d)

Attempt This Online!

-3 bytes thanks to @emanresuA.

Outputs via presence of an exception or not.

Answer 5

Wolfram Language (Mathematica), 43 38 31 bytes

#[[;;-3]]+#[[2;;-2]]==#[[3;;]]&

Try it online!

Previously I had a 43-byte version using Partition, which simplifies to a 39-byte solution with BlockMap:

And@@BlockMap[Plus@@#==2#[[3]]&,#,3,1]&

In case it gives anyone ideas, there is a 44-byte solution using a function specifically for generating linear recurrences:

#==LinearRecurrence[{1,1},#[[;;2]],Tr[1^#]]&

Answer 6

R, 40 bytes

function(l)any(diff(l,2)-head(l,-1)[-1])

Try it online!

Returns FALSE for Fibonacci-like sequences, and TRUE otherwise.

Slightly different approach than Dominic van Essen's, takes the lag-2 differences of l and compares to the list with the first and last elements removed, relying on the following idea:

\$F_{n+1}=F_{n}+F_{n-1}\Rightarrow F_n=F_{n+1}-F_{n-1}\$

Answer 7

Jelly, 4 bytes

IḊw@

Attempt This Online!

I      differences between consecutive elements
 Ḋ     remove the first item
  w@   find the sublist index of this in the input

1 is truthy and all other values are falsey.

Answer 8

Pari/GP, 27 bytes

a->#Pol(Ser(a)*(1-x-x^2))<3

A sequence is Fibonacci-like if and only if its generating function is of the form \$\frac{a+b\ x}{1-x-x^2}\$.

Try it online!

Answer 9

Julia, 48 44 43 bytes

~f=0∉3:length(f).|>i->f[i]==f[i-2]+f[i-1]

Try it online!

Answer 10

JavaScript (Node.js), 32 bytes

• -1 byte by l4m2

a=>!a.some(n=>n+a[i]-a[++i],i=1)

Try it online!

Answer 11

Dyalog APL, 11 10 bytes

⊃2∘↓⍷2+/⊢

-1 thanks to @DLosc.

Try it online!

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

 2∘↓      Is the array with the first two elements removed         (2 3 5)
    ⍷     a subarray of
     2+/⊢ the sum of each consecutive pair of numbers in the array (2 3 5 8)
⊃         at the first position?

Answer 12

Haskell, 34 bytes

g(a:l@(b:c:_))=a+b==c&&g l;g _=0<1

Try it online!

• Thanks to @Laikoni for suggesting a recursive approach 1 Byte shorter

• Original solution 35 bytes

g l@(a:b:c)=zipWith(-)c l==b:init c

Try it online!

Answer 13

Curry (PAKCS), 22 bytes

-3 bytes thanks to Wheat Wizard.

f(_++a:b:c:_)|a+b/=c=0

Try it online!

This returns nothing if the input is Fibonacci-like, and 0 otherwise.

Answer 14

Python 2, 39 bytes

• -3 bytes by loopy walt

lambda a:map(sum,zip(a[1:-1],a))==a[2:]

Try it online!

---

Python 3 + NumPy, 35 bytes

lambda a:all(a[1:-1]+a[:-2]==a[2:])

Try it online!

Answer 15

05AB1E, 4 bytes

¥¦Å?

Port of @pxeger's Jelly answer.

Try it online or verify all test cases.

An inversed version is also possible, but would be a byte longer:

ü+¨Å¿

Try it online or verify all test cases.

Explanation:

       #  e.g. input = [49,71,120,191,311,502]

¥      # Get the deltas/forward-differences of the (implicit) input-list
       #  STACK: [22,49,71,120,191]
 ¦     # Remove the first item
       #  STACK: [49,71,120,191]
  Å?   # Check if the (implicit) input-list starts with this sublist
       #  STACK: 1
       # (after which the result is output implicitly)

ü      # For each overlapping pair of the (implicit) input-list:
 +     #  Add them together
       #   STACK: [120,191,311,502,813]
  ¨    # Remove the last item
       #   STACK: [120,191,311,502]
   Å¿  # Check if the (implicit) input-list ends with this sublist
       #   STACK: 1
       # (after which the result is output implicitly)

Answer 16

MATL, 10 bytes

d4L)tfGw)=

Try it online!

Just the usual: take the pairwise difference, discard the first, chop off the last two elements of input, compare.

---

Alternate:

MATL, 17 16 bytes

tnwTTZ+2YSG=s-I<

Try it online!

Perform a convolution of the input with [1 1], circularly shift the result twice to align the sums, compare with input, and see that the last n - 2 values match. (The last two bytes might as well be 2= I think, but it's the same byte count anyway.)

Previous solution: TT2&Y+3L)G&m2-tf=
Perform a convolution of the input with [1 1], and check that the 1:n-1 values of the result (excluding the last sum) are present in the input at right index.

---

Output is all 1s (in both solutions) for truthy.

Answer 17

Husk, 5 6 5 bytes

€¹tẊ-

Try it online!

Outputs 1 for truthy (it's a fibonacci-like sequence), any other non-negative integer for falsy (it isn't a fibonacci-like sequence).

Get the pairwise differences (Ẋ-), remove the first one (t), and check if this is an ordered sublist of the input find the index of this sublist in the input (€ḣ¹), or 0 if not present.

Of course, it needs to be a prefix of the input (rather than a sublist at any other position), but I think this should be ensured since the input is increasing. Edit: the fact that the input is increasing does not ensure that sublists must be prefixes (consider 1 2 4 with difference sublist 2), so we check this by requiring that the index of the sublist must be 1.

Answer 18

80386 machine code, 19 16 bytes

\x49\x49\x8b\x44\x8a\x04\x2b\x04\x8a\x2b\x44\x8a\xfc\xe1\xf3\xc3

Try it online!

Applying @PeterCordes's suggestion to remove setz saved 3 bytes. I first considered simply returning al as a boolean value, but then the problem is that a non-zero value will represent false and zero will represent true. I felt it's not clear-cut whether this is okay.

Now, the function works as returning the zero flag. Thus, it is not possible to be directly called from C as before. If you follow the TIO link, there is a wrapper function to interface with this assembly function returning a flag value. Since I'll usually have to write such wrapper when calling functions from other languages, I think this approach is okay.

Thanks to @Deadcode for letting me know a nice way to translate the flag to a value in the wrapper function.

assembly (nasm)

testfib: ; fastcall, ecx = length of array, edx = pointer to array
    dec ecx
    dec ecx
.loop:
    mov eax, [edx + ecx * 4 + 4]
    sub eax, [edx + ecx * 4]
    sub eax, [edx + ecx * 4 - 4]
    loopz .loop
    ret

Answer 19

Desmos, 37 bytes

f(l)=min(1-sign(l[3...]-l[2...]-l)^2)

Try It On Desmos!

Try It On Desmos! - Prettified

Tell me if there is anything wrong. I made this answer faster than usual :D

Answer 20

Python 3.8 (pre-release), 46 bytes

f=lambda n:n[2:]and(n[0]+n[1]-n[2]or f(n[1:]))

Try it online!

Recursion is shorter than doing all(... for i,e in enumerate(n)).

-2 by @emanresuA, -4 by @pxeger. What am I doing today...

Answer 21

Factor, 30 bytes

[ dup differences rest head? ]

Try it online!

Explanation

Does the input start with its differences sans the first?

              ! { 1 1 2 3 5 }
dup           ! { 1 1 2 3 5 } { 1 1 2 3 5 }
differences   ! { 1 1 2 3 5 } { 0 1 1 2 }
rest          ! { 1 1 2 3 5 } { 1 1 2 }
head?         ! t

Answer 22

C (gcc), ^{58 57} 51 bytes

r;f(a,n)int*a;{for(r=0;n-->2;)r|=*a+*++a-a[1];n=r;}

Try it online!

Saved 6 bytes thanks to pxeger!!!

Inputs a pointer to an array on integers and its length (because pointers in C carry no length info).
Returns \$0\$ if its a Fibonacci-like sequence or a truthy value otherwise.

Answer 23

C (GCC), 44 bytes

f(a,n)int*a;{n=*a+*++a-a[1]||--n>2&&f(a,n);}

Attempt This Online!

-1 byte by inverting output, thanks to @AZTECCO

Recursive.

Answer 24

BQN, 14 13 bytes

+´↑∊·2⊸↓⊸⋈⊢-»

Try it at BQN online REPL

              »     # shift the input array right,
             -      # and subtract this from
            ⊢       # the input;
     ·2⊸↓           # now drop the first two elements,
          ⊸⋈       # and make a list of this list,
    ∊               # and check whether this equals
   ↑                # any prefix of the input;
×´                  # finally get the product to check if all are true.

Answer 25

J, ³⁸ 12 bytes

2{]E.~2+/\}:

Or

2&}.-:2+/\}:

-26 bytes, thanks @Jonah

Try it online!

Answer 26

Standard ML (MLton), 51 48 45 bytes

fun$(x::y::z::L)=x+y=z andalso$(tl L)| $_=1=1

Try it online!

-3 bytes thanks to Laikoni.

-3 bytes using tl to recurse instead of pattern matching.

Answer 27

Retina 0.8.2, 38 37 bytes

\d+
$*
^((1+),(?=(1+),\2\3\b))+1+,1+$

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert to unary.

^((1+),(?=(1+),\2\3\b))+

Repeatedly match a number, each time checking that the number two ahead is the sum of it and the next number.

1+,1+$

Match the final two numbers.

Previous 38-byte version used .NET's ability to recapture an existing named or numbered group:

\d+
$*
^(1+),(1+)(,(?<2>\1(?<1>\2)))+$

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert to unary.

^(1+),(1+)

Match two numbers \1 and \2...

(,(?<2>\1(?<1>\2)))+$

... then repeatedly match numbers that are the sum of \1 and \2, but recapture \1 as \2 and \2 as the sum, so that each number has to be the sum of the previous two.

Answer 28

APL+WIN, 26 bytes

Prompts for input

(¯2+⍴v)=+/(¯2↓v)=1↓-2-/v←⎕

Try it online! Thanks to Dyalog Classic

Answer 29

PowerShell Core, 53 bytes

!(3..($a=$args).length|?{$a[--$_-2]+$a[$_-1]-$a[$_]})

Try it online!

Takes a list of numbers as parameter and returns a boolean

Answer 30

C#, 114 113 bytes

var a=args;int i=0,r=0;for(;i<a.Length-2;)if(int.Parse(a[i])+int.Parse(a[i+1])!=int.Parse(a[i+++2]))r=1;return r;

Program expects the list to be passed as a list of command line arguments, e.g.:

./program 1 2 3 5 8

Program uses C# v9 top-level statements feature, this is a full C# program. Unwrapped:

var a = args;
int i = 0, r = 0;
for (; i < a.Length - 2;)
    if (int.Parse(a[i]) + int.Parse(a[i + 1]) != int.Parse(a[i++ + 2]))
        r = 1;
return r;