Are the digits of Pi random?
David H. Bailey
https://www.davidhbailey.com
Lawrence Berkeley National Laboratory (retired)
Updated 1 March 2024

1 / 18

DHB receives a fax from the Simpsons
In October 1992, while working at NASA, DHB
received this fax from the Simpsons TV crew,
requesting the 40,000th digit of π. He
computed and faxed back 40,000 digits, notingthat the 40,000th digit is a 1.
In the 6 May 1993 episode, Apu (manager of aconvenience store) was challenged by Marge’s
attorney in a courtroom. He replied that he hasa perfect memory; he can recite 40,000 digits ofπ, and the last digit is a 1.
No other mathematical constant has this levelof public interest in its digits!
2 / 18

Normal numbers: An embarrassing ignorance
Given integer b ≥ 2, a real number x is b-normal (or “normal base b”) if every m-longstring of digits appears in the base-b expansion of x with limiting frequency 1/b m .
Using measure theory, it can be shown that almost all real numbers are b-normal forany given integer base b. It is widely believed that all of these are b-normal, for all
integer bases b ≥ 2:
1. π = 3.14159265358979323846 . . .
2. e√= 2.7182818284590452354 . . .
3. 2 = 1.4142135623730950488 . . .
4. log(2) = 0.69314718055994530942 . . .
5. Every irrational algebraic number (Borel’s conjecture).
But there are no proofs for any of these constants in any number base. We do noteven know for sure whether the digit 7 appears 1/10 of the time in the decimal
expansion of π, or whether the digit 1 appears 1/2 of the time in the binary expansion.
Until recently, normality proofs were known only for a few contrived examples such as
Champernowne’s constant = 0.12345678910111213141516 . . . (which is 10-normal).
3 / 18

One very weak result for algebraic numbers
If x is algebraic of degree d > 1, then its binary expansion through position n musthave at least Cn1/d 1-bits, for all sufficiently large n and for some C that depends on x.
√√
Simple special case: The first n binary digits of 2 must have at least n one bits.
This result follows by noting that the one-bit countof the product of two integers is less than or equal
to the product of the one-bit counts of the twointegers. The more general result above requires amore sophisticated approach.

1001×1

1
100
1
1

10
1

1
10

1
1
1

However, note that these results are still a far cry from even single-digit normality.

1. D. H. Bailey, J. M. Borwein, R. E. Crandall and C. Pomerance, “On the binary expansions ofalgebraic numbers,” J. Number Theory Bordeaux, v. 16 (2004), 487–518; preprint at DHB’swebsite.
4 / 18

A random walk generated from the base-4 digits of π

See this user-searchable random walk on the first 100 billion base-4 digits of π(courtesy F. Aragon-Artacho), available at http://gigapan.com/gigapans/106803.
5 / 18Experimental mathematics: Data mining meets mathematical research
Methodology:
1. Compute various mathematical entities (integrals, infinite series sums, limits, etc.)
to very high numeric precision, typically 100–100,000 digits.
2. Use algorithms such as PSLQ to recognize these numerical values as results offormulas involving known mathematical constants.
3. Seek formal mathematical proofs of the discovered relations.
Many results have recently been found using this methodology, in both pure andapplied mathematics.
If mathematics describes an objective world just like physics, there is no reason whyinductive methods should not be applied in mathematics just the same as in physics.
— Kurt Godel

6 / 18

The PSLQ integer relation algorithm
Let (xn ) be a given vector of real numbers. An integer relation algorithm either findsintegers (an ) such thata1 x1 + a2 x2 + · · · + an xn = 0(to within the “epsilon” of the arithmetic being used), or else finds bounds within
which no relation can exist.
The “PSLQ” algorithm and its variants, due to mathematician-sculptor Helaman
Ferguson, is the most widely used integer relation algorithm.
Integer relation detection by any algorithm requires very high precision (at least n × ddigits, where d is the size in digits of the largest ak ), both in the input data and in theoperation of the algorithm.
1. H. R. P. Ferguson, D. H. Bailey and S. Arno, “Analysis of PSLQ, an integer relation findingalgorithm,” Math. of Computation, v. 68 (Jan 1999), 351–369; preprint at DHB’s website.
2. D. H. Bailey and D. J. Broadhurst, “Parallel integer relation detection: Techniques andapplications,” Math. of Computation, v. 70 (Oct 2000), 1719–1736; preprint at DHB’s website.
7 / 18

The BBP formula for π
In 1996, a PSLQ-like computer program discovered this new formula for π:
∞X
142
1
1
π=−−−.
16k 8k + 1 8k + 4 8k + 5 8k + 6n=0

