# The Fibonacci Sequence is Normal Base 10

Brennan Benfield  Brennan Benfield: Department of Mathematics, University of
Hawaii, 2565 McCarthy Mall, Honolulu, HI 96822, USA<EMAIL_ADDRESS>and  Michelle Manes  Michelle Manes: Department of Mathematics, University of
Hawaii, 2565 McCarthy Mall, Honolulu, HI 96822, USA<EMAIL_ADDRESS>
###### Abstract.

In this paper, we show that the concatenation of the Fibonacci sequence is
normal in base $10$, meaning every string of a given length, $k$, occurs as
frequently as every other string of length $k$ (there are as many $1$’s as
$2$’s and as many $704$’s and $808$’s). Although we know that almost every
number is normal, we can name very few of them. It is still unclear if $e$,
$\pi$, or $\sqrt{2}$ are normal. We show that concatenating the Fibonacci
sequence behind a decimal creates a normal number in every base of the form
$5^{x}\times 2^{y}$. We then provide evidence that potentially extends our
result to all integer bases, and claim that the Fibonacci concatenation is
absolutely normal.

###### Key words and phrases:

Fibonacci numbers, normal numbers, uniform distribution, concatenation

###### 2020 Mathematics Subject Classification:

11B39, 11B50

Second author partially supported by Simons Foundation grant number 359721.

##  1\. Introduction

The sequence of Fibonacci numbers $\left(F_{n}\right)_{n\in\mathbb{N}}$ is
given by the recurrence equation:

$\displaystyle F_{0}$ $\displaystyle=0$ $\displaystyle F_{1}$
$\displaystyle=1$ $\displaystyle F_{n}$ $\displaystyle=F_{n-1}+F_{n-2}$
$\displaystyle\left(F_{n}\right)_{n\in\mathbb{N}}$
$\displaystyle=0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946\ldots$

In this paper, we investigate whether this famous sequence, when concatenated
behind a decimal, creates a normal number. A number in a base $\beta$ is
normal if every string of length $k$ occurs in the limit as often as every
other string of length $k$, namely with a frequency of $1/\beta^{k}$. To prove
that the Fibonacci concatenation is normal in a base $\beta$, we use a
technique that measures the frequency of each digit in every place value of
the Fibonacci numbers in base $\beta$. A major tool we use is the well-known
fact that the Fibonacci sequence is purely periodic modulo every integer base
$\beta$. The length of one period of the Fibonacci sequence modulo a base
$\beta$ is known as the Pisano period. The aim of this paper is to connect the
notion of normal numbers and Pisano periods, to prove that the Fibonacci
concatenation is normal in Base $10$, and to provide computations and
heuristic evidence that the Fibonacci concatenation absolutely normal.

######  Theorem 1.1 (Main Theorem).

The Fibonacci sequence, when concatenated behind a decimal, is normal in every
base of the form $5^{x}2^{y}$ for nonnegative integers $x$ and $y$.

For the convenience of the reader, we provide here an outline of the paper and
a summary of techniques used:

Section 2:

Background information on normal numbers and Pisano periods.

Section 3:

Connecting the relationship between periodicity of the Fibonacci sequence
modulo an integer $\beta$ with the sequences of digits in each place value of
the Fibonacci numbers in base $\beta$.

Section 4:

Proof that the Fibonacci concatenation is normal in every base of the form
$\beta=5^{x}$.

Section 5:

Proof that the Fibonacci concatenation is normal in every base of the form
$\beta=2^{y}$.

Section 6:

Combining the results from the previous two sections to show that the
Fibonacci concatenation is normal in every base of the form
$\beta=5^{x}2^{y}$.

Section 7:

Computational evidence that the Fibonacci concatenation is in fact normal in
every base, thus is absolutely normal.

##  2\. Preliminaries

There are many definitions of a normal number. The first was given by Borel in
1909 [2], but the definition has been refined during the last century. We use
the definition given by Davenport and Erdös [5].

######  Definition 2.1.

Let $x$ be a real number in a base $\beta$. Let $a_{1}a_{2}\cdots a_{k}$ be
any string of length $k$ written in base $\beta$. Let $N(t)$ denote the number
of times that this string occurs among the first $t$ digits of $x$. Then, $x$
is normal in $\beta$ if

$\lim_{t\to\infty}\frac{N(t)}{t}=\frac{1}{\beta^{k}}.$

In the case where $k=1$, we say $x$ is simply normal in base $\beta$ if

$\lim_{t\to\infty}\frac{N(t)}{t}=\frac{1}{\beta}.$

Finally, a number is absolutely normal if it is normal in every base.

More plainly, a number is normal in a base $\beta$ if every string of length
$k$ occurs with a limiting relative frequency of $1/\beta^{k}$ and is simply
normal if each digit occurs with a limiting relative frequency of $1/\beta$.
The equivalent definition of normal that was given by Borel [2] in 1909 was
further refined by Pillai [13] in 1940:

######  Lemma 2.2 (Pillai).

A number is normal in base $\beta$ if and only if it is simply normal in base
$\beta^{k}$ for all positive integers $k$.

Borel [2] showed that in every base, almost every number is normal, in the
sense that non-normal numbers have Lebesgue measure $0$. Despite their
overwhelming population on the real line, mathematicians have yet to prove
that any of the commonplace mathematical constants like $\pi$, $e$,
$\sqrt{2}$, $\phi$ etc. are normal. Because of this, the earliest examples of
normal numbers were concatenations of well known sequences. Champernowne [3]
showed the concatenation of the natural numbers is normal in base $10$. Other
early examples of normal numbers in base $10$ include the concatenation of the
square numbers (Besicovitch [1]) and the concatenation of the primes (Copeland
and Erdős [4]).

Champernowne $\displaystyle.123456789101112131415161718192021222324252\ldots$
Besicovitch $\displaystyle.149162536496481100121144169196225256289324\ldots$
Copeland & Erdős
$\displaystyle.235711131719232931374143475359616771737983\ldots$

We consider here the concatenation of the Fibonacci sequence behind a decimal.
Let $\left(F_{n,\beta}\right)$ denote the Fibonacci sequence in base $\beta$
and let $\left<\left(F_{n,\beta}\right)\right>$ denote its concatenation
behind a decimal.

######  Example.

In bases $2,\ldots,10$, the concatenation of the Fibonacci sequence is given
by the following:

$\displaystyle\left<\left(F_{n,2}\right)\right>=$
$\displaystyle.01110111011000110110101100010110111101100110010000111\ldots$
$\displaystyle\left<\left(F_{n,3}\right)\right>=$
$\displaystyle.01121012221112101021200110022121002212211122221112111\ldots$
$\displaystyle\left<\left(F_{n,4}\right)\right>=$
$\displaystyle.01123112031111202313112121003221113212120233123120331\ldots$
$\displaystyle\left<\left(F_{n,5}\right)\right>=$
$\displaystyle.01123101323411142103241034141330024420124222234240314\ldots$
$\displaystyle\left<\left(F_{n,6}\right)\right>=$
$\displaystyle.01123512213354131225400102514252454432311221155443120\ldots$
$\displaystyle\left<\left(F_{n,7}\right)\right>=$
$\displaystyle.01123511163046106155264452104615312610444110351151222\ldots$
$\displaystyle\left<\left(F_{n,8}\right)\right>=$
$\displaystyle.01123510152542671312203515711142173330755030101251515\ldots$
$\displaystyle\left<\left(F_{n,9}\right)\right>=$
$\displaystyle.01123581423376110817027845874713162164348156551024616\ldots$
$\displaystyle\left<\left(F_{n,10}\right)\right>=$
$\displaystyle.01123581321345589144233377610987159725844181676510946\ldots$

There are periodic patterns in the Fibonacci sequence for every integer
modulus. In 1877, Lagrange [11] noted that the Fibonacci sequence modulo $10$
repeats every $60$ terms. Several specific results for the periodicity of the
Fibonacci sequence modulo various integers followed, culminating in the
following theorem of Wall from 1960 [24].

