enrevesados recurrencia: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$

Question

La relación de recurrencia:

$f(0)=1$

$f(1)=1$

$f(2)=2$

$f(2n)=f(n)+f(n+1)+n\ \ \ (\forall n>1)$

$f(2n+1)=f(n)+f(n-1)+1\ \ \ (\forall n\ge 1)$

(los primeros números de la secuencia son: 1, 1, 2, 3, 7, 4, 13, 6, 15, 11, 22, 12, 25, 18, 28)

Dado un número $S$, me gustaría encontrar $n$ tal que $f(n) = S$, utilizando un enfoque que se ejecuta en tiempo de $O(\log n)$. ¿Cualquier ideas o consejos de cómo solucionarlo? Trató de sustitución hasta el momento pero no ahora.

Answer 1

Su recurrencia es uno de los grandes de la clase de similares características llamado "2-regular". Estas recurrencias pueden ser expresadas en un número de maneras diferentes. Por ejemplo, se desprende de los documentos a continuación que existen matrices cuadradas $M_0, M_1$ y vectores $u, v$ de manera tal que si la base 2 de la expansión de $n$ está dado por $e_1 e_2 \cdots e_j$, $$f(n) = u M_{e_1} \cdots M_{e_j} v.$ $ El tamaño de las matrices que se llama el rango; su serie parece tener el rango 10 por lo que puedo ver.

A partir de esta expresión a menudo se pueden encontrar, por ejemplo, el comportamiento asintótico de la recurrencia. Pero, en general, incluso de las propiedades básicas de estas secuencias (tales como "¿ 0 nunca se producen?") es indecidible—aunque a menudo decidable para cualquier secuencia determinada.

En su caso particular, creo que se podría probar con un poco de trabajo que $\liminf f(n)/(n \log n)$ $\limsup f(n)/(n \log n)$ ambos existen y son acotados. Para $n$ suficientemente grande debe ser el caso de que $.39 n \log n ≤ f(n) ≤ .5 n \log n$. Esto significa que si usted está tratando de solucionar $f(n) = S$ a continuación, para cada una de las $S$, no es sólo una gama limitada (dependiendo $S$) que debe buscarse.

Esto le da un algoritmo (una vez que se prueban las desigualdades) para todos los $n$ suficientemente grandes, pequeñas $n$ puede ser buscado a través de la fuerza bruta. Este enfoque el uso de la expresión asintótica no va a permitir que usted para resolver por $n$ $O(\log n)$ tiempo, por lo que no satisface sus necesidades.

Sin embargo, usted puede aprovechar el hecho de que los dos subsecuencias $(f(2n))_{n≥0}$ $(f(2n+1))_{n≥0}$ son, individualmente, monótonamente creciente. Esto significa que usted puede solucionar $f(n) = S$ a través de la búsqueda binaria, uno para el incluso índices y otro para los impares.

Referencias:

Allouche y Shallit, El anillo de $k$-regular secuencias, Teori. Comput. Sci. 98 (1992), 163-197. Allouche y Shallit, El anillo de $k$-regular secuencias, II. Teori. Comput. Sci. 307 (2003), 3-29.