How can i find if a given number occurs in a custom Fibonacci sequence?

Question

Its a recent interview question from Amazon. For e.g. let starting numbers be $a$ and $b$, then third number will be $a+b$ and so on: forming recursion like:

$F(n)=F(n-1)+F(n-2) , n\ge 2$

$F(1)=a$

$F(2)=b$

I know its a Fibonacci relation but in this case initial two numbers are arbitrarily chosen. Also there exists golden ratio relation for standard Fibonacci sequence for finding if a number occurs in sequence. How can i find a given number appears in such sequence (of course efficiently). Thanks in advance.

EDIT:

For original sequence i used following relation where isPerfectSquare returns true if given number is perfect square:

bool isFibonacci(int n)
{
   // n is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both
   // is a perferct square
   return isPerfectSquare(5*n*n + 4) || isPerfectSquare(5*n*n - 4);
}

Answer 1

I was a little surprised how this worked out. If you have a "custom" Fibonacci sequence, it would appear that you really do a target $T$ such that $5 f^2 \pm T$ is a square. I made one up $$ 6,17,23,40,63,103,166,... $$ Now, for a custom sequence, call it $J_n,$ there is automatically an equation $$ J_n = a F_n + b L_n, $$ where $F_n$ are the Fibonacci sequence and the $L_n$ are the Lucas sequence. The one I made up is $$ J_n = 14 F_n + 3 L_n, $$ and the relation turns out to be
$$ 5 J_n^2 \pm 604 $$ is a square. Indeed, the thing to be squared is $$ W_n = 15 F_n + 14 L_n. $$ You can show easily that $$ 5 J_n^2 - W_n^2 = 141 (5 F_n^2 - L_n^2) = -604 (-1)^n. $$

Now, the problem in using $ 5 J_n^2 \pm 604 $ as a test is that some numbers appear with negative index. As you can see from the table below, using negative index in the Fibonacci or Lucas numbers does nothing worse than introducing some $\pm$ signs on the same numbers, but this need not hold for a "custom" sequence:

$$\begin{array}{rrrrrrrrrrrrrrrr} n & -7 & -6 & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \\ F_n & 13 & -8 & 5 & -3 & 2 & -1 & 1 & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 \\ L_n & -29 & 18 & -11 & 7 & -4 & 3 & -1 & 2 & 1 & 3 & 4 & 7 & 11 & 18 & 29\\ \\ J_n & 95 & -58 & 37 & -21 & 16 & -5 & 11 & 6 & 17 & 23 & 40 & 63 & 103 & 166 & 269 \\ W_n & -211 & 132 & -79 & 53 & -26 & 27 & 1 & 28 & 29 & 57 & 86 & 143 & 229 & 372 & 601 \end{array}$$

As long as $a,b $ are integers, all you need for $$ J_n = a F_n + b L_n $$ is $$ W_n = 5 b F_n + a L_n, $$ after which $$ 5 J_n^2 - W_n^2 = -4 (a^2 - 5 b^2) (-1)^n. $$

NOTE: I was temporarily worried about $a,b$ rational, but it is alright. With the indexing i use, we have $$F_n \equiv L_n \pmod 2.$$ Next, we are demanding $$ a+b, a+3b $$ to be integers, from which we get $2b$ integral. At worst, we have $b = (2k+1)/2,$ in which case $a = (2j+1)/2.$ Put everything together, once we demand $ J_n = a F_n + b L_n $ integral, we automatically get $ W_n = 5 b F_n + a L_n $ as well.

NOTE TOOOO, Saturday. I finally figured out where the trouble with composite targets appears. The first one I put has $604 = 4 \cdot 151,$ and $151$ is prime. This time, I am going to get $836 = 4 \cdot 209 = 4 \cdot 11 \cdot 19,$ with the result that two different custom sequences will have the same test value. One of the sequences will be $6F + 7 L,$ with squares of $35F + 6 L,$ the other sequence will be $17F + 4 L,$ with squares of $20F + 17 L.$ Both succeed with $5 J^2 \pm 836.$ The test can still be used as a very fast preliminary screen, but then extra work will be required to see which sequence owns the number of interest.

$$\begin{array}{rrrrrrrrrrrrrrrr} n & -7 & -6 & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \\ F_n & 13 & -8 & 5 & -3 & 2 & -1 & 1 & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 \\ L_n & -29 & 18 & -11 & 7 & -4 & 3 & -1 & 2 & 1 & 3 & 4 & 7 & 11 & 18 & 29\\ \\ J_n & -125 & 78 & -47 & 31 & -16 & 15 & -1 & 14 & 13 & 27 & 40 & 67 & 107 & 174 & 281 \\ W_n & 281 & -172 & 109 & -63 & 46 & -17 & 29 & 12 & 41 & 53 & 94 & 147 & 241 & 388 & 629 \\ \\ J_n & 105 & -64 & 41 & -23 & 18 & -5 & 13 & 8 & 21 & 29 & 50 & 79 & 129 & 208 & 337 \\ W_n & -233 & 146 & -87 & 59 & -28 & 31 & 3 & 34 & 37 & 71 & 108 & 179 & 287 & 466 & 753 \end{array}$$

Answer 2

You have a recurrence relation $$a_n - a_{n-1} - a_{n-2} = 0\ \ \ \ \ \ (1)$$ with initial conditions $a_1 = a$, $a_2 = b$.

The initial relation is the same as for the normal fibonacci sequence, and has (positive) solution (which you can check) $$a_n = \lambda\phi^n + \mu\phi^{-n}$$ $\lambda$ and $\mu$ can then be calculated using the initial conditions, as in the standard case (where you get $\lambda = \mu = \sqrt5$.

---

More detail:

We look for a solution of $(1)$ of the form $a_n = \alpha t^n$. Then $$\alpha t^n - \alpha t^{n-1} - \alpha t^{n-2}=0$$so $$t^2 - t - 1 = 0$$and $t = \phi, \phi^{-1}$. So a general solution takes the form $a_n = \lambda\phi^n + \mu\phi^{-n}$. $$a_1 = a =\lambda\phi^1+\mu\phi^{-1} \\a_2 = b =\lambda\phi^2 +\mu\phi^{-2} $$These equations can be solved simultaniously for $\lambda$ and $\mu$.