######  Theorem 2.3 (Wall).

For every positive integer $m$, the Fibonacci sequence is periodic modulo $m$.

The length of this period is known as the Pisano period and is denoted
$\pi(m)$. Pisano periods have been generalized for Lucas numbers, Pell
numbers, $(a,b)$-Fibonacci numbers, and $n$-step Fibonacci numbers. For our
purpose, we are only concerned with the Fibonacci sequence, and so will use
the following definition.

######  Definition 2.4.

The Pisano period of a positive integer $m$, denoted $\pi(m)$, is the smallest
number $k>0$ such that $F_{k}\equiv 0\mod{m}$ and $F_{k+1}\equiv 1\mod{m}$.

-Equivalently-

The Pisano period $\pi(m)$ is the length of one (shortest) period of the
Fibonacci sequence modulo $m$.

######  Example.

The sequence of Pisano periods can be found at OEIS: A001175 [16]. Below are
the first few Pisano periods up to $20$.

$m$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\pi(m)$ | 3 | 8 | 6 | 20 | 24 | 16 | 12 | 24 | 60 | 10 | 24 | 28 | 48 | 40 | 24 | 36 | 24 | 18 | 60
Table 1. Pisano period of the first $20$ integers.

Notice that the only odd integer that is a Pisano period is $\pi(2)=3$.
Combining this with the results of Stanley [21] and Ehrlich [6], Renault [14]
showed the following:

######  Proposition 2.5 (Renault).

For every even integer $n>4$, there is an integer $m$ such that $\pi(m)=n$.

A property that we will use frequently is the nesting property of Pisano
periods. For every positive integer $n$, the Pisano period of $n$ divides the
Pisano period of every multiple of $n$.

######  Lemma 2.6 (Wall [24]).

For any two positive integers $m,n$, if $m\mid n$ then $\pi(m)\mid\pi(n)$.

For our purpose, we only need the nesting property for powers of the base we
are considering. Given an integer $m$, $\pi(\beta^{i})\mid\pi(\beta^{i+1})$.

######  Example 1.

Following the investigation of Legrange, Geller [7] observes the nesting of
powers of 10:

$\pi(10)=60,\qquad\pi(100)=300,\qquad\pi(1000)=1500,\qquad\pi(10000)=15000,\ldots$

This pattern was later generalized by Jarden [9] into the following
proposition:

######  Proposition 2.7 (Jarden).

The Fibonacci sequence is periodic modulo powers of ten with the following
periods:

$\pi(10^{k})=\begin{cases}60&k=1\\\ 300&k=2\\\ 15\cdot 10^{k-1}&k\geq
3\qquad.\end{cases}$

From the Lemma 2.6 it follows that for a positive prime $p$,
$\pi(p^{i})\leq\pi(p^{i+1})$. We can refine this expression to strict
inequality, provided the prime $p$ is not a Wall-Sun-Sun prime.

######  Definition 2.8 (Wall, Sun, Sun).

A Wall-Sun-Sun prime is a prime number $p$ such that $\pi(p)=\pi(p^{2})$.

Although there are conjectured to be infinitely many Wall-Sun-Sun primes [10],
none have been found. If it can be shown that Wall-Sun-Sun primes do not
exist, that would imply Fermat’s last theorem [22]. Wall [24] proposed the
following lemma that tests whether a candidate integer can be a Wall-Sun-Sun
prime.

######  Lemma 2.9 (Wall).

Given a prime $p$, let $t$ be the largest integer such that
$\pi(p^{t})=\pi(p)$. Then for all $e\geq t$, $\pi(p^{e})=p^{e-t}\pi(p)$.

The online research community PrimeGrid is currently leading a computer search
for Wall-Sun-Sun primes with its leading edge over $3\times 10^{17}$. Because
we have still not found a Wall-Sun-Sun prime, we can say that for every known
prime that has been tested, $t=1$ and $\pi(p^{e})=p^{e-1}\pi(p)$.

######  Corollary 2.10.

For every prime $p$ that is not a Wall-Sun-Sun prime,
$\pi(p^{i})<\pi(p^{i+1})$ for $i\in\mathbb{Z}^{+}$.

###### Proof.

Because we are supposing that $p$ is not a Wall-Sun-Sun prime, Wall’s lemma
2.9 tells us that for all $e\geq 1$, $\pi(p^{e})=p^{e-1}\pi(p)$. Then
$\pi(p^{i})=p^{i-1}\pi(p)<p^{(i+1)-1}\pi(p)=\pi(p^{i+1})$. ∎

Leveraging the following Lemma by Wall [24], we can extend Corollary 2.10 to
composite integers.

######  Lemma 2.11 (Wall).

If $m$ has the prime factorization $m=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots
p_{n}^{e_{n}}$, then

$\pi(m)=\text{LCM}\left(\pi(p_{1}^{e_{1}}),\pi(p_{2}^{e_{2}}),\cdots,\pi(p_{n}^{e_{n}})\right).$

Then we have the following result:

######  Proposition 2.12.

For every integer $m$ that has no Wall-Sun-Sun primes in its prime
factorization, $\pi(m^{i})<\pi(m^{i+1})$ for $i\in\mathbb{Z}^{+}$.

###### Proof.

Suppose $m$ has the prime factorization $m=p_{1}^{e_{1}}p_{2}^{e_{2}}\ldots
p_{n}^{e_{n}}$, where no $p$ is a Wall-Sun-Sun prime. Then we have the
following:

$\pi(m^{i})=\text{LCM}\left(\pi(p_{1}^{{ie_{1}}})\pi(p_{2}^{{ie_{2}}})\cdots\pi(p_{n}^{{ie_{n}}})\right).$

And by Theorem 2.10 we have that for all $j=1,2,\ldots,n$,
$\pi(p_{j}^{ie_{j}})<\pi(p_{j}^{(i+1)e_{j}})$. Then

$\displaystyle\pi(m^{i})$
$\displaystyle=\text{LCM}\left(\pi(p_{1}^{{ie_{1}}})\pi(p_{2}^{{ie_{2}}})\cdots\pi(p_{n}^{i(e_{n})})\right)$
$\displaystyle<\text{LCM}\left(\pi(p_{1}^{{(i+1)e_{1}}})\pi(p_{2}^{{(i+1)e_{2}}})\cdots\pi(p_{n}^{{(i+1)e_{n}}})\right)$
$\displaystyle=\pi(m^{i+1}).\qed$

##  3\. Bases and Moluli

We prove the Main Theorem by exploiting the connection between the digits in
the $\beta^{k}$’s place of the Fibonacci sequence in base $\beta$ and the
Fibonacci sequence modulo $\beta^{k+1}$. To extract the digits
$0,1,2,\ldots,\beta-1$ in the $\beta^{k}$’s place, we introduce the following
function:

######  Definition 3.1.

Denote by $\left(\Phi_{\beta^{k}}(n)\right)_{n\in\mathbb{N}}$ the sequence of
$\beta^{k}$’s place digits in the Fibonacci sequence in base $\beta$. To
obtain this sequence, we can use the following function:

$\displaystyle\Phi_{\beta^{k}}:\mathbb{N}$
$\displaystyle\rightarrow\mathbb{Z}/\beta\mathbb{Z}$ $\displaystyle n$
$\displaystyle\mapsto\left\lfloor\frac{F_{n}}{\beta^{k}}\right\rfloor\mod{\beta}.$

Let $\left(\Phi_{\beta^{k}}(n)\right)_{n=1}^{N_{k}}$ denote one (shortest)
period of the $\beta^{k}$’s place digits of the Fibonacci sequence in base
$\beta$ where $N_{k}$ is the length of a shortest period of the sequence
$\left(\Phi_{\beta^{k}}(n)\right)_{n\in\mathbb{N}}$. This notation is
justified in the following Lemma.

