26
$\begingroup$

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:

Fibonacci parabola artifact

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

Extracted fibonacci parabola artifact

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

Variant of extracted fibonacci parabola artifact Variant of extracted fibonacci parabola artifact Variant of extracted fibonacci parabola artifact

$\endgroup$

migrated from cs.stackexchange.com Sep 1 '15 at 9:53

This question came from our site for students, researchers and practitioners of computer science.

  • 4
    $\begingroup$ This is an interesting question but I don't see any connection with computer science. The question is, essentially, about why the sequence given by the number of digits of successive Fibonacci numbers has a certain property. $\endgroup$ – David Richerby Sep 1 '15 at 9:39
  • 1
    $\begingroup$ I am sorry, I was not sure where to post it. I was thinking about mathematics, too, but I thought that people who would like to answer this should be able to use the Haskell code I provided (so it is easy for them to reproduce my results). Since I don't have enough reputation, feel free to request a move of the question to another, appropriate site. $\endgroup$ – CharlyDelta Sep 1 '15 at 9:45
23
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is, of course, easy to give a closed form formula for the sum of those approximations to $k_n$. The main point here is that the slowish linear growth of the decimal expansions automatically leads to the observed phenomenon. $\endgroup$ – Jyrki Lahtonen Sep 1 '15 at 10:30
  • 2
    $\begingroup$ Observe that the same phenomenon occurs when similarly printing any geometric sequence such that the ratio of consecutive entries $q$ is slightly larger than $1$. If $q$ is very large, then the parabola will be quite sharp, and less visible. Looks like the Golden ratio is in a good range for a pleasing visual effect :-) $\endgroup$ – Jyrki Lahtonen Sep 1 '15 at 10:42
  • $\begingroup$ Continuing the same line of thought: We get two parabolas in the region where $d_n$ is close to $M/2$ (approximately two separators per line), and a sparse parabola, when $d_n$ is close to $2M$ (separators on every other line). $\endgroup$ – Jyrki Lahtonen Sep 1 '15 at 10:44
  • 1
    $\begingroup$ +1: You would probably get similar results (with slightly sharper parabolas) looking at powers of $2$. $\endgroup$ – Henry Sep 1 '15 at 12:50
  • 1
    $\begingroup$ No problem, @Christian. I think myself that the presentation could be improved quite a bit. It just evolved to this with me reorganizing paragraphs, copy/pasting and such. I don't want to "bump" this too often with minor edits. OTOH, if you have specific questions or points I could improve, please let me know. My time zone and schedule tomorrow do make it difficult for me to come back to this soon. Thus it is best to leave the door open for a better (more compact, yet clearer) explanation. I'm particularly unhappy with using the derivative. Working with just differences might be better. $\endgroup$ – Jyrki Lahtonen Sep 1 '15 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.