Secuencia similar a la de Fibonacci

Question

Hoy tengo que lidiar con algo que recuerda la secuencia de Fibonacci. Digamos que tengo un cierto número k, que es el número n-ésimo de cierta secuencia. Esta secuencia, sin embargo, es creada por una fórmula recursiva que conocemos de Fibonacci $a(n) = a(n-1) + a(n-2)$ donde $n \ge 2$ y $a(0) \le a(1) \le \dots \le a(n)$ . Así que digamos $a(n) = k$ . Ahora tengo que encontrar $a(0)$ , $a(1)$ que son el número inicial de esta secuencia, sin embargo la secuencia debe ser lo más larga posible y en caso de que haya muchas de ellas que sean de la misma longitud $a(0)$ debería ser lo más pequeño posible. Algún ejemplo:

$k = 10$

Puedo decir simplemente $a(0) = 0$ , $a(1) = 10$ así que $a(n) = k$ es parte de esta secuencia, ya que $a(0) + a(1) = a(2) = 10$ . Pero no es el más largo posible. Por ejemplo, elegir $a(0) = 0$ , $a(1) = 2$ Ahora $a(2) = 2$ , $a(3) = 4$ , $a(4) = 6$ , $a(5) = 10$ también es válida la secuencia y la longitud es $6$ y por lo que sé, no puede ser más largo.

¿Alguna idea de cómo hacerlo para cualquier $k$ ? Podría ser una fórmula matemática o algún algoritmo.

Answer 1

Mi opinión es elegir $a(n-1)$ para que $a(n)/a(n-1)$ se acerca a la relación de Fibonacci.

Answer 2

Como dice Michael, mira la secuencia de otra manera: el reverso de una secuencia de Fibonacci satisface la relación de recurrencia $a(n) = a(n+1) + a(n+2)$ o $a(n+2) = a(n)-a(n+1)$ .

Escoge $a(0) = k$ . Quiere elegir un valor para $a(1)$ de tal manera que cuando se define $a(n+2) = a(n) - a(n+1)$ se obtiene la racha más larga posible de enteros positivos.

Definir $b(n) = a(n+1)/a(n)$ . Entonces $b(n+1) = 1/b(n)-1$ . $a(n)$ se vuelve negativo cuando $b(n-1)$ se vuelve negativo, por lo que quieres elegir $a(1)$ (y así $b(0)$ ) tal que la secuencia $b(n)$ es positivo en la medida de lo posible.

Esta secuencia se obtiene eligiendo $b(0)$ tan cerca de $1/\phi = \frac {\sqrt 5-1} 2$ como sea posible: deje $f(x) = 1/x-1$ . Entonces $f \circ f(x) = (2x-1)/(1-x)$ que aumenta de $(0;1)$ a $(-1;\infty)$ y quieres que la secuencia permanezca dentro $(0;1)$ durante el mayor tiempo posible. $f$ tiene su único punto fijo en $1/\phi$ así que aquí es donde quieres empezar.

Por lo tanto, debe elegir $a(1) = \lfloor a(0)/\phi \rfloor$ o $a(1) = \lceil a(0)/\phi \rceil$ . Elige la que te dé la secuencia positiva más larga.

Answer 3

Asumiré que $a(0), a(1)$ deben ser enteros no negativos; en caso contrario, no hay longitud máxima.

Estos son conocido para tener la formulario $$a(n)=\alpha \phi^n + \beta \psi^n$$ donde $\alpha,\beta$ son números reales que dependen de las condiciones iniciales, $\phi=\frac{1+\sqrt{5}}{2}$ y $\psi=\frac{1-\sqrt{5}}{2}$ . Porque $|\psi|<1$ El $\beta \psi^n$ tiene un valor absoluto muy pequeño, por lo que $a(n)\approx[\alpha \phi^n]$ , donde $[\cdot]$ denota el redondeo al entero más cercano, y la aproximación es exacta para todos los casos, excepto para un número finito de $n$ .

Por lo tanto, una buena aproximación para el $n$ para lo cual $a(n)=k$ es $$\frac{\ln k}{\ln \phi}\approx 2.078 \ln k$$

Un procedimiento, también sugerido por Michael, para producir esos valores de partida (no tengo una forma cerrada) es hacer ingeniería inversa de este proceso. Supongamos que tenemos $k=100$ . Entonces $\frac{k}{\phi}\approx 61.8$ . De ahí que recomiende que la secuencia, en sentido inverso, comience por $100, 62$ . Teniendo dos términos podemos continuar como $100,62,38,24,14,10,4$ . Esto tiene una longitud $7$ , mientras que mi estimación es $9.57$ .

Answer 4

Por fuerza bruta, para $0 \leq k < 10^5$ la distancia entre la elección óptima de $a(n-1)$ y $k/\phi$ está siempre en el rango $\pm 0.72$ y está dentro de 0,5 alrededor del 90% de las veces. Por lo tanto, si necesita respuestas precisas, podría valer la pena obtener un límite teórico de este error, que le permitiría comprobar simplemente tres valores posibles de $a(n-1)$ como máximo. Me imagino que conseguir una expresión exacta será bastante difícil.