######  Lemma 3.2.

The sequence $\left(\Phi_{\beta^{k}}(n)\right)_{n\in\mathbb{N}}$ is periodic.
Furthermore, if the base $\beta$ is not divisible by any Wall-Sun-Sun primes,
the length $N_{k}$ of its period is equal to $\pi(\beta^{k+1})$.

###### Proof.

Periodicity of the sequence
$\left(\Phi_{\beta^{k}}(n)\right)_{n\in\mathbb{N}}$ follows immediately from
the periodicity of the Fibonacci sequence modulo $\beta^{k+1}$; all of the
digits must repeat after $\pi(\beta^{k+1})$ terms, so the $k^{\text{th}}$
digit (in base $\beta$) certainly repeats every $\pi(\beta^{k+1})$ terms. It
follows that $N_{k}\mid\pi(\beta^{k+1})$.

To show equality, we proceed by contradiction. Suppose that we do not have
equality, then $N_{k}<\pi(\beta^{k+1})$. That says that the $k^{\text{th}}$
digit (in base $\beta$) repeats on a shorter period than the Fibonacci number
modulo $\beta^{k+1}$. So the sequence modulo $\beta^{k+1}$, ignoring the
$k^{\text{th}}$ digit, would have the same period. In other words,
$\pi(\beta^{k})=\pi(\beta^{k+1})$. But this contradicts Proposition 2.12. ∎

######  Example.

Consider the Fibonacci sequence in ternary (base $3$). The $3^{0}$’s place
digits are given by the sequence:

$\displaystyle\left(\Phi_{3^{0}}(n)\right)_{n=1}^{8}=0,1,1,2,0,2,2,1\circlearrowleft.$

This sequence repeats every $8$ terms. The length exactly coincides with the
Pisano period $\pi(3)=\pi(\beta^{1})$ (this sequence is indeed the Fibonacci
sequence modulo $3$). Consider now the sequence of $3^{1}$’s place digits in
base $3$:

$\displaystyle\left(\Phi_{3^{1}}(n)\right)_{n=1}^{24}=0,0,0,0,1,1,2,1,1,2,0,2,0,2,2,2,2,1,0,1,2,0,2,0\circlearrowleft.$

This sequence repeats every $24$ terms. The length exactly coincides with the
Pisano period $\pi(9)=\pi(\beta^{2})$. Again, consider the sequence of
$3^{2}$’s place digits in base $3$:

$\displaystyle\left(\Phi_{3^{2}}(n)\right)_{n=1}^{72}=$ $\displaystyle
0,0,0,0,0,0,0,1,2,0,0,0,1,1,2,1,1,0,2,2,1,1,2,1,$ $\displaystyle
1,2,0,2,2,1,0,2,0,2,0,2,0,2,2,2,2,2,2,1,0,2,2,2,$ $\displaystyle
2,1,0,1,1,2,0,0,1,1,0,1,2,0,2,0,0,1,2,0,2,0,2,0\circlearrowleft.$

This sequence repeats every $72$ terms. The length exactly coincides with the
Pisano period of $\pi(27)=\pi(\beta^{3})$.

It is well known [15, 14] that the integer bases, with respect to the
Fibonacci sequence, can be evenly divided into three categories according to
the number of zeros in their Pisano period.

######  Definition 3.3.

For a base $\beta$, denote by $\omega(\beta)$ the number of zeros in one
Pisano period of $\beta$.

The sequence produced by $\omega(n)$ for $n=1,2,3,\ldots$ can be found at OEIS
A001176 [17].

$\beta$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\pi(\beta)$ | 3 | 8 | 6 | 20 | 24 | 16 | 12 | 24 | 60 | 10 | 24 | 28 | 48 | 40 | 24 | 36 | 24 | 18 | 60
$\omega(\beta)$ | 1 | 2 | 1 | 4 | 2 | 2 | 2 | 2 | 4 | 1 | 2 | 4 | 2 | 2 | 2 | 4 | 2 | 1 | 2
Table 2. Table of $\beta$, $\pi(\beta)$, and $\omega(\beta)$ for
$2\leq\beta\leq 20$.

It has been proven by Gupta et. al. [15] that the only possible values for
$\omega(n)$ are $1,2,$ and $4$. In the table below, we categorize the integer
bases according to the number of zeros in their Pisano period.

$\omega(\beta)=1$ | $\omega(\beta)=2$ | $\omega(\beta)=4$
---|---|---
1, 2, 4, 11, 19, 22, 29, 31, | 3, 6, 7, 8, 9, 12, 14, 15, | 5, 10, 13, 17, 25, 26, 34, 37,
38, 44, 58, 59, 62, 71, 76, 79, | 16, 18, 20, 21, 23, 24, 27, 28, | 50, 53, 61, 65, 73, 74, 85, 89,
101, 116, 118, 121, 124, 131, | 30, 32, 33, 35, 36, 39, 40, | 97, 106, 109, 113, 122, 125,
139,142, 151, 158, 179, 181,… | 41, 42, 43, 45, 46, 47, 48, 49,… | 130, 137, 146, 149, 157…
OEIS: A053031 [20] | OEIS: A053030 [19] | OEIS: A053029 [18]
Table 3. Splitting of bases $\beta$ according to the number of zeros in one
Pisano period

Although there are countably many integer bases in each category, the rate at
which each category grows is not balanced. Of the first ten thousand bases,
$1013$ bases have one zero in their Pisano period, $7917$ bases have two zeros
in their Pisano period, and $1070$ bases have four zeros in their Pisano
period. Evidence of this uneven distribution in found in a series of
conjectures on the OEIS: A053029, A053030, and A053031 [18, 19, 20] concerning
the number of zeros in an integer’s Pisano period. We have summarized the
three conjectures from the OEIS into the following:

######  Conjecture 3.4.

[OEIS: A053029, A053030, A053031]

i. An integer $m$ has four zeros in its Pisano period if and only if $m$ is an
odd number, all of whose factors have four zeros in their Pisano period, or if
$m$ is twice such a number.

ii. An integer $m$ has one zero in its Pisano period if and only if $m$ is an
odd number, all of whose factors have one zero in their Pisano period, or if
$m$ is twice or four times such a number.

iii. Every other integer has one zero in its Pisano period.

There is a table of relations compiled by Vinson [23] that was distilled into
a theorem of Renault [14] categorizing when a number has exactly $1$, $2$, or
$4$ zeros in its Pisano period.

######  Theorem 3.5 (Renault).

Let $m$ and $n$ be integer bases, then:

|  |  | $\omega(m)$ |
---|---|---|---|---
|  | 1 | 2 | 4
| 1 | 1 | 2 | 4 if $m=2$, else 2
$\omega(n)$ | 2 | 2 | 2 | 2
| 4 | 4 if $n=2$, else 2 | 2 | 4
Table 4. Table of $\omega\left(\text{LCM}(m,n)\right)$.

We will primarily concern ourselves in this paper with bases $\beta$ where
$\omega(\beta)=4$. There is a stability to these bases that allows us to
determine if the Fibonacci concatenation is normal. First we will show that in
the smallest such base, base $5$, the Fibonacci concatenation is normal.

##  4\. Bases of the form $5^{x}$

The technique to prove the Main Theorem relies on measuring the distribution
of the digits of the Fibonacci sequence. We are particularly interested in the
case where the digits are uniformly distributed.

######  Definition 4.1.

Given a number in base $\beta$, the digits $0,1,2,\ldots,\beta-1$ are
uniformly distributed if every digit occurs with a frequency of $1/\beta$.

Consider the Fibonacci sequence in base $5$. The digits in base $5$ are
$0,1,2,3,4$. Then the Fibonacci sequence in base 5 begins:

$\displaystyle(F_{n,5})=0,1,1,2,3,10,13,23,41,114,210,324,1034,1413,3002,4420,12422,22342,40314,\ldots$