This formula permits one to compute base-2 (binary) or base-16 (hexadecimal) digitsof π beginning at an arbitrary starting position, using a very simple scheme that
requires only standard 64-bit or 128-bit floating-point arithmetic.
In 2004, Borwein, Galway and Borwein proved that the only BBP-type formulas for π
have base n = 2m for some m. But there is both a base-2 and a base-3 formula for π 2 .
1. D. H. Bailey, P. B. Borwein and S. Plouffe, “On the rapid computation of various polylogarithmicconstants,” Math. of Computation, v. 66 (Apr 1997), 903–913; preprint at DHB’s website.
2. J. M. Borwein, W. F. Galway and D. Borwein, “Finding and excluding b-ary Machin-type BBP
formulae,” Canadian J. of Mathematics, v. 56 (2004), 1339–1342.
8 / 18

A sample of the many BBP-type formulas found using PSLQ
∞

216
7254
9144
−
−−+(6k + 1)2(6k + 2)2(6k + 3)2(6k + 4)2(6k + 5)2k=0

∞
2 X 1405
8127243π2 =−−−
27729k (12k + 1)2(12k + 2)2(12k + 4)2(27k + 5)2k=0
72995
1−−−−+(12k + 6)2(12k + 7)2(12k + 8)2(12k + 10)2(12k + 11)2
∞
1 X 1
6144
43008
24576
30720
1536
ζ(3) =−++−
1792
212k (24k + 1)3(24k + 2)3(24k + 3)3(24k + 4)3(24k + 5)3π2 =

1X 1
864k

k=03072
768
3072
2688
192
1536
++−−−−(24k + 6)3(24k + 7)3(24k + 9)3(24k + 10)3
(24k + 11)3
(24k + 12)3966723842448
12−−−++−(24k + 13)3
(24k + 14)3(24k + 15)3(24k + 17)3(24k + 18)3(24k + 19)3

12048423++−+(24k + 20)3(24k + 21)3(24k + 22)3
(24k + 23)3
1. D. H. Bailey, “A compendium of BBP-type formulas,” preprint at DHB’s website.

9 / 18

How to compute binary digits of log 2 at an arbitrary position
The BBP algorithm for computing binary digits at an arbitrary position can beillustrated as follows, based Euler’s formula for log 2:∞X
1= 0.101100010111001000010111111101111101000111001111011 . . .2
log 2 =n2nn=1Note that the binary digits of log 2 beginning at position d + 1 can be written as
frac(2d log 2), where frac(·) denotes fractional part. Thus we can write:!
!
d∞
d−n
d−n
X
X
22
frac(2d log 2) = frac
+ fracnn
n=1
n=d+1!
!
d∞X
X
2d−n mod n
2d−n= frac+ frac
,
nn
n=1

n=d+1

where we have inserted modn since were are only interested in the fractional partwhen divided by n. Now note that the numerator 2d−n mod n can be calculated very
rapidly by the binary algorithm for exponentiation.
10 / 18

The binary algorithm for exponentiation
Problem: What is 317 mod 10? In other words, what is the last decimal digit of 317 ?
Algorithm A:
317 = 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × ×3 = 129140163,
so answer = 3.
Algorithm B (much faster): 317 = ((((32 )2 )2 )2 ) × 3 = 129140163, so answer = 3.
Algorithm C (much faster still):
317 mod 10 = ((((32 mod 10)2 mod 10)2 mod 10)2 mod 10) × 3 mod 10 = 3.
Note that we never have to deal with integers larger than 9 × 9 = 81.
The BBP scheme for π, combined with the binary algorithm for exponentiation, hasbeen used to calculate a string of binary digits of π beginning at position 2 quadrillion.
All recent large computations of π (the current record is 100 trillion decimal digits)
employ the BBP scheme as a check.
11 / 18BBP formulas and normality
Consider a general BBP-type constant (i.e., a formula that permits the BBP scheme):
α=∞
Xp(n)
,b n q(n)n=0where p and q are integer polynomials, deg p < deg q, and q has no zeroes fornonnegative arguments.
In 2001, DHB and Richard Crandall proved that α is b-normal iff the sequence x0 = 0,p(n)xn = frac bxn−1 +q(n)is equidistributed in the unit interval. Here “equidistributed” means that the sequence
visits each subinterval [c, d) with limiting frequency d − c.
1. D. H. Bailey and R. E. Crandall, “On the random character of fundamental constantexpansions,” Experimental Mathematics, v. 10 (Jun 2001), 175–190; preprint at DHB’s website.
12 / 18

Two specific examples
Consider the sequence x0 = 0 and1.
xn = frac 2xn−1 +nThen log 2 is 2-normal iff this sequence is equidistributed in the unit interval.
Similarly, consider the sequence x0 = 0 and120n2 − 89n + 16
xn = frac 16xn−1 +.
512n4 − 1024n3 + 712n2 − 206n + 21
Then π is 16-normal (and hence 2-normal) iff this sequence is equidistributed in theunit interval. By the way, this iteration gives the sequence of base-16 (hexadecimal)
digits of π without any errors, as far as we can determine.
These results are promising first steps, but the question of whether log 2 or π is2-normal (or 10-normal) remains unanswered. But perhaps some smart young person...
13 / 18

