Algebra Challenge
Commie Catholics
31-01-2006, 09:40
The Nth Fibonacci number is found using the following formula:
Fn = (1/√5) * [((1 + √5)/2)^n - ((1 - √5)/2)^n]
Where (1 + √5)/2 = φ and (1 - √5)/2 = φ'
If I am given a Fibonacci number Fn, what formula can I use to determine n?
(hidden) ::log(sqrt(5)*Fn)/log(phi) rounded to the nearest int if Fn > 1, if Fn=0 then n=0, if Fn=1 it's 1 or 2::
Commie Catholics
31-01-2006, 10:08
log(Fn)/log(phi) rounded to the nearest int
Wrong. An attempted proof would be nice though.
Wrong. An attempted proof would be nice though.It's not wrong, I just forget something. Give me a minute to work it out will ya.. :rolleyes:
or 4 minutes as the case may be.
Commie Catholics
31-01-2006, 10:12
It's not wrong, I just forget something. Give me a minute to work it out will ya.. :rolleyes:
ln (13) / ln (phi) ≈ 5.33; therefore the 5th Fib number. It's actually the 7th. It seems wrong.
sigh.. I had already edited my post before you posted.
I had inadvertably forgotten the sqrt(5), that's all.
Commie Catholics
31-01-2006, 10:13
It's not wrong, I just forget something. Give me a minute to work it out will ya.. :rolleyes:
or 4 minutes as the case may be.
How are you approaching it? Are you finding the inverse of the function?
Commie Catholics
31-01-2006, 10:14
sigh.. I had already edited my post before you posted.
I had inadvertably forgotten the sqrt(5), that's all.
Ah. I see.
How are you approaching it? Are you finding the inverse of the function?You just have to notice that |1-phi| < 1 So any power of it goes to zero quickly, i.e. you can ignore it.
Fn is phi^n/sqrt(5) rounded to the nearest integer (except for the first few)
Commie Catholics
31-01-2006, 10:25
You just have to notice that |1-phi| < 1 So any power of it goes to zero quickly, i.e. you can ignore it.
Fn is phi^n/sqrt(5) rounded to the nearest integer (except for the first few)
Which makes a good approximation for large values of n. But I'm looking for a function to give an exact integer solution for any Fib number.
Fn = * [((1 + √5)/2)^n - ((1 - √5)/2)^n/√5)]
=((1 + √5)/2)^n/√5 + ((1 - √5)/2)^n/√5
| ((1 - √5)/2)^n/√5 | goes to 0 (monotonically) for increasing n; in fact it's already less than a half to start with. Which means
Fn = ((1 + √5)/2)^n/√5 rounded to the nearest integer
But for this you can simply take the inverse
log(√5 Fn) = n * log((1 + √5)/2) Bearing in mind you're slightly imprecise. So you need to round.
Which makes a good approximation for large values of n. But I'm looking for a function to give an exact integer solution for any Fib number.It does give the exact integer solution, where it is possible (it is impossible to distinguish F1 and F2, as they're both 1)
If you want something without rounding (even though one can show that it does not lead to imprecision), I'm not sure that's possible.
Commie Catholics
31-01-2006, 10:41
It does give the exact integer solution, where it is possible (it is impossible to distinguish F1 and F2, as they're both 1)
If you want something without rounding (even though one can show that it does not lead to imprecision), I'm not sure that's possible.
Ok. Well done. :fluffle: :fluffle: :fluffle:
I'll make the challenge more clear. The function is to be rearanged so that n becomes the subject of the formula. It is possible, since I've done it before.