1
$\begingroup$

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);
}
$\endgroup$
2
  • 3
    $\begingroup$ The question in the title is different than the question in the body. $\endgroup$ Jul 31, 2014 at 18:54
  • 1
    $\begingroup$ You should probably display your idea for efficiently finding whether a number occurs in the original Fibonacci sequence, and give some examples. The verbal description is not precise enough, I am unable to estimate how much you know. $\endgroup$
    – Will Jagy
    Jul 31, 2014 at 18:59

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Can you pls elaborate the second eqn: lambda and phi one. I'm unable to understand it. :) thanks in advance. $\endgroup$ Jul 31, 2014 at 19:36
  • 1
    $\begingroup$ @HarshalGajjar is that clearer? $\endgroup$
    – Mathmo123
    Jul 31, 2014 at 19:42
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ superb explanation!!..thanks :) $\endgroup$
    – kalimba
    Aug 2, 2014 at 8:12
  • $\begingroup$ @kalimba, added cautionary paragraph about the possibility of more than one custom sequence using the same value in your test, here $5J^2 \pm 836.$ Still a good start. $\endgroup$
    – Will Jagy
    Aug 3, 2014 at 0:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .