15 votos

Los números que hay en la secuencia de Fibonacci

Suponiendo que me piden para generar los números de Fibonacci hasta N, ¿cuántos números puedo generar? Estoy buscando el recuento de los números de Fibonacci hasta N, no el Enésimo número.

Así, como ejemplo, si puedo generar números de Fibonacci hasta el 25, me va a generar:

  • 1, 1, 2, 3, 5, 8, 13, 21
  • que de 8 números

¿Cómo puedo calcular este matemáticamente por una arbitraria "n"?

16voto

Andrew Puntos 140

Como se ha mencionado en los comentarios, la fórmula de Binet,

$$F_n=\frac1{\sqrt{5}}(\phi^n-(-\phi)^{-n})$$

donde $\phi=\frac12(1+\sqrt 5)$ es la proporción áurea, es una forma cerrada de la expresión de los números de Fibonacci. Ver esta cuestión de un par de pruebas.

Como para contar cuántos números de Fibonacci están ahí que son igual o inferior a un determinado número de $n$, se puede derivar una estimación a partir de la fórmula de Binet. El segundo término de la fórmula puede ser ignorada por gran suficientemente $n$, por lo que

$$F_n\approx\frac{\phi^n}{\sqrt{5}}$$

La solución para $n$ aquí da

$$n=\frac{\log\,F_n+\frac12\log\,5}{\log\,\phi}$$

Tomar la palabra, de la que da una estimación razonable; es decir, la expresión

$$\left\lfloor\frac{\log\,n+\frac12\log\,5}{\log\,\phi}\right\rfloor$$

puede ser utilizado para estimar el número de números de Fibonacci $\le n$. Esto es impreciso para las pequeñas $n$, pero qué mejor que un gran $n$.


Resulta que mediante la adición de un fudge plazo de $\frac12$$n$, los falsos positivos de la fórmula anterior desaparecen. (Bueno, al menos en la gama que he probado.) Por lo tanto,

$$\left\lfloor\frac{\log\left(n+\frac12\right)+\frac12\log\,5}{\log\,\phi}\right\rfloor$$

da mejores resultados.

3voto

HappyEngineer Puntos 111

Suponiendo que tomamos $F_0=0$$F_1=1$, para todos los $n\geq 0$, el valor de la $F_n$ es el entero más cercano a $\frac{\phi^n}{\sqrt{5}}$ donde $\phi = \frac{1+\sqrt{5}}{2}$.

Así, el número de Fibonnaci números de menos de $N$ es el número de $n\geq 0$ tal forma que:

$$ \frac{\phi^n}{\sqrt{5}} \leq N+\frac{1}{2}$$

La solución de esto, vemos que la $n \leq \log_\phi(\sqrt{5}(N+\frac{1}{2}))$. Eso significa que el número de $n$ es:

$$1+\lfloor{\log_\phi(\sqrt{5}(N+\frac{1}{2}))}\rfloor$$

-1voto

Mr Ayodele Puntos 16

No creo que usted será capaz de encontrar una forma cerrada fórmula para el número de números de Fibonacci menos de $N$ - si hubiera escogido $N = 26$ en lugar de $N = 25$, que habría llegado a la misma respuesta, pero si ha configurado $N = 34$, la respuesta habría de repente saltó a $9$. Como se ha sugerido antes, usted puede utilizar la fórmula de Binet:

enésimo número de Fibonacci $F_n= (\phi^n - (-\phi)^{-n})/(\sqrt 5)$ donde $\phi = (1 + (\sqrt 5))/2$

Simplemente enchufe en los valores de $n$ hasta $F_n > N$; a continuación, el número que se busca es $n-1$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X