Parabolas in sequences of digits from the Fibonacci sequence

In preperation for an exam, I was studying Haskell. Therefore I was solving an old assignment where you had to define the fibonacci series. After solving the task (see 1] for source code) and reviewing the result, I found a rather interesting artifact. Running

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

produced this:

The list separators of the infinite list of fibonacci numbers formed a parabola. To make this better visible, I changed the code a little bit so that the numbers don't overlay the artifact (see 2] for source code). Here is the extracted parabola of the first picture: (For more pictures, see 3])

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

Observation

Interestingly all list saparators form a parabola somehow (the vertex is not always visible though). I couldn't stop thinking about this and asked myself why this happens. A coincidence can be ruled out, because the artifacts are visible everywhere when you scroll through the output (at least in the beginning, after a while the numbers become to big) and resizing the terminal window makes them grow. Some outgrow the terminal window, but new parabolas will form.

Explanation (An attempt)

Since the equation for (at least a part of) a parabola like that is $f(x) = \sqrt{x}$ (coefficients and constant parts excluded, so, asymptotically), I assumed, that this growth must be found somewhere in the fibonacci series, too. The speed in which the numbers grow in length must be describable with a function of the form $\sqrt{x}$. But this would only explain the upper part of the parabola, and not the lower part (below the vertex, namely $f(x) = -\sqrt{x}$).

Questions

Assuming that I am heading in the right direction: How can this fully be described?

If not: What would a proper explanation look like? What is your approach?

In any case: How can the explanation be proven?

Appendix

1] Original code where I discovered the artifact

-- Fibonacci.hs
module Fibonacci where

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

2] Modified code to extract the artifact

-- 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] More pictures

Solution 1:

If I understood it correctly, the question is about the placements of separators, when the decimal expansions of elements of the Fibonacci sequence are printed on a terminal following the rule that a comma is the only separator.

The observed parabolas will appear whenever the terminal has a fixed line width $M$. A short explanation is that the length of the decimal expansion $d_n$ of $F_n$ grows linearly as a function of $n$. We get something like a parabola near the region, where $d_n\approx M$. Shortly before that point the Fibonacci numbers take slightly less than one row to print, and the commas acceleratingly drift to the right as we scroll up. Shortly after that point the Fibonacci numbers take a bit more than one row to print, and the separators begin an accelerating drift to the right as we scroll down.

Then the TL;DR; version:

This follows from Binet's formula telling us that $$ F_n\approx\frac1{\sqrt5}\left(\frac{1+\sqrt5}2\right)^n. $$ The approximation is very good in the sense that $F_n$ is the closest integer to the r.h.s., and the difference tends to zero quite rapidly.

Consequently $d_n$ is well approximated by $$ 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. $$

The comma following $F_n$ appears on the column $k_n, 0\le k_n<M$, where $k_n$ is determined by the congruence $$ k_n\equiv\sum_{i=1}^n (d_i+1)\pmod M. $$ We see that $$ k_{n+1}-k_n\equiv d_{n+1}\pmod M. $$ So when we are in a range, where $d_n$ is close to $M$ (the exact meaning of "close" depends on $M$), then the sum $d_n+k_n$ overflows (= exceeds $M$), and we get as the difference $$ k_{n+1}-k_n=0.209(n-N), $$ where $N$ is a constant. In the pictures $N$ tells us the row where the peak of the parabola lies. It is unlikely to be exactly an integer, but the small difference will not affect the conclusion below.

Namely, here the r.h.s. here is the derivative of a quadratic polynomial of the form $$p(x)=0.1045 x^2+ax+b.$$ This explains the emergence of the parabolas. In case of a quadratic the difference, $p(n+1)-p(n)$, differs from the derivative, $p'(n)$, by a constant amount, so using one instead of the other does not change the general conclusion.

As a (slightly inaccurate) test for the above calculations I claim that the peak of the parabola will appear approximately at the comma following $F_n$, where $$ n\approx\frac{M}{0.208988}. $$ So if $M=80$, we get that the peak occurs after $F_{383\pm\epsilon}$.

The constant $0.208988$ is approximately $1/5$. This shows in the figures as follows. You see that the separators stay on the same column for approximately five rows, below that they drift one position to the right for the next approximately five rows. Drift two positions at a time for the next five et cetera. Scrolling up, the reverse happens.