There is a curious fact [12] about the distribution of the digits in the
Fibonacci sequence that only holds modulo a power of $5$:

######  Lemma 4.2 (Niederreiter [12]).

The digits $0,1,2,\ldots,5^{k}-1$ in the Fibonacci sequence modulo $5^{k}$ are
uniformly distributed.

######  Proposition 4.3.

For every positive integer $k$, the digits $0,1,2,3,4$ are uniformly
distributed in the sequences $\left(\Phi_{5^{k}}(n)\right)_{n=1}^{N_{k}}$.

###### Proof.

We proceed by induction on $k$. For $k=0$, Lemma 4.2 says that each digit is
uniformly distributed in $\left(\Phi_{5^{0}}(n)\right)_{n=1}^{N_{0}}$. Now,
suppose for all $0\leq i<j$ that the sequences
$\left(\Phi_{5^{i}}(n)\right)_{n=1}^{N_{i}}$ are uniformly distributed and
consider the sequence $\left(\Phi_{5^{j}}(n)\right)_{n=1}^{N_{j}}$. By Lemma
4.2, we know that the Fibonacci sequence modulo $5^{j+1}$ is uniformly
distributed. Further, the digits in each place $5^{i}$ for all $0\leq i<j$ are
uniformly distributed. So the digits of the Fibonacci sequence in the
$5^{j}$’s place must be uniformly distributed. It follows that the digits in
the sequence $\left(\Phi_{5^{j}}(n)\right)_{n=1}^{N_{j}}$ are uniformly
distributed. ∎

######  Example.

Consider the function $\Phi_{5^{0}}(n)$. A single period of the $5^{0}$’s
place is given below:

$\displaystyle\left(\Phi_{5^{0}}(n)\right)_{n=1}^{20}=0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1\circlearrowleft.$

Notice that each digit $0,1,2,3,4$ appears exactly four times. After each
period of twenty terms of the Fibonacci sequence in base $5$, each digit in
the $5^{0}$’s place has a frequency of $1/5$; the digits are uniformly
distributed. Next, consider the $5^{1}$’s place. The length of the period is
given by $\pi(5^{2})=100$. A single period of the $5^{1}$’s place is given
below:

$\displaystyle\left(\Phi_{5^{1}}(n)\right)_{n=1}^{100}=$ $\displaystyle
0,0,0,0,0,1,1,2,4,1,1,2,3,1,0,2,2,4,1,1,3,4,2,1,3,$ $\displaystyle
0,3,3,2,0,3,3,1,0,2,3,0,3,3,2,1,3,4,2,1,4,0,4,0,4,$ $\displaystyle
0,4,4,4,4,4,3,2,0,3,4,2,1,3,4,3,2,0,3,3,2,0,2,3,1,$ $\displaystyle
0,1,1,2,4,2,1,3,4,2,2,4,1,1,2,4,1,0,2,3,1,4,0,4,0\circlearrowleft.$

Notice again that each digit $0,1,2,3,4$ occurs exactly twenty times; the
digits are uniformly distributed. Further, there are exactly five periods of
$5^{0}$’s place digits nested in every one period of $5^{1}$’s place digits.
We can continue this pattern for every place value of the Fibonacci sequence
in base $5$.

######  Theorem 4.4.

The concatenation of the Fibonacci sequence in base $5$ is simply normal.

###### Proof.

Because the digits in every place value of the Fibonacci sequence in base $5$
are uniformly distributed, we can construct its concatenation in a particular
way that demonstrates that it is simply normal. Suppose we color the digits
Fibonacci sequence so that every digit that occurs in the $k$’s place value is
colored the same:

$\displaystyle{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{\left(\Phi_{5^{0}}(n)\right)_{n\in\mathbb{N}}}}\
\ \ \ \
{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{\left(\Phi_{5^{1}}(n)\right)_{n\in\mathbb{N}}}}\
\ \ \ \
{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}\left(\Phi_{5^{2}}(n)\right)_{n\in\mathbb{N}}}\
\ \ \ \
{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{\left(\Phi_{5^{3}}(n)\right)_{n\in\mathbb{N}}}}\
\ \ \ \
{\color[rgb]{1,0.71,0.16}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.71,0.16}\pgfsys@color@cmyk@stroke{0}{0.29}{0.84}{0}\pgfsys@color@cmyk@fill{0}{0.29}{0.84}{0}{\left(\Phi_{5^{4}}(n)\right)_{n\in\mathbb{N}}}}$
$\displaystyle(F_{n,5})={\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{0}},{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{1}},{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{1}},{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{2}},{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{3}},{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{0}},{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{3}},{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{2}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{3}},{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{4}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{1}},{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{1}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{4}},{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{2}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{0}},{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{3}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{2}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{4}},{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{1}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{0}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{3}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{4}},{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{1}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{4}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{3}},{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{3}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{0}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{0}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{2}},{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{4}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{4}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{2}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{0}},{\color[rgb]{1,0.71,0.16}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.71,0.16}\pgfsys@color@cmyk@stroke{0}{0.29}{0.84}{0}\pgfsys@color@cmyk@fill{0}{0.29}{0.84}{0}{1}}{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{2}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{4}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{2}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{2}},{\color[rgb]{1,0.71,0.16}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.71,0.16}\pgfsys@color@cmyk@stroke{0}{0.29}{0.84}{0}\pgfsys@color@cmyk@fill{0}{0.29}{0.84}{0}{2}}{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{2}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{3}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{4}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{2}},{\color[rgb]{1,0.71,0.16}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.71,0.16}\pgfsys@color@cmyk@stroke{0}{0.29}{0.84}{0}\pgfsys@color@cmyk@fill{0}{0.29}{0.84}{0}{4}}{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{0}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{3}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{4}},\ldots$

Then the concatenation of the Fibonacci sequence in base 5 is given by:

$\displaystyle\left<(F_{n,5})\right>={\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{0}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{2}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{3}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{0}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{3}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{2}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{3}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{4}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{1}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{1}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{4}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{2}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{0}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{3}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{2}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{4}}{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{1}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{0}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{3}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{4}}{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{1}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{4}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{3}}{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{3}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{0}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{0}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{2}}{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{4}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{4}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{2}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{0}}{\color[rgb]{1,0.71,0.16}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.71,0.16}\pgfsys@color@cmyk@stroke{0}{0.29}{0.84}{0}\pgfsys@color@cmyk@fill{0}{0.29}{0.84}{0}{1}}{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{2}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{4}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{2}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{2}}{\color[rgb]{1,0.71,0.16}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.71,0.16}\pgfsys@color@cmyk@stroke{0}{0.29}{0.84}{0}\pgfsys@color@cmyk@fill{0}{0.29}{0.84}{0}{2}}{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{2}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{3}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{4}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{2}}{\color[rgb]{1,0.71,0.16}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.71,0.16}\pgfsys@color@cmyk@stroke{0}{0.29}{0.84}{0}\pgfsys@color@cmyk@fill{0}{0.29}{0.84}{0}{4}}{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{0}}{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{3}}{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{1}}{\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color<EMAIL_ADDRESS>
We can imagine the process of concatenating the Fibonacci sequence in base $5$
through this coloring technique by taking the digits $0,1,2,3,4$ in a
piecemeal fashion extracted from each sequence
$\left(\Phi_{5^{k}}(n)\right)_{n\in\mathbb{N}}$ and threading them into the
appropriate place. Every digit in the Fibonacci concatenation in base $5$
belongs to a particular $\left(\Phi_{5^{k}}(n)\right)_{n\in\mathbb{N}}$.
Further, all of the digits in
${\color[rgb]{0.72,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.72,0,0}\pgfsys@color@cmyk@stroke{0}{0.89}{0.94}{0.28}\pgfsys@color@cmyk@fill{0}{0.89}{0.94}{0.28}{\left(\Phi_{5^{0}}(n)\right)_{n\in\mathbb{N}}}}$
occur with a frequency of $1/5$, and all of the digits in
${\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}{\left(\Phi_{5^{1}}(n)\right)_{n\in\mathbb{N}}}}$
occur with a frequency of $1/5$, and all of the digits in
${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{\left(\Phi_{5^{2}}(n)\right)_{n\in\mathbb{N}}}}$
occur with a frequency of $1/5$, etc. That is, the limiting relative frequency
of every digit $0,1,2,3,4$ in each place value of the Fibonacci concatenation
base $5$ is $1/5$. Then the limiting relative frequency of each digit
$0,1,2,3,4$ in the Fibonacci concatenation base $5$ is $1/5$. It follows that
the concatenation of the Fibonacci sequence in base $5$ is simply normal. ∎

