-1
$\begingroup$

Hi mathgeeks,

Given an extremely large fibonacci number X, and it's position in the fibonacci sequence N, is there any way to determine the N-1th fibo num, WITHOUT doing the bruteforce dance of counting from 1 upwards?

I've tried attacking the problem by dividing the number by two, and determining the difference between the N-1th, and N-2th, but that would require calculating Fib(n-3)/2, which makes the problem circular.

Also would be interested, if this can be proven not to be possible, thanks

$\endgroup$

closed as off topic by Todd Trimble, Mark Sapir, José Figueroa-O'Farrill, Andrés E. Caicedo, Qiaochu Yuan Dec 26 '10 at 16:49

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ Just divide by the golden mean and round to the nearest integer. This gives the correct (n-1)st Fibonacci provided that F_n is greater than 1. $\endgroup$ – Todd Trimble Dec 26 '10 at 15:34
  • $\begingroup$ @Todd, that's a very similar approach to the one suggested below by J.C. Ottem. $\endgroup$ – Mariano Suárez-Álvarez Dec 26 '10 at 15:41
  • $\begingroup$ Yes, I see that now. Anyway, I vote to close this question as being not anywhere near research level. $\endgroup$ – Todd Trimble Dec 26 '10 at 15:42
5
$\begingroup$

For large $n$, $\frac{f_{n+1}}{f_n} \approx \phi = 1.618..$. Hence you can get $f_n$ from $f_{n+1}$ by rounding $\frac{f_{n+1}}{\phi}$ to the nearest integer.

$\endgroup$
1
$\begingroup$

The n-th Fibonacci number can be calculated in log n steps, see, e.g., here

$\endgroup$
0
$\begingroup$

Yes, mathgeeks can compute a large fibonacci number without doing any kind of dance.

http://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio

$\endgroup$
  • 1
    $\begingroup$ But here the idea is that you know one of the numbers and want the previous one. Using Binet's formula in the obvious way forgets that piece of information. $\endgroup$ – Mariano Suárez-Álvarez Dec 26 '10 at 15:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.