A class of provably normal constants
DHB and Crandall proved that an infinite class of constants are 2-normal, for example:∞X1
α2,3 =n
3 23nn=1= 0.041883680831502985071252898624571682426096 . . .10= 0.0ab8e38f 684bda12f 684bf 35ba781948b0fcd6e9e0 . . .16
This constant was proven 2-normal by Stoneham in 1971, but we have extended this tothe case where (2, 3) are any pair (p, q) of relatively prime integers ≥ 2. We also
extended this result to an uncountable class: For any real r in [0, 1), the constant
α2,3 (r ) =∞Xn=1

1
3n 23n +rn

is 2-normal, where rn is the n-th bit in the binary expansion of r in [0, 1). These
constants are all distinct, so the class is uncountable.
1. D. H. Bailey and R. E. Crandall, “Random generators and normal numbers,” Experimental
Mathematics, v. 11 (2002), 527–546; preprint at DHB’s website.

14 / 18

A “hot spot” lemma to prove normality
A known result from measure theory: Let {frac(b j α)} be shifts of the base-b expansionof the constant α. If there exists some B such that for every subinterval (c, d) of (0, 1),#0≤j<m frac(b j α) ∈ (c, d)lim sup≤ B,m(d − c)m≥1then α is b-normal.
In plain English: If α is not b-normal, then there exists some interval (c, d) that isvisited 10 times too often relative to its size by shifts of the base-b expansion of α;
there is some other interval (c 0 , d 0 ) that is visited 100 times too often; there is someother interval (c 00 , d 00 ) that is visited 1000 times too often; etc.
Conversely, if one can show that no interval (c, d) is visited, say, more than 10 times
too often by the sequence of shifts {frac(b j α)}, then this proves α is b-normal.
This result can be employed to dramatically simplify the proofs of normality forconstants such as α2,3 and αp,q . Perhaps also for constants such as π and log 2?
15 / 18

A strong “hot spot” lemma
In 2006, DHB and Michal Misiurewicz proved a stronger version of this result, using
methods of ergodic theory: Let Xn = (0.x1 x2 x3 . . . xn ) be the base-b expansion of xout to position n. If for every x ∈ (0, 1), it is true thatlim inf lim supn≥1m≥1#0≤j<m frac(b j α) ∈ (Xn , Xn + b −n )< ∞,mb −nthen α is b-normal.
In plain English: If α is not b-normal, then there is at least one x ∈ (0, 1) such thatshifts of the base-b expansion of α visit all sufficiently small neighborhoods of x too
often, by an arbitrarily large factor. Note that this avoids the possibility, mentioned in
the previous viewgraph, that the intervals might be different.
1. DHB and M. Misiurewicz, “A strong hot spot theorem,” Proc. of the American MathematicalSociety, v. 134 (2006), 2495–2501; preprint at DHB’s website.
16 / 18

The constant α2,3 is 2-normal but not 6-normalFirst 900 base-6 digits of α2,3 :3130140430003334251130502130000001243555045432233011500243525320551352
3435410104300000000000000005141130054040555455303144250433435101241345
2351125142125134505503545015053522052044340452151505102411552500425130
0511244540010441311500324203032130000000000000000000000000000000000000
0000014212034311121452013525445342113412240220525301054204423552411055
4150155204350414555400310145303033532002534340401301240104453254343502
1420204324150255551010040433000455441145010313314511510144514123443342
3412400551313335045423530553151153501533452435450250055521453054234342
1530350125024205404135451231323245353031534552304115020154242121145201
5422225343403404505301233255344404431033324453321414150142334545424124
3203125340050134150245514404300000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000313350542444431111055534141052014540213412313001424333133115

Note the long stretches of zeroes after power-of-three positions, e.g., after 3, 9, 27, 81,
243, 727, etc. This observation can be fashioned into a rigorous proof of non-normality. 17 / 18Conclusion
1. Despite literally millennia of wonder and effort by mathematicians throughout
history, the question of whether the digits of π are “random” remains unanswered.
2. We do not even know for sure whether the digit 7 appears 1/10 of the time in thedecimal expansion of π, or whether the digit 1 appears 1/2 of the time in thebinary expansion.
3. The same conclusion applies to numerous
other well-known constants of√mathematics, including log 2, e, 2, φ (golden ratio), and more.
4. Large statistical analyses on literally trillions of digits, binary and decimal, havefailed to find any significant abnormalities. But there are no proofs.
5. On the other hand, several new results and techniques, computational as well as
theoretical, have been obtained in the past few years, suggesting that perhaps
some very bright young person...
This talk is available at:
http://www.davidhbailey.com/dhbtalks/dhb-west-point-2024.pdf
18 / 18