Parábolas en secuencias de dígitos de la secuencia de Fibonacci

Question

En la preparación de un examen, estaba estudiando a Haskell. Por lo tanto, estaba resolviendo una vieja tarea en la que había que definir la serie de fibonacci. Después de resolver la tarea (ver 1] para el código fuente) y revisando el resultado, encontré un artefacto bastante interesante. Corriendo

$ ghci Fibonacci.hs
...
*Fibonacci> fibonacci

produjo esto:

Los separadores de la lista infinita de números de fibonacci formaban una parábola. Para hacer esto más visible, cambié un poco el código para que los números no se superpongan al artefacto (ver 2] para el código fuente). Aquí está la parábola extraída de la primera imagen: (Para más imágenes, ver 3] )

$ ghci Fibonacci.hs
...
*Fibonacci> highlightArtifact fibonacci

Observación

Es interesante que todas las zarandas de la lista forman una parábola de alguna manera (aunque el vértice no siempre es visible). No podía dejar de pensar en esto y me pregunté por qué sucede esto. Se puede descartar una coincidencia, porque los artefactos son visibles en todas partes cuando se desplaza a través de la salida (al menos al principio, después de un tiempo los números se hacen demasiado grandes) y al redimensionar la ventana terminal los hace crecer. Algunos superan la ventana terminal, pero se formarán nuevas parábolas.

Explicación (Un intento)

Dado que la ecuación para (al menos una parte de) una parábola como esa es $f(x) = \sqrt {x}$ (coeficientes y partes constantes excluidas, por lo tanto, asintóticamente), asumí, que este crecimiento debe ser encontrado en algún lugar de la serie de fibonacci, también. La velocidad en la que los números crecen en longitud debe ser descriptible con una función de la forma $ \sqrt {x}$ . Pero esto sólo explicaría la parte superior de la parábola, y no la parte inferior (debajo del vértice, es decir $f(x) = - \sqrt {x}$ ).

Preguntas

Asumiendo que voy en la dirección correcta: ¿Cómo se puede describir esto completamente?

Si no: ¿Cómo sería una explicación adecuada? ¿Cuál es su enfoque?

En cualquier caso: ¿Cómo se puede probar la explicación?

Apéndice

1] El código original donde descubrí el artefacto

-- Fibonacci.hs
module Fibonacci where

fibonacci :: [Integer]
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

2] El código modificado para extraer el artefacto

-- Fibonacci.hs
module Fibonacci where

fibonacci :: [Integer]
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

highlightArtifact :: [Integer] -> String
highlightArtifact (l : list) = (hideString (show l)) ++ "*" ++ (highlightArtifact list)

hideString :: String -> String
hideString "" = ""
hideString (c : string) = " " ++ hideString string

3] Más fotos

Answer 1

Si lo he entendido bien, la pregunta es sobre la colocación de los separadores, cuando las expansiones decimales de los elementos de la secuencia de Fibonacci se imprimen en una terminal siguiendo la regla de que una coma es el único separador.

---

Las parábolas observadas aparecerán siempre que la terminal tenga un ancho de línea fijo $M$ . Una breve explicación es que la longitud de la expansión decimal $d_n$ de $F_n$ crece linealmente en función de $n$ . Conseguimos algo así como una parábola cerca de la región, donde $d_n \approx M$ . Poco antes de ese punto, los números de Fibonacci tardan un poco menos de una fila en imprimirse, y las comas se desplazan rápidamente hacia la derecha a medida que nos desplazamos hacia arriba. Poco después de ese punto los números de Fibonacci tardan un poco más de una fila en imprimirse, y los separadores empiezan a desplazarse aceleradamente hacia la derecha a medida que nos desplazamos hacia abajo.

---

Luego la versión TL;DR;:

Esto se desprende de la fórmula de Binet que nos dice que $$ F_n \approx\frac1 { \sqrt5 } \left ( \frac {1+ \sqrt5 }2 \right )^n. $$ La aproximación es muy buena en el sentido de que $F_n$ es el entero más cercano al R.H.S., y la diferencia tiende a cero bastante rápidamente.

Por consiguiente, $d_n$ está bien aproximado por $$ d_n=1+ \lfloor\log_ {10}F_n \rfloor\approx 1+n \log_ {10} \left ( \frac {1+ \sqrt5 }2 \right )- \log_ {10} \sqrt5\approx 0.209 n+0.651. $$

La coma que sigue a $F_n$ aparece en la columna $k_n, 0 \le k_n<M$ donde $k_n$ está determinado por la congruencia $$ k_n \equiv\sum_ {i=1}^n (d_i+1) \pmod M. $$ Vemos que $$ k_{n+1}-k_n \equiv d_{n+1} \pmod M. $$ Así que cuando estamos en un rango, donde $d_n$ está cerca de $M$ (el significado exacto de "cerca" depende de $M$ ), entonces la suma $d_n+k_n$ desbordamientos (= excede $M$ ), y tenemos como la diferencia $$ k_{n+1}-k_n=0.209(n-N), $$ donde $N$ es una constante. En las imágenes $N$ nos dice la fila donde se encuentra el pico de la parábola. Es poco probable que sea exactamente un número entero, pero la pequeña diferencia no afectará a la conclusión que sigue.

A saber, aquí el r.h.s. es el derivado de un polinomio cuadrático de la forma $$p(x)=0.1045 x^2+ax+b.$$ Esto explica el surgimiento de las parábolas. En el caso de una cuadrática la diferencia, $p(n+1)-p(n)$ difiere del derivado, $p'(n)$ en una cantidad constante, por lo que el uso de una en lugar de la otra no cambia la conclusión general.

---

Como una prueba (ligeramente inexacta) para los cálculos anteriores afirmo que el pico de la parábola aparecerá aproximadamente en la coma siguiente $F_n$ donde $$ n \approx\frac {M}{0.208988}. $$ Así que si $M=80$ entendemos que el pico se produce después de $F_{383 \pm\epsilon }$ .

---

La constante $0.208988$ es aproximadamente $1/5$ . Esto se muestra en las figuras como sigue. Ves que los separadores permanecen en la misma columna durante aproximadamente cinco filas, debajo de eso se desplazan una posición a la derecha para las siguientes cinco filas aproximadamente. Se desplazan dos posiciones a la vez para las siguientes cinco, etc. Desplazándose hacia arriba, sucede lo contrario.