12
$\begingroup$

Recall that a normal decimal number is an irrational number $\alpha \in \mathbb{R}$ such that each digit 0-9 appears with average frequency tending toward $\frac{1}{10}$, each pair of digits 00-99 appears with average frequency tending toward $\frac{1}{100}$ in the decimal expansion of $\alpha$, etc.

Since the Champernowne constant $$0.12345678910111...$$ obtained by concatenating natural numbers is known to be normal, and since the Copeland-Erdős Constant $$0.23571113171923...$$ obtained by concatenating prime numbers is known to be normal, and since the Besicovitch constant $$0.14916253649648...$$ obtained by concatenating the squares of natural numbers is known to be normal, it is natural to consider whether or not the "Fibonacci constant" $$0.11235813213455...$$ obtained by concatenating consecutive entries in the Fibonacci sequence is normal in base $10$.

This problem has been considered previously in the linked arXiv article, although the "proof" given in this article is erroneous. So it is natural to ask:

(1) Is the Fibonacci constant $0.11235813213455...$ normal in base $10$?

(2) Is the Fibonacci constant $0.11235813213455...$ known to be normal in base $10$?

$\endgroup$
  • 1
    $\begingroup$ I thought the definition of a normal number was that any finite sequence appears in it. Are those definitions equivalent? $\endgroup$ – GFauxPas Jun 30 '16 at 19:25
  • 1
    $\begingroup$ @GFauxPas According to Wikipedia: "A disjunctive sequence is a sequence in which every finite string appears. A normal sequence is disjunctive, but a disjunctive sequence need not be normal." $\endgroup$ – John M. Campbell Jun 30 '16 at 19:32
  • 2
    $\begingroup$ Do we even know if it's disjunctive? $\endgroup$ – Ohad Jun 30 '16 at 21:42
  • $\begingroup$ I believe this property, like for many other constants, is rather hard to prove. You can easily come up with heuristic and numeric evidence that it is normal, but you will likely not find a rigorous proof. $\endgroup$ – user347499 Jul 8 '16 at 21:31
7
+50
$\begingroup$

On Edit: code completely revised (and now debugged!)

It is an interesting question. The answer is probably "yes", though I have no idea how to prove it.

It can't hurt to write a program to explore it. Here is a simple Python3 function to explore the digit-block distributions:

import statistics

def fibConst(n):
    #Generator for first n digits of the Fibonacci constant
    F1 = 0
    F2 = 1
    pool = list(str(F2))
    pool.reverse() #list of digits in reversed order
    for i in range(n):
        if len(pool) == 0:
            F1,F2 = F2, F1+F2
            pool = list(str(F2))
            pool.reverse()
        yield int(pool.pop())

def digitDist(n,k = 1, summary = True):
    #returns the distribution of the k-digit blocks
    #first n digits of the Fibonacci constant
    #.1123581321...
    #if summary = True (the default)
    #a statistical summary is returned:
    #(min, max, median, mean, standard deviation)
    #otherwise, the whole distribution is returned as a list

    counts = [0] * 10**k
    digits = fibConst(n)

    num = 0
    for i in range(k):
        num = 10*num + next(digits)
    counts[num] = 1 #record initial block of length k

    for i in range(k,n):
        num = (10 * num + next(digits)) % 10**k
        counts[num] += 1

    if not summary:
        return counts
    else:
        minCount = min(counts)
        maxCount = max(counts)
        med = statistics.median(counts)
        m = statistics.mean(counts)
        sd = statistics.pstdev(counts)
        return (minCount,maxCount,med,m,sd)

The first function is a generator (aka lazy list) which produces successive digits on demand. It doesn't attempt to keep the full n digits in memory.

Typical runs:

>>> for k in range(1,6): print(digitDist(10**6,k))

(99445, 100743, 100013.0, 100000.0, 351.6694470664178)
(9819, 10245, 10002.0, 9999.99, 91.5220732938235)
(894, 1096, 1000.0, 999.998, 31.575560105879358)
(61, 142, 100.0, 99.9997, 10.070278045317318)
(0, 28, 10.0, 9.99996, 3.1738399453028503)

>>> for k in range(1,7): print(digitDist(10**7,k))

(997286, 1003133, 999964.0, 1000000.0, 1490.5531188119396)
(99373, 100868, 100014.5, 99999.99, 322.87339608583426)
(9650, 10363, 10001.5, 9999.998, 98.10266049399476)
(890, 1140, 1000.0, 999.9997, 31.520718581751908)
(56, 143, 100.0, 99.99996, 9.967519249963855)
(0, 28, 10.0, 9.999995, 3.1578519597940304)

While this data seems to on the whole support the conjecture that the number is normal, the bottom lines of these runs are both surprising. When you look at the first million digits some 5-digit sequences appear not at all and some appear 28 times. A bit of sleuthing uncovered that the sequence 24242 appeared zero times and the sequence 48087 appeared 28 times. I don't now what to make of this, though it is enough to make me a little more hesitant in conjecturing normality.

Final remark: if you want a string representation of the initial part of the constant you can write a function like:

def strFib(n):
    return '0.' + ''.join(str(d) for d in fibConst(n))

For example,

>>> strFib(20)
'0.11235813213455891442'
>>> strFib(100)
'0.1123581321345589144233377610987159725844181676510946177112865746368750251213931964183178115142298320'
$\endgroup$
  • 2
    $\begingroup$ The fact that some numbers are avoided for a longer time than their mean time of appearance is not surprising. In the coupon collector's problem the mean time of appearance of each coupon is $n$ but the mean time to get every coupon at least one is of order $n\log n$, which is $\gg n$. $\endgroup$ – Did Jul 3 '16 at 16:45
  • 1
    $\begingroup$ @Did Maybe that is all there is to it, but I found the 28 to 0 discrepancy surprisingly large and wondered if there was something about the Fibonacci recurrence that on the one hand makes certain numbers difficult to create and on the other had other numbers to pop up many times. $\endgroup$ – John Coleman Jul 3 '16 at 17:17
  • 1
    $\begingroup$ Related. $\endgroup$ – Did Jul 3 '16 at 17:51
  • $\begingroup$ @Did You seem to be right that what I observed is what should be expected if thought of as a coupon's collector problem. I ran my code again with the Fibonacci constant generator replaced by something which spits out a pseudo-random stream of numbers and had almost identical results (some occurring 0 times and other occurring 25-30 times, with standard deviations of frequencies being intriguingly just above pi) $\endgroup$ – John Coleman Jul 3 '16 at 18:48
  • $\begingroup$ Simulations on the question asked in my recent post would be welcome... $\endgroup$ – Did Jul 3 '16 at 19:40

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.