Note that the result by Niederreiter 4.2 shows that the Fibonacci sequence is
uniformly distributed modulo every power of $5$. It immediately follows that
the same coloring technique used in Theorem 4.4 can be used to show that the
Fibonacci concatenation is simply normal in every base $\beta=5^{x}$.

######  Proposition 4.5.

In every base of the form $5^{x}$, the concatenation of the Fibonacci sequence
is simply normal.

###### Proof.

From Lemma 4.2 we know that in every base of the form $5^{x}$, the digits
$0,1,2,\ldots,5^{x}-1$ in the Fibonacci sequence base $5^{x}$ are uniformly
distributed. By induction on the result of Proposition 4.3, the digits in the
sequences $\left(\Phi_{{(5^{x})}^{k}}(n)\right)_{n\in\mathbb{N}}$ are
uniformly distributed. We can apply the same coloring technique that was used
in Theorem 4.4 to every base that is a power of $5$ because the digits are
always uniformly distributed. It follows that the Fibonacci concatenation in
every base of the form $\beta=5^{x}$ is simply normal. ∎

######  Corollary 4.6.

In every base of the form $5^{x}$, the Fibonacci concatenation is normal.

###### Proof.

This follows immediately from Proposition 4.5 and Lemma 2.2. ∎

##  5\. Bases of the form $2^{y}$

Consider the Fibonacci sequence in base 2 where the only digits are $0$ and
$1$. We are looking at the sequence:

$F_{n,2}=0,1,1,10,11,101,1000,1101,10101,100010,110111,1011001,10010000,11101001,\ldots$

We would like to apply the same coloringing technique we used in base $5$ to
the Fibonacci concatenation in base $2$. Unfortunately, the frequency of $0$’s
and $1$’s is not equal in the first five place values.

$k$’s place | $\pi(2^{k+1})$ | $\left(\Phi_{2^{k}}(n)\right)$ |  $0$’s |  $1$’s
---|---|---|---|---
$2^{0}$’s place | 3 | $0,1,1\circlearrowleft$ | $1$ | $2$
$2^{1}$’s place | $6$ | $0,0,0,1,1,0\circlearrowleft$ | $4$ | $2$
$2^{2}$’s place | $12$ | $0,0,0,0,0,1,0,1,1,0,1,0\circlearrowleft$ | $8$ | $4$
$2^{3}$’s place | $24$ | $0,0,0,0,0,0,1,1,0,0,0,1,0,1,1,0,1,1,1,0,1,0,1,0\circlearrowleft$ | $10$ | $14$
$2^{4}$’s place | $48$ | $0,0,0,0,0,0,0,0,1,0,1,1,1,0,1,0,1,1,1,1,0,0,0,1,$ |  |
|  | $0,1,1,0,1,1,0,1,0,0,0,0,1,1,0,0,0,0,1,0,1,0,1,0\circlearrowleft$ | $28$ | $20$
Table 5. Distribution of $0$’s and $1$’s in the first five place values of the
Fibonacci sequence in base $2$.

However, from Theorem 5.2 below, the sequences
$\left(\Phi_{2^{k}}(n)\right)_{n=1}^{N_{k}}$ are uniformly distributed for all
$k\geq 5$. For example, in the $2^{5}$’s place, there are exactly forty eight
$0$’s and forty eight $1$’s.

$\displaystyle\left(\Phi_{2^{5}}(n)\right)_{n=1}^{96}=$ $\displaystyle
0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,1,0,1,0,0,1,0,1,1,$ $\displaystyle
1,0,1,0,1,1,1,0,0,1,1,0,1,1,1,1,0,1,1,1,0,0,0,1,$ $\displaystyle
0,1,1,0,1,1,0,1,1,1,0,1,0,0,0,1,1,0,0,1,0,0,0,0,$ $\displaystyle
1,1,0,0,0,0,1,1,1,1,0,1,1,0,0,1,1,0,1,0,1,0,1,0\circlearrowleft.$

The proof technique that we will use to demonstrate normality of the Fibonacci
concatenation in bases of the form $2^{y}$ is very similar to the coloring
technique, except that we will ignore the first five place values.

######  Theorem 5.1.

For a base $\beta$, if there exists a $K$ such that for all $k\geq K$, the
digits $0,1,2,\ldots,\beta-1$ in the $\beta^{k}$’s place of the Fibonacci
sequence base $\beta$ occur with a frequency of $1/\beta$, then the Fibonacci
concatenation in base $\beta$ is simply normal.

###### Proof.

Suppose in base $\beta$ that the Fibonacci concatentaion is not uniformly
distributed for the first $K$ places, but for all $k\geq K$, the digits in the
$\beta^{k}$’s place are uniformly distributed. The digits in the $\beta^{0}$’s
place, $\beta^{1}$’s place, $\ldots,\beta^{K}$’s place do not effect the
limiting frequency of each digit, in the sense that the digits in these first
place values contribute a Lebesgue measure $0$ number of digits to the
Fibonacci concatenation base $\beta$. There are a finite number of place
values that are not uniformly distributed, and an infinite number of place
values that are uniformly distributed. It follows that the measure of the
digits in the $\beta^{0}$’s place, $\beta^{1}$’s place, $\ldots,\beta^{K}$’s
place is zero. ∎

Another way to say this is that the digits in the $\beta^{0}$’s place,
$\beta^{1}$’s place, $\ldots,\beta^{K}$’s place get overwhelmed in the limit.
Suppose we choose a digit at random from the Fibonacci concatenation in such a
base; the odds of choosing a digit from a place value that is not uniformly
distributed has probability $0$. With this theorem in mind, we turn our
attention back to the Fibonacci sequence in base $2$.

The distribution of digits of the Fibonacci sequence modulo $2^{k}$ is well
established. Jacobson [8] completely described the number of occurrences of
$0$’s and $1$’s. He observed that for the Fibonacci sequence modulo $2^{k}$,
there is a “type of stability” that occurs when $k\geq 5$.

######  Theorem 5.2 (Jacobson).

Denote the number of occurrences of $z$ as a residue in one (shortest) period
of the Fibonacci sequence modulo $m$ by $v(m,z)$. Then for the Fibonacci
sequence modulo $2^{k}$ and for $k\geq 5$, we have:

$\displaystyle v(2^{k},z)=$ $\displaystyle\begin{cases}1&\text{if}\ z\equiv
3\mod 4\\\ 2&\text{if}\ z\equiv 0\mod 8\\\ 3&\text{if}\ z\equiv 1\mod 4\\\
8&\text{if}\ z\equiv 2\mod 32\\\ 0&\text{for all other residues.}\end{cases}$

Jacobson recognized that after the $2^{4}$’s place, there is a regular pattern
that emerges. This stability of the Fibonacci sequence modulo $2$ allows us to
make observations about the Fibonacci concatenation in base $2$.

######  Theorem 5.3.

For all $k\geq 5$, the digits $0$ and $1$ in
$\left(\Phi_{2^{k}}(n)\right)_{n\in\mathbb{N}}$ are uniformly distributed.

###### Proof.

Consider the Fibonacci sequence in base $2$ and let $k\geq 5$. We will
represent numbers written in binary modulo $2^{k+1}$ in the following way:

$1\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}\quad\text{ and }\quad
0\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}.$

