| The fibonacci sequence is a sequence of integers in which each number is equal to the sum of the two preceding numbers. The first two integers in the sequence are both 1. Formally:
- F
_{1} = 1
- F
_{2} = 1
- F
_{i} = F_{i-1} + F_{i-2} for each i > 2
The beginning of this sequence is 1,1,2,3,5,8,13,21.
We'll define the fibonacci position of an integer greater than or equal to 1 as follows:
- The fibonacci position of 1 is 2 (since F
_{2} = 1)
- The fibonacci position of any integer n > 1 such that F
_{i} = n is i
- The fibonacci position of any integer n > 1 such that it is strictly between F
_{i} and F_{i+1} is i+(n-F_{i})/(F_{i+1}-F_{i}) (informally, this means it is linearly distributed between F_{i} and F_{i+1})
As examples, if FP(n) is the fibonacci position of n,
FP(1)=2 (first rule)
FP(5)=5 (second rule F_{5} = 5)
FP(4)=4.5 (third rule, is right in the middle of F_{4} = 3 and F_{5} = 5)
Given an integer **n**, return its fibonacci position as a double. |