# Is it a fibonacci-like sequence?

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.

• Will input always contain at least 3 numbers? Or will [1] and [1,1] consider valid?
– tsh
Feb 17 at 8:33
• @tsh Input will always contain at least three numbers Feb 17 at 8:33
• Suggest adding or changing a falsy testcase to one that fails just at the beginning (to edge testcase backwards calculations). eg [3, 4, 6, 10, 16] Feb 17 at 10:17
• If you want just the increasing part of the Lucas numbers, start with 1, 3. Feb 18 at 6:12
• Suggested test case: [1, 1, 1, 2] (all sums of adjacent pairs except the last appear in the sequence, but output should be falsey) Feb 19 at 16:31

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

• give this man a bounty for using the new lang "Shue"! Feb 17 at 13:20
• I'm trying to run this with an input of 1,1,11, on my local machine, since it times out on TIO, and it's taking a very long time. How long did it take for 1,1,111, when you ran it? Feb 19 at 5:06
• @DLosc whoops, I forgot to add an error propagation rule, fixed now. The link contains an optimized version, which doesn't consider strings that have more than one "R". It can now run 1,1,111, and others in TIO. Feb 19 at 7:52
• Ah, nice. I think another approach, which isn't quite as fast but doesn't require changing the interpreter, is to change the first line from =R to 1,=<,R. Feb 19 at 15:00

# R, 464142 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.

• 40 bytes :-) Feb 17 at 17:14
• Looks like it fails for c(3, 3, 6); if I understand correctly ! in seq should fix it for +1: Try it online! Feb 17 at 19:07
• @pajonk - thanks! Feb 17 at 22:20

# Wolfram Mathematica34 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.]

• 29 bytes
– att
Feb 18 at 6:21
• Nice trick using the doubled sequence :) Feb 18 at 18:47

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

• Save three more bytes by not using b or c Feb 17 at 9:04

# 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}\$$

• I love the use of the lag parameter for diff, that I'd never previously seen a use for! But I'm afraid I've stolen your use of a negative n for head... Feb 17 at 23:47
• @DominicvanEssen you have to know your tips! Feb 18 at 0:50

# Wolfram Language (Mathematica), 4338 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^#]]&

• == isn't Listable, so you don't need And@@
– att
Feb 18 at 6:21
• Also, BlockMap is shorthand for mapping over Partition
– att
Feb 18 at 6:22
• There's also this 37 byte one that's nearly competitive: {-1,1,1}~ListConvolve~#~MatchQ~{0..}& Feb 18 at 7:27
• Better, 0==##&@@... for 32
– att
Feb 18 at 7:36
• Rest@Differences@#==#~Drop~-2& for 30 bytes (or Rest@Differences@#==#[[;;-3]]&) Feb 18 at 7:53

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

• IḊẇ - 3 bytes, uses 1/0 for truthy/falsey Feb 17 at 18:42
• The shortening to 3 bytes doesn't work for sequences like 1, 3, 6, 12, 24, ... Feb 18 at 19:09

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

# Julia, 4844 43 bytes

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


Try it online!

• please use all instead of !(0 in(, it hurts my eyes Feb 17 at 23:20
• Cool, I didn't know that function. Feb 18 at 0:57
• Please use 0∉ instead of all, it hurts my eyes (~f=0∉3:length(f).|>i->f[i]==f[i-2]+f[i-1]) Feb 18 at 1:06
• @dingledooper I'm wondering the whole time if there is a clever way to get rid of the length statement. This is costly and I needed a in most challenges so far. Feb 18 at 1:13
• This gets you to 29: ~f=diff(f)[2:end]==f[1:end-2]. The slicing part is annoyingly verbose and it could probably be improved, but it's a lot better than the "long way". Feb 18 at 1:36

# JavaScript (Node.js), 32 bytes

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


Try it online!

• 32
– l4m2
Feb 17 at 10:21

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!

• The simple recursive approach is one byte shorter: Try it online! Feb 21 at 16:03

# Python 2, 39 bytes

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!

• -3 Feb 17 at 9:20

# 05AB1E, 4 bytes

¥¦Å?


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

ü+¨Å¿


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:
#   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)


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

# Husk, 56 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.

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

• Thanks! Just updated my answer. Feb 20 at 3:10

# 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

• You can return in ZF if you want, avoiding the setz: Tips for golfing in x86/x64 machine code. The language of your answer is pure asm / machine code, not including C calling conventions. Also, EAX will already be zero or non-zero after sub to match ZF, so you can call that the integer return value. (0 or non-zero are equally easy to test for a caller, so both are valid choices for "truthy" in asm.) Feb 19 at 6:14
• Anyway, interesting approach; I was thinking of loading the first 2 and then computing forward (with xchg/add or xadd as in Golf a Custom Fibonacci Sequence) and compare against memory. And take a pointer in esi for lodsd / xchg eax, edx / lodsd. Possibly take an end-pointer instead of a count, for looping with cmp/jne? But then you'd need some other way to break out of the loop, like possibly scasd/jne as well. Your idea to use loopz is nice. Feb 19 at 6:23
• Can you post an objdump to show how the bytes map to instructions? I guess the mov instructions look pretty complicated. ecx is changing from loopz?
– qwr
Feb 19 at 9:30
• @qwr Here. Yes, loopz decrements ecx. Feb 19 at 11:41
• @PeterCordes I applied your suggestion. BTW, is that second link correct? I think that post is suggesting that only 1 can represent "true" for functions returning an integer value. Feb 19 at 13:59

# 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

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

# Factor, 30 bytes

[ dup differences rest head? ]


Try it online!

## Explanation

              ! { 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 }


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

• 51 bytes: r;f(a,n)int*a;{for(r=0;n-->2;)r|=*a+*++a-a[1];n=r;} Feb 17 at 12:01
• @pxeger Nice one - thanks! :))) Feb 17 at 12:13
• @pxeger: Just for the record, *a and a[1] are unsequenced wrt. *++a in that, so it's perhaps worth mentioning that reliance on this happens-to-work implementation detail of how GCC -O0 handles this undefined behaviour. (Beyond the usual nasty hacktastic return value via a gcc -O0 implementation detail mentioned in the C golfing tips Q&A.) Still a valid code golf answer, just worth mentioning this abuse of C to get the compiler to make working asm. Feb 19 at 5:57
• @PeterCordes I actually tried *a+++*a-a[1] at first, which didn't work! So yes, I'm aware ;) Feb 19 at 7:01
• @PeterCordes Avert thine eye, code golfing is not for the pure of heart! Lots of terrible hacks here that rely solely on specific flags and the direction of the wind! T_T Feb 19 at 8:54

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

• misread that title as "CGCC" Feb 17 at 17:15

# J, 38 12 bytes

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


Or

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


-26 bytes, thanks @Jonah

Try it online!

• APL answers approach for 14: 2(1{.}.E.+/\)] Feb 24 at 12:40
• Actually, 12: 2{]E.~2+/\}:. Another variation: 2&}.-:2+/\}: Feb 24 at 12:47

# Standard ML (MLton), 5148 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. • Save two bytes by replacing f with a symbol, e.g. $, and another byte by replacing true with 1=1: Try it online! Feb 21 at 15:54

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

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

# APL+WIN, 26 bytes

Prompts for input

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


Try it online! Thanks to Dyalog Classic

# 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

• -19 bytes. awesome! Feb 18 at 8:18

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


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

• It is permitted to write a function instead of a full program to save a lot of bytes.
– qwr
Feb 18 at 20:50
• Also a recursive solution may be shorter
– qwr
Feb 18 at 20:51