Consider the occurence of numbers congruent to $3$ modulo $4$ in the Fibonacci
sequence modulo $2^{k+1}$. Every number that has a residue of $3$ modulo $4$
occurs exactly once in one (shortest) period of the Fibonacci sequence modulo
$2^{k+1}$. That is, the numbers

$1\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}11\quad\text{ and }\quad
0\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}11.$

each occur exactly once in $\left(\Phi_{2^{k}}(n)\right)_{n=1}^{N_{k}}$. Next,
consider the occurence of numbers congruent to $0$ modulo $8$ in the Fibonacci
sequence modulo $2^{k+1}$. Every number that has a residue of $0$ modulo $8$
occurs exactly twice in one (shortest) period of the Fibonacci sequence modulo
$2^{k+1}$. That is, the numbers

$1\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}000\quad\text{ and }\quad
0\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{ digits}}}a_{4}a_{3}000.$

each occur exactly twice in $\left(\Phi_{2^{k}}(n)\right)_{n=1}^{N_{k}}$.
Next, consider the occurence of numbers congruent to $1$ modulo $4$ in the
Fibonacci sequence modulo $2^{k+1}$. Every number that has a residue of $1$
modulo $4$ occurs exactly three times in one (shortest) period of the
Fibonacci sequence modulo $2^{k+1}$. That is, the numbers

$1\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}01\quad\text{ and }\quad
0\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}01.$

each occur exactly three times in
$\left(\Phi_{2^{k}}(n)\right)_{n=1}^{N_{k}}$. Finally, consider the occurence
of numbers congruent to $2$ modulo $32$ in the Fibonacci sequence modulo
$2^{k+1}$. Every number that has a residue of $2$ modulo $32$ occurs exactly
eight times in one (shortest) period of the Fibonacci sequence modulo
$2^{k+1}$. That is, the numbers

$1\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}00010\quad\text{ and }\quad
0\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{ digits}}}00010.$

each occur exactly eight times in
$\left(\Phi_{2^{k}}(n)\right)_{n=1}^{N_{k}}$. All other residues occur exactly
zero times in the Fibonacci sequence modulo $2^{k+1}$ for $k\geq 5$. Then
there is a one-to-one correspondence between numbers in the smallest period
with a 1 in the $2^{k}$ digit and numbers with a 0 in the $2^{k}$ digit.
Hence, the digits in the Fibonacci sequence are uniformly distributed in every
$2^{k}$’s place for $k\geq 5$. ∎

Now that we know that the digits $0$ and $1$ are uniformly distributed for
sufficiently large place values, we have the following result:

######  Corollary 5.4.

The Fibonacci concatenation is simply normal in every base of the form
$\beta=2^{k}$.

###### Proof.

This immediately follows from Theorem 5.1 and Theorem 5.3. ∎

Now that we know every base that is a power of $2$ is simply normal, we can
invoke Borel’s definition of normality and achieve a stronger result:

######  Theorem 5.5.

The Fibonacci concatenation is normal in every base of the form $\beta=2^{y}$.

###### Proof.

This follows immediately from Corollary 5.4 and Lemma 2.2 ∎

##  6\. Bases of the form $5^{x}2^{y}$

Consider now bases of the form $5^{x}2^{y}$. Because $5$ and $2$ are not Wall-
Sun-Sun primes, by Lemma 2.9 we know that $\pi(5^{x})=20(5^{x-1})$ and
$\pi(2^{y})=3(2^{y-1})$. Further, because $2^{y}$ and $5^{x}$ will always be
coprime, by Lemma 2.11 we know that

$\displaystyle\pi(5^{x}2^{y})=\text{LCM}\left(\pi(5^{x}),\pi(2^{y})\right)=\begin{cases}12\times
5^{x}&\text{if}\ 1\leq y\leq 3\\\ 12\times 5^{x}\times 2^{y-3}&\text{if}\
y>3.\end{cases}$

For example, if $x=y=1$, then $\pi(2\times 5)=12(5^{1})=60=\pi(10)$. Jacobson
[8] considered the Fibonacci sequence modulo integers of the form $5^{x}2^{y}$
and obtained the following result:

######  Theorem 6.1 (Jacobson).

Denote the number of occurrences of $z$ as a residue in one (shortest) period
of the Fibonacci sequence modulo $5^{x}2^{y}$ by $v(5^{x}2^{y},z)$. Then for
$x\geq 0$ and $y\geq 5$ we have that

$v(5^{x}2^{y},z)=\begin{cases}1&\text{if}\ z\equiv 3\mod 4\\\ 2&\text{if}\
z\equiv 0\mod 8\\\ 3&\text{if}\ z\equiv 1\mod 4\\\ 8&\text{if}\ z\equiv 2\mod
32\\\ 0&\text{for all other residues.}\end{cases}$

Jacobson showed here that because the Fibonacci sequence is uniformly
distributed modulo every power of $5$, the residues in the Fibonacci sequence
modulo any power of $5^{x}2^{y}$ will be the same as the residues modulo any
power of $2^{y}$ provided, $y\geq 5$.

######  Theorem 6.2.

For $\beta=5^{x}2^{y}$, and for all $k\geq 5$, the digits $0,1,\ldots,\beta-1$
in $\left(\Phi_{\beta^{k}}(n)\right)_{n\in\mathbb{N}}$ are uniformly
distributed.

###### Proof.

Let $\beta=5^{x}2^{y}$. The case $x=0$ is exactly the statement of Theorem
5.2, and the case $y=0$ is exactly the statement of Proposition 4.3. Assume
now that $x\geq 1$ and $y\geq 1$, so in particular $10\mid\beta$. The proof
follows the same structure as Theorem 5.2, but the bookkeeping is a bit more
complicated.

Since $10\mid\beta$, we have $4\mid 100_{\beta}$, $8\mid 1000_{\beta}$, and
$32\mid 100000_{\beta}$, meaning a number is 3 (resp. 1) modulo 4 exactly when
the last two digits are 3 (resp. 1) modulo 4, a number is 2 modulo 8 exactly
when the last three digits are 2 modulo 8, and a number is 8 modulo 32 exactly
when the last five digits are 8 modulo 32.

Let $a_{1}a_{0}$ be a two-digit number in base $\beta$ that is congruent to 3
modulo 4. Then from 6.1, each of these numbers (written in base $\beta$)
appears exactly once in one (shortest) period of the Fibonacci sequence modulo
$\beta^{k+1}$:

$\displaystyle\beta-1$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}$ $\displaystyle\vdots$ $\displaystyle 1$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}$ $\displaystyle 0$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}.$

Similarly, if $a_{1}a_{0}$ is a two-digit number in base $\beta$ that is
congruent to 1 modulo 4, then each of these numbers (written in base $\beta$)
appears exactly three times in one (shortest) period of the Fibonacci sequence
modulo $\beta^{k+1}$:

$\displaystyle\beta-1$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}$ $\displaystyle\vdots$ $\displaystyle 1$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}$ $\displaystyle 0$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}.$

If $a_{2}a_{1}a_{0}$ represents a three-digit number in base $\beta$ that is
congruent to 0 modulo 8, then each of these numbers appears exactly twice in
one (shortest) period of the Fibonacci sequence modulo $\beta^{k+1}$:

$\displaystyle\beta-1$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}$ $\displaystyle\vdots$ $\displaystyle 1$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}$ $\displaystyle 0$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}.$

And if $a_{4}a_{3}a_{2}a_{1}a_{0}$ represents a five-digit number that is
congruent to 2 modulo 32, then each of these numbers appears exactly eight
times in one (shortest) period of the Fibonacci sequence modulo $\beta^{k+1}$:

$\displaystyle\beta-1$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}$ $\displaystyle\vdots$ $\displaystyle 1$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}$ $\displaystyle 0$
$\displaystyle\underbrace{\ldots\ldots\ldots}_{\text{$k-5$ \text{
digits}}}a_{4}a_{3}a_{2}a_{1}a_{0}.$

