# FIBonacci sequence

For this code golf, you will receive an input of a fibonacci sequence, that is, a normal Fibonacci sequence but with one number incorrect. See, the sequence is fibbing! Get it? :D

Your job is to find out which number is incorrect, and print the index (0-based) of that number.

For example:

Input : 1 1 2 9 5 8 13
Output: 3

Input : 8 13 21 34 55 80
Output: 5

Input : 2 3 5 5 13 21
Output: 3


Specifications:

• The sequence may start at any number.
• The first two numbers of the input will always be correct.
• Shortest code (character count) wins.
• Does the input have to be space-delimited or can commas be used as well? – Volatility Jun 23 '13 at 0:26
• @Volatility Input is space-delimited. – Doorknob Jun 23 '13 at 0:33
• The job is to find only the first such number, right? For example, if you started from the right in the first sequence you could think that 8 is incorrect because it doesn't equal 9+5 – Luis Mendo Jan 23 '15 at 16:40
• @LuisMendo There will always be only one such number. – Doorknob Jan 23 '15 at 16:48
• @LuisMendo Okay, let me reword that: There will always be exactly one way to change a single number that causes the sequence to be correct. – Doorknob Jan 23 '15 at 16:53

## GolfScript (18 chars)

~]:^,,{^>3<~-+}?2+


The key to keeping this short is ? (find).

• +1 for the portrait of Fibonacci ~]:^, – gnibbler Jun 26 '13 at 5:26

## J, 30 23

(2+0 i.~2&}.=[:}:}:+}.)


## Golfscript, 31282625 23

~]-1%~1{)\3$3$-=}do])\;


## APL (19)

1+1⍳⍨(1↓1⌽k)≠2+/k←⎕


Explanation:

• k←⎕: store user input in k
• 2+/k: sum each pair of elements in k (i.e. 1 1 2 3 -> 1+1 1+2 2+3 -> 2 3 5)
• 1↓1⌽k: rotate k to the right by 1 and then drop the first element (i.e. 1 1 2 3 -> 2 3 1)
• ≠: find the place where these lists are not equal
• 1⍳⍨: find the location of the first 1 in this list (location of the incorrect number)
• 1+: add 1 to compensate for the dropped element

# K, 32

{2+*&~(n@n@x)=x+(n:{1_x,x 0})@x}


# dc, 36 32

?zszsasb[lalbdsa+dsb=x]dsxxlzz-p


dc is a reverse-Polish calculator, so obviously you need to input the numbers in reverse order ;)

$dc fib.dc <<< "999 13 8 5 3 2 1 1" 7$ dc fib.dc <<< "999 1 1"
2


# Javascript (69686160 55)

for(s=prompt(i=2).split(' ');s[i]-s[i-1]==s[i-2];i++);i


(60)

s=prompt(i=2).split(' ');for(;s[i]==+s[i-1]+ +s[i++-2];);--i


(61)

s=prompt(i=1).split(' ');for(k=+s[1];k+=+s[i-1],k==s[++i];);i


(68)

s=prompt(i=1).split(' ');for(k=+s[1];k+=+s[i-1],k==s[++i];);alert(i)


(69)

s=prompt(i=1).split(' ');k=+s[1];for(;k+=+s[i-1],k==s[++i];);alert(i)


# Awk: 55

