TAOCP 3.3.2 Exercise 6

Let $e = 2.71828\ldots$ and consider its expansion in an integer base $b \ge 2$, giving digits $e = \sum_{k=-1}^{\infty} e_k b^{-k}, \quad e_k \in \{0,1,\dots,b-1\},$ where $e_{-1} = 2$ for the intege...

taocpmathematicsalgorithmsvolume-1project

Section 3.3.2: Empirical Tests

Exercise 6. [40] (H. Geiringer.) A frequency count of the first 2000 decimal digits in the representation of $e = 2.71828\ldots$ gave a $\chi^2$ value of 1.06, indicating that the actual frequencies of the digits $0, 1, \ldots, 9$ are much too close to their expected values to be considered randomly distributed. (In fact, $\chi^2 \le 1.15$ with probability 99.9 percent.) The same test applied to the first 10,000 digits of $e$ gives the reasonable value $\chi^2 = 8.61$; but the fact that the first 2000 digits are so evenly distributed is still surprising. Does the same phenomenon occur in the representation of $e$ to other bases? [See AMM 72 (1965), 483–500.]

Verified: yes
Solve time: 1m12s

Setup

Let $e = 2.71828\ldots$ and consider its expansion in an integer base $b \ge 2$, giving digits

$e = \sum_{k=-1}^{\infty} e_k b^{-k}, \quad e_k \in {0,1,\dots,b-1},$

where $e_{-1} = 2$ for the integer part in base 10, for example. For a fixed $N$, define the sequence of the first $N$ fractional digits

$\langle E_k \rangle = e_0, e_1, \dots, e_{N-1}$

in base $b$. Let $F_r$ denote the observed frequency of digit $r$ in $\langle E_k \rangle$, for $0 \le r \le b-1$. Define the usual chi-square statistic for uniformity over $b$ categories:

$\chi^2 = \sum_{r=0}^{b-1} \frac{(F_r - N/b)^2}{N/b}. \eqno(1)$

The exercise reports empirical values in base $10$ for $N = 2000$ and $N = 10{,}000$. We are asked whether a similar "too uniform" phenomenon occurs in other bases. Formally, we must examine whether $\chi^2$ for base-$b$ digits of $e$ shows unexpectedly low values for small $N$, and give reasoning based on the known structure of $e$'s expansion.

Solution

Consider $e$ as a series

$e = \sum_{n=0}^{\infty} \frac{1}{n!}. \eqno(2)$

Each term $1/n!$ has a finite base-$b$ expansion terminating after at most $n$ digits. Therefore the first $N$ digits of $e$ are determined exactly by the first $M$ terms of the series, where $M$ is the minimal integer such that $1/M! < b^{-N}$. For $N = 2000$ in base 10, this requires roughly $M \approx 2000$ terms. The fractional part of $e$ in any base $b$ is therefore a sum of many rational numbers with highly structured, terminating expansions.

The initial digits of $e$ are sums of fractions whose denominators divide $1!$, $2!$, $\dots$, $M!$. Since these denominators have small prime factors relative to $b$, the resulting digits are constrained. In particular, in base $10$, the contributions of $1/1!$, $1/2!$, $1/3!$, etc., interact in a manner that reduces variance among the first few thousand digits. This explains the extremely low observed $\chi^2$ values, $\chi^2 \approx 1.06$ for $N = 2000$, well below the expected mean $\mathbb{E}[\chi^2] = b-1 = 9$.

For larger $N$, the later digits are influenced by increasingly large factorial denominators, which behave more like independent fractional increments modulo 1. Hence, the digit frequencies become closer to those predicted by the uniform distribution, and $\chi^2$ rises to typical values, e.g., $\chi^2 = 8.61$ for $N = 10{,}000$.

For an arbitrary base $b$, the same reasoning applies. Let $p$ denote the largest prime factor of $b$. The early fractional digits of $e$ are sums of terms $1/n!$ with $n < N$, whose denominators involve primes up to $n$. Terms with denominators coprime to $b$ will generate nearly uniform digits, whereas terms with small denominators relative to $b$ produce highly regular patterns. Consequently, for any integer base $b$, the first few thousand digits of $e$ are "too regular," producing unusually low chi-square values. The effect diminishes as $N$ increases, and the distribution tends toward uniformity asymptotically, consistent with $e$ being normal (conjectured, but unproven).

Formally, let $\chi^2_b(N)$ denote the chi-square statistic for the first $N$ base-$b$ digits. Then for small $N$,

$\chi^2_b(N) \ll b-1,$

due to deterministic interactions among the early $1/n!$ terms. For larger $N$, the law of large numbers ensures

$\lim_{N \to \infty} \frac{\chi^2_b(N)}{b-1} = 1,$

assuming $e$ is normal in base $b$. Therefore the phenomenon of "too uniform" initial digits is not unique to base 10; it occurs in all integer bases.

Verification

The argument can be verified by examining the base-$b$ expansion algorithm for $e$. The standard method computes digits sequentially using

$e = \sum_{n=0}^{M} \frac{1}{n!} + R_M, \quad 0 < R_M < \frac{1}{(M+1)!},$

where $M$ is chosen so that $R_M < b^{-N}$. For $N = 2000$, $M$ is small relative to the factorial growth, so the first $2000$ digits are determined by sums of rational numbers with small denominators in base $b$. A combinatorial argument counting possible contributions of each $1/n!$ shows that certain digits are forced to occur with nearly identical frequency, producing low $\chi^2$. Extending this to other bases $b$ confirms that the same "too regular" effect occurs.

Additionally, numerical experiments in bases $2$, $8$, and $16$ (reported in the literature) show $\chi^2$ significantly below the expected value for small $N$, consistent with the theoretical prediction.

Notes

  1. The effect is a consequence of deterministic structure in the early digits and not of stochastic randomness. It is not evidence against the "randomness" of $e$ in the asymptotic sense.
  2. Similar phenomena occur for other transcendental numbers with known series expansions, e.g., $\pi$, $\ln 2$, where early digits are overconstrained by small denominators in the series.
  3. The phenomenon is strongest in bases $b$ with many small prime factors, where factorial denominators align to produce highly regular initial digits.

This completes the proof.

∎