No other numbers appear in the Fibonacci sequence modulo $\beta^{k+1}$. This
one-to-one correspondence shows that each first digit $0,1,\dots,\beta-1$
appears exactly as often as every other digit in the Fibonacci sequence modulo
$\beta^{k+1}$. It follows that the digits $0,1,\dots,\beta-1$ in
$\left(\Phi_{\beta^{k}}(n)\right)_{n\in\mathbb{N}}$ are uniformly distributed
for $k\geq 5$. ∎

######  Proposition 6.3.

The Fibonacci concatenation is simply normal in every base of the form
$\beta=5^{x}2^{y}$.

###### Proof.

This immediately follows from Theorem 6.2 and Theorem 6.2. ∎

As before, now that we know every base that is a power of $5^{x}2^{y}$ is
simply normal, we can invoke Borel’s definition of normality and achieve a
stronger result.

###### Proof of Main Theorem.

The proof that the Fibonacci concatenation is normal in every base of the form
$\beta=5^{x}2^{y}$ immediately follows from Proposition 6.3 and Lemma 2.2. ∎

##  7\. Other bases

In this section we provide computational evidence to suggest that our Main
Theorem holds for infinitely many bases, perhaps in every base. We begin with
bases $\beta$ such that $\omega(\beta)=4$ [18]:

$5,10,13,17,25,26,34,37,50,53,61,65,73,74,85,89,97,106,109,113,122,125,130,137,146,149,\ldots$

We have seen that in the smallest entry on this list, base $5$, the Fibonacci
concatenation is normal. There is computational and heuristic evidence to
believe the Fibonacci concatenation is normal in every base on this list. We
begin with a definition.

######  Definition 7.1.

For an integer base $\beta$, let $\Upsilon(\beta)$ denote the smallest $K$
such that for all $k\geq K$, the digits $0,1,2,\ldots,\beta-1$ are uniformly
distributed in $\left(\Phi_{\beta^{k}}(n)\right)_{n=1}^{N_{k}}$.

######  Conjecture 7.2.

For every base $\beta$ where $\omega(\beta)=4$, there exists a $K$ such that
for all $k\geq K$, the digits in the sequences
$\left(\Phi_{\beta^{k}}(n)\right)_{n\in\mathbb{N}}$ are uniformly distributed.

In fact, the data collected in Table 6111Computations done in Mathematica.
below suggests that for all prime bases $p>5$ where $\omega(p)=4$, conjecture
7.2 holds for $K=1$. In other words, the only time
$\left(\Phi_{p^{k}}(n)\right)_{n\in\mathbb{N}}$ is not uniformly distributed
is in the ones place.

Base $\beta$ | $\Upsilon(\beta)$ | Searched to $\beta^{k}$’s place
---|---|---
5 | 0 | Proven normal
13 | 1 |  $13^{4}$’s place
17 | 1 |  $17^{4}$’s place
37 | 1 |  $37^{3}$’s place
53 | 1 |  $53^{2}$’s place
61 | 1 |  $61^{2}$’s place
Table 6. The first few prime bases with four zeros in their Pisano period.

######  Conjecture 7.3.

In every base $\beta$ where $\omega(\beta)=4$, and for all nonnegative $x$,
the Fibonacci concatenation is normal in every base of the form $2^{y}\beta$.

First, computations below for small $\beta$ on the list indicate that the
digits in each place beyond $\beta^{0}$ are uniformly distributed. If
Conjecture 3.4 holds, then whenever $\omega(\beta)=4$ then
$\omega(\beta^{i})=4$ for all $i\geq 1$. This suggests applying Theorem 5.1 to
show that the Fibonacci concatenation is simply normal in these bases.
Furthermore, from Theorem 3.5, if $\beta_{1}$ and $\beta_{2}$ are relatively
prime such that $\omega(\beta_{1})=\omega(\beta_{2})=4$, then
$\omega(\beta_{1}\beta_{2})=4$ as well. Similarly, if $\omega(\beta)=4$, then
$\omega(2^{y}\beta)=4$. All of this suggests that one could mimic the proofs
in Section 6 in these cases. We could then determine what happens when a base
has a prime factorization $\beta=2^{y}p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots
p_{j}^{e_{j}}$ where for every odd prime $p$, $\omega(p)=4$.

Jacobson [8] demonstrated how to combine information about distribution of
Fibonacci numbers modulo relatively prime bases $5^{x}$ and $2^{y}$ into a
result modulo $5^{x}2^{y}$. We suggest a generalization of his approach
phrased in terms of uniform distribution of digits:

######  Conjecture 7.4.

Given two coprime bases $\beta_{1}$ and $\beta_{2}$ such that
$\Upsilon(\beta_{1})=u$ and $\Upsilon(\beta_{2})=v$ then
$\Upsilon(\beta_{1}\beta_{2})=\text{max}(uv)$. Inductively, it would follow
for any finite set of coprime bases $\beta_{1},\beta_{2},\ldots,\beta_{n}$
where $\Upsilon(\beta_{1})=u_{1}$, $\Upsilon(\beta_{2})=u_{2}$, $\ldots$,
$\Upsilon(\beta_{n})=u_{n}$ then
$\Upsilon(\beta_{1},\beta_{2},\ldots,\beta_{n})=\text{max}(u_{1},u_{2},\ldots,u_{n})$.

If we are able to determine that the sequences
$\left(\Phi_{\beta^{k}}(n)\right)_{n\in\mathbb{N}}$ are uniformly distributed
for each base of the form $2^{y}\beta$ where $\omega(\beta)=4$ and $y\geq 0$,
we could proceed as above. Applying Theorem 5.1 we know that every base of the
form $\beta\times 2^{y}$ (including powers of these bases from Conjecture 3.4)
is simply normal, and by Lemma 2.2 we would conclude that every base where
$\omega(\beta)=4$ is normal.

We now turn our attention to bases not yet covered by Conjecture 7.3. For a
base $\gamma$ that falls outside the criteria of Conjecture 7.3, the sequences
$\left(\Phi_{\gamma^{k}}(n)\right)_{n\in\mathbb{N}}$ do not obviously become
uniformly dirstibuted based on our computer search. It is possible that there
is a $K$ such that for all $k\geq K$ the sequences
$\left(\Phi_{\gamma^{k}}(n)\right)_{n\in\mathbb{N}}$ are all uniformly
distributed, but if this is the case, the smallest such $K$ is beyond our
computational power. Nevertheless, we provide below computational evidence to
believe that the Fibonacci concatenation is normal in every base.

######  Conjecture 7.5.

The Fibonacci concatenation is absolutely normal.

We will build the argument to support Conjecture 7.5 like before, by showing
that the Fibonacci concatenation is simply normal in every base. It follows
that the Fibonacci concatenation is simply normal in every _power_ of every
base. Then, by Lemma 2.2, the Fibonacci concatenation is normal in every base.

######  Conjecture 7.6.

The Fibonacci concatenation is simply normal in every base.

######  Example.

Consider again the Fibonacci sequence in base 3. Below is a table of the first
few sequences of $\left(\Phi_{3^{k}}(n)\right)_{n}^{N_{k}}$ along with a
running total of the frequency of the digits $0,1,2$ and a running percentage
showing the distribution at finite levels. The running total and running
percentages are calculated using the nesting property (Lemma 2.6): in one
period of $3^{k}$’s place digits there are three periods of $3^{k-1}$’s place
digits, nine periods of $3^{k-2}$’s place digits, twenty seven periods of
$3^{k-3}$’s place digits etc.