{for(i=3;i<=NF;i++)if($i+$(i-1)!=$(i+1)){print i;exit}}  ## JavaScript, 70 for(n=prompt().split(' '),i=n.length;i---2;)if(n[i-2]- -n[i-1]!=n[i])i  # Ruby, 66 My first attempt at an (somewhat) complicated Ruby program: p gets.split.map(&:to_i).each_cons(3).find_index{|a,b,c|a+b!=c}+2  • You can save quite a few characters if you replace gets.split with $* (ARGV) to take input as command line arguments instead of on the standard input stream. The space between p and $* can then also be safely removed. – britishtea Jan 23 '15 at 18:38 # Python, 74 a=map(int,raw_input().split()) i=2 while a[i-2]+a[i-1]==a[i]:i+=1 print i  I had this solution first, but Doorknob answered the question about the format of input right before I had time to post it: # Python, 66 a,b=input(),input() i=2 while input()==a+b:a,b=b,a+b;i+=1 print i  Assumes newline separated input. VB.net (77) Assuming the numbers are already in a IEnumerable(Of Integer).  Dim p = xs.Skip(2).TakeWhile(Function(c, i) c = xs.Skip(i).Take(2).Sum).Count + 2  # JS, 52B for(s=prompt(i=2).split ;s[i]-s[i-1]==s[i++-2];);i  # Matlab / Octave, 39 bytes Thanks to Stewie Griffin for saving a byte! (- instread of ~=) @(x)find(diff(x(2:end))-x(1:end-2),1)+1  This is an anonymous function that inputs an array and outputs a number. Try it online! # Kotlin, 77 bytes {val r=it.split(' ').map{it.toInt()} var i=2 while(r[i]==r[i-1]+r[i-2])i++ i}  ## Beautified { val r = it.split(' ').map { it.toInt() } var i=2 while(r[i] == r[i-1] + r[i-2]) i++ i }  ## Test var f:(String)->Int = {val r=it.split(' ').map{it.toInt()} var i=2 while(r[i]==r[i-1]+r[i-2])i++ i} data class Test(val input: String, val output: Int) val TESTS = listOf( Test("1 1 2 9 5 8 13", 3), Test("8 13 21 34 55 80", 5), Test("2 3 5 5 13 21", 3) ) fun main(args: Array<String>) { val fails = TESTS .asSequence() .map { it to f(it.input) } .filter { (test, res) -> test.output != res } .toList() if (fails.isEmpty()) { println("Test Passed") } else { fails.forEach{ println(it)} } }  # Raku, 45 bytes {first :k,?*,(@($/=.words)Z-($0,$1,*+*...*))}


Try it online!

$/ = .words stores the words (numbers) of the input string into the pattern-match variable $/. Conveniently, the elements of that variable can be accessed with $0, $1, etc, so $0,$1, * + * ... * forms the Fibonacci sequence starting with the first two input numbers. The input numbers and the Fibonacci sequence are then zipped together using the subtraction operator (Z-), forming a new sequence which is nonzero only at the place where the two series are different. Then first :k, ?*, ... returns the index (thanks to the :k parameter) of that location; ?* is an anonymous predicate function that coerces its argument to a boolean value.

## Python (90)

a=map(int,raw_input().split())
print min(i for i in range(2,len(a))if a[i-2]+a[i-1]!=a[i])


# Mathematica 59

Because space-delimited input is required, StringSplit needs to be employed. The following assumes that the input is in the form of a string i.

s = StringSplit@i;
p = 3; While[s[[p - 1]] + s[[p - 2]] == s[[p]], p++]; p - 1


f l=length$fst$span id$zipWith(==)l$1:scanl(+)1l


# Jelly, 11 bytes

ÆḞ€i\$€In1i1


Try it online!

# QBIC, 31 bytes

_!_!{_!~a+b=c|a=b┘b=c┘s=s+1\_Xs


## Explanation

_!_!           Ask the user for two umbers, assign them to 'a' and 'b'
{              DO
_!            Ask for a third number (this will be assigned to 'c' on every iteration)
~a+b=c        IF the previous two terms add up to the third
|a=b          THEN shift b into a,
┘b=c            and c into b
┘s=s+1          increment s (starts as 3 in QBIC)
\_Xs          ELSE quit, printing the step counter


I'm not quite sure if this is allowed; the sequence is entered one term at a time, and the program aborts on error, not after entering the entire sequence.

# Pxem, 0 bytes (content) + 52 bytes (filename).

• Filename (escaped): \002._._X.w.c.t.v.m.v.+._.c.t.v.m.v.-\001.r.x.n.d.a\001.+.vX.a

## Usage

• From stdin
• Must be an actual FIBonacci sequence
• Each integer are separated with blank characters

XX.z
# Initial stack: F(i-1), F(i-2), i
# i is initially 2
.a\002._._XX.z
# while :; do
.aX.wXX.z
# to: (F(i-1)+F(i-2)), i, F(i-1)
.a.c.t.v.m.v.+XX.z
# input is F(i)
# to: F(i), (F(i-1)+F(i-2)), i, F(i-1), F(i)
.a._.c.t.v.m.vXX.z
# to 0, abs(F(i)-F(i-1)-F(i-2)), i, F(i-1), F(i)
# if (pop!=pop); then
.a.-\001.r.xXX.z
# print pop; exit; fi
.a.n.d.aXX.z
# to F(i), F(i-1), (i+1)
.a\001.+.vXX.z
# done
.aX.a


Try it online!

# Husk, 5 bytes

δV≠İf


Try it online!

You know it's a good day when you get to use decorV in an answer.