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 protected] and Michelle Manes Michelle Manes: Department of Mathematics, University of Hawaii, 2565 McCarthy Mall, Honolulu, HI 96822, USA [email protected]

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@cmyk@fill{0}{0.89}{0.94}{0.28}{4}}\ldots

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 6¹¹1Computations 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.

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.

The Fibonacci Sequence is Normal Base 10

Abstract.

Key words and phrases:

2020 Mathematics Subject Classification:

1. Introduction

Theorem 1.1 (Main Theorem).

2. Preliminaries

Definition 2.1.

Lemma 2.2 (Pillai).

Example.

Theorem 2.3 (Wall).

Definition 2.4.

Example.

Proposition 2.5 (Renault).

Lemma 2.6 (Wall [24]).

Example 1.

Proposition 2.7 (Jarden).

Definition 2.8 (Wall, Sun, Sun).

Lemma 2.9 (Wall).

Corollary 2.10.

Proof.

Lemma 2.11 (Wall).

Proposition 2.12.

Proof.

3. Bases and Moluli

Definition 3.1.

Lemma 3.2.

Proof.

Example.

Definition 3.3.

Conjecture 3.4.

Theorem 3.5 (Renault).

4. Bases of the form 5x5^{x}

Definition 4.1.

Lemma 4.2 (Niederreiter [12]).

Proposition 4.3.

Proof.

Example.

Theorem 4.4.

Proof.

Proposition 4.5.

Proof.

Corollary 4.6.

Proof.

5. Bases of the form 2y2^{y}

Theorem 5.1.

Proof.

Theorem 5.2 (Jacobson).

Theorem 5.3.

Proof.

Corollary 5.4.

Proof.

Theorem 5.5.

Proof.

6. Bases of the form 5x​2y5^{x}2^{y}

Theorem 6.1 (Jacobson).

Theorem 6.2.

Proof.

Proposition 6.3.

Proof.

Proof of Main Theorem.

7. Other bases

Definition 7.1.

Conjecture 7.2.

Conjecture 7.3.

Conjecture 7.4.

Conjecture 7.5.

Conjecture 7.6.

Example.

Acknowledgements

References

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

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

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