$3^{k}$’s |  $0$’s |  $1$’s |  $2$’s | Running total of $0$’s:$1$’s:$2$’s | Running Percentage of $0$’s:$1$’s:$2$’s
---|---|---|---|---|---
$3^{0}$’s | 2 | 3 | 3 | 2 : 3 : 3 | 25.0000% : 37.5000% : 37.5000%
$3^{1}$’s | 9 | 6 | 9 | 15 : 15 : 18 | 31.2500% : 31.2500% : 37.5000%
$3^{2}$’s | 27 | 18 | 27 | 72 : 63 : 81 |  $33.\overline{3333}$% : $29.1\overline{666}$% : 37.5000%
$3^{3}$’s | 75 | 66 | 75 | 291 : 255 : 318 |  $33.680\overline{5}\%$ : $29.513\overline{8}$% : $36.80\overline{55}\%$
$3^{4}$’s | 216 | 216 | 216 | 1089 : 981 : 1170 |  $33.6\overline{111}$% : $30.2\overline{777}$% : $36.\overline{1111}$%
$3^{5}$’s | 630 | 684 | 630 | 3897 : 3627 : 4140 | 33.4105% : 31.0957% : 35.4938%
$3^{6}$’s | 1971 | 1890 | 1971 | 13662 : 12771 : 14391 | 33.4656% : 31.2831% : 35.2513%
$3^{7}$’s | 5859 | 5778 | 5859 | 46845 : 44091 : 49032 | 33.4684% : 31.5008% : 35.0309%
$3^{8}$’s | 17577 | 17334 | 17577 | 158112 : 149607 : 164673 | 33.4705% : 31.6701% : 34.8594%
$3^{9}$’s | 52326 | 52812 | 52326 | 5266621 : 501633 : 546345 | 33.4465% : 31.8570% : 34.6964%
$3^{10}$’s | 157707 | 156978 | 157707 | 1737693 : 1661877 : 1796742 | 33.4409% : 31.9818% : 34.4577%
$3^{11}$’s | 472635 | 471906 | 472635 | 5685714 : 5457537 : 5862861 | 33.4334% : 32.0916% : 34.4750%
Table 7. Table of the number of times each digit appears in
$\left(\Phi_{3^{k}}(n)\right)_{n=1}^{N_{k}}$ for $k\leq 11$.

Notice in the table that the limiting frequency of each digit seems to
approach $1/3$. If this running percentage of the number of times each digit
$0,1,2$ appears in $\left(\Phi_{3^{k}}(n)\right)_{n=1}^{N_{k}}$ does in fact
tend to $1/3$, then each digit will appear equally often in the limit of the
Fibonacci concatenation. This is exactly what we would expect from a number
that is simply normal. From this, we could stitch together the Fibonacci
concatenation in base $3$ exactly like we did before with the coloring
technique. Note that base $3$ is not the only base $\gamma$ in which the
running percentage of digits appears to converge to $1/\gamma$. In every base
we have studied, the running percentage of digits in base $\gamma$ converges
to $1/\gamma$. Below, we graph the running percentage of the first few such
bases.

Base 3 $3^{0}$’s$\ldots 3^{11}$’s

Base 6 $6^{0}$’s$\ldots 6^{8}$’s

Base 7 $7^{0}$’s$\ldots 7^{6}$’s

Base 9 $9^{0}$’s$\ldots 9^{5}$’s

Base 11 $11^{0}$’s$\ldots 11^{5}$’s

Base 12 $12^{0}$’s$\ldots 12^{5}$’s

Base 14 $14^{0}$’s$\ldots 14^{5}$’s

Base 15 $15^{0}$’s$\ldots 15^{4}$’s

Base 18 $18^{0}$’s$\ldots 18^{4}$’s

Figure 1. Running Percentage of digits $0,1,2,\ldots,1-\gamma$ with line
$1/\gamma$

These computations provide evidence that Conjecture 7.6 holds. If Conjecture
7.6 holds for a base $\gamma$, then it necessarily holds for every base
$\gamma^{i}$ for all $i$. We could then invoke Lemma 2.2 one more time and
claim that the Fibonacce concatenation is absolutely normal.

## Acknowledgements

The authors would like to extend their sincerest gratitude to Will Brian for
his early encouragement on this project, to Marc Renault, and Joseph Vandehey
for their correspondence and expertise, and to Michael De Vlieger for his
brilliant Mathematica code.

## References

  * [1] A. S. Besicovitch.  The asymptotic distribution of the numerals in the decimal representation of the squares of the natural numbers.  Mathematische Zeitschrift, 39:146–156, 1935.
  * [2] M. Émile Borel.  Les probabilités dénombrables et leurs applications arithmétiques.  Rendiconti del Circolo Matematico di Palermo (1884-1940), 27:247–271.
  * [3] D.G. Champernowne.  The construction of decimals normal in the scale of ten.  Journal of the London Mathematical Society, s1-8:254–260, 1933\.
  * [4] A. H. Copeland and P. Erdős.  Note on normal decimals.  Canadian Journal of Mathematics, 4:58–63, 1946.
  * [5] H. Davenport and P. Erdös.  Note on normal decimals.  Canadian Journal of Mathematics, 4:58–63, 1952.
  * [6] Amos Ehrlich.  On the periods of the fibonacci sequence modulo m.  Fibonacci Quarterly, 5:11–13, 1989.
  * [7] S. P. Geller.  A computer investigation of a property of the fibonacci sequence.  Fibonacci Quarterly, 1(2):84, 1963.
  * [8] Eliot T. Jacobson.  Distribution of the fibonacci numbers mod $2^{k}$.  Fibonacci Quarterly, 30(3):211–215, 1992.
  * [9] Dov Jarden.  On the periodicity of the last digits of the fibonacci sequence.  Fibonacci Quarterly, 1(4):21–23, 1963.
  * [10] J. Klǎska.  Short remark on fibonacci-wieferich primes.  Acta Mathematica Universitatis Ostraviensis, 15(1):21–25, 2007\.
  * [11] J. L. Lagrange.  Oeuvres de lagrange.  Gauthier Villars, Paris, 7:5–182, 1877.
  * [12] Harald Niederreiter.  Distribution of the fibonacci numbers mod $5^{k}$.  Fibonacci Quarterly, 10(4):373–374, 1972.
  * [13] S. S. Pillai.  On normal numbers.  Proceedings of the Indian Academy of Science, 12:179–184, 1940\.
  * [14] Marc Renault.  The fibonacci sequence under various moduli.  Master’s thesis, 1996.
  * [15] Parousia Rockstroh Sanjai Gupta and Francis Edward Su.  Splitting fields and periods of fibonacci sequences modulo primes.  Mathematics Magazine, 85(2):130–135, 2012.
  * [16] Neil J. A. Sloane and The OEIS Foundation Inc.  The on-line encyclopedia of integer sequences A001175.  http://oeis.org/A001175, 2021.
  * [17] Neil J. A. Sloane and The OEIS Foundation Inc.  The on-line encyclopedia of integer sequences A001176.  http://oeis.org/A001176, 2021.
  * [18] Neil J. A. Sloane and The OEIS Foundation Inc.  The on-line encyclopedia of integer sequences A053029.  http://oeis.org/A053029, 2021.
  * [19] Neil J. A. Sloane and The OEIS Foundation Inc.  The on-line encyclopedia of integer sequences A053030.  http://oeis.org/A053030, 2021.
  * [20] Neil J. A. Sloane and The OEIS Foundation Inc.  The on-line encyclopedia of integer sequences A053031.  http://oeis.org/A053031, 2021.
  * [21] T. E. Stanley.  Some remarks on the periodicity of the sequence of fibonacci numbers.  Fibonacci Quarterly, 18:52–54, 1980.
  * [22] Z. H. Sun & Z. W. Sun.  Fibonacci numbers and fermat’s last theorem.  Acta Arithmetica, 60:371–388, 1992.
  * [23] J. Vinson.  The relation of the period modulo m to the rank of apparition of m in the fibonacci sequence.  Fibonacci Quarterly, 1(2):37–45, 1963.
  * [24] D. D. Wall.  Fibonacci series modulo m.  The American Mathematical Monthly, 67(6):525–532, 1960.