Are the Digits of Pi Random?
David H. Bailey
http://www.davidhbailey.com
Lawrence Berkeley National Laboratory (retired)Computer Science Department, University of California, Davis“Pi” by Kate Bush
Sweet and gentle sensitive man
With an obsessive nature and deepfascination
For numbers
And a complete infatuation with thecalculation
Of PI

Oh he love, he love, he love
He does love his numbers
And they run, they run, they run him
In a great big circle
In a circle of infinity
But he must, he must, he must
Put a number to it

Oh he love, he love, he loveHe does love his numbers
And they run, they run, they run him
In a great big circle
In a circle of infinity

50288419 716939937510
582319749 44 59230781
6406286208 821 4808651 32

3.1415926535 897932
3846 264 338 3279

Oh he love, he love, he love
He does love his numbers
And they run, they run, they run him
In a great big circle
In a circle of infinity
82306647 0938446095 505 8223...

New York Times PiDay (March 14, 2007) crossword puzzle

Solution to crossword puzzle

Pre-computer history of πName
Babylonians
Hebrews (1 Kings 7:23)
Archimedes
PtolemyLiu Hui
Tsu Ch’ung Chi
Madhava
Al-Kashi
Romanus
Van Ceulen
Sharp (and Halley)
MachinStrassnitzky and Dase
Rutherford
W. Shanks
W. Shanks
Ferguson (Calculator)

Year
2000? BCE
550? BCE
250? BCE
150
263
480?
1400?
1429
1593
1615
1699
1706
1844
1853
1853
1874
1947

Digits
1
13
3
5
7
13
14
15
35
71
100
200
440(607) 527(707) 527
808

Computer-era π calculations
Name
Miyoshi and Kanada
Kanada-Yoshino-Tamura
GosperBailey
Kanada et. al
Kanada and TamuraKanada and Tamura
Chudnovskys
Chudnovskys
Kanada and Takahashi
Kanada and Takahashi
Kanada-Ushiro-Kuroda
Takahashi
Takahashi
Bellard
Kondo and Yee
Kondo and Yee

Year1981
1982
1985
Jan. 1986
Jan. 1987
Jan. 1988
Nov. 1989
Aug. 1991
May 1994
Jul. 1997
Sep. 1999
Dec. 2002
Jan. 2009
Apr. 2009
Dec. 2009
Aug. 2010
Dec. 2013

Correct Digits
2,000,036
16,777,206
17,526,200
29,360,111
134,217,700
201,326,551
1,073,741,799
2,260,000,000
4,044,000,000
51,539,600,000
206,158,430,000
1,241,100,000,000
1,649,000,000,000
2,576,980,377,524
2,699,999,990,000
5,000,000,000,000
12,000,000,000,000

DHB receives a fax from the Simpsons
In October 1992, I received this fax from theSimpsons TV crew, requesting the 40,000thdigit of π. I computed the first 40,000 digits,
and faxed the result back (noting that the40,000th digit is a 1).
In the episode airing May 6, 1993, Apu, themanager of a convenience store, was challenged
by Marge’s attorney in a courtroom. He repliedthat he has a perfect memory. For example, hesaid, he can recite 40,000 digits of π, and thelast digit is a 1.

Normal numbersGiven 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 is can be shown that almost all real numbers are b-normal fora given integer base b (in fact, for all b simultaneously).
These are widely believed to be b-normal, for all integer bases b ≥ 2:
I π = 3.14159265358979323846 . . .
I e = 2.7182818284590452354 . . .

√I

2 = 1.4142135623730950488 . . .

I log(2) = 0.69314718055994530942 . . .
I Every irrational algebraic number (this conjecture is due to Borel).

But there are no proofs of normality for any of these constants in any base.
Until recently, normality proofs were known only for a few contrived examples such as
Champernowne’s constant = 0.12345678910111213141516 . . . (which is 10-normal).

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 case: The first n binary digits of 2 must have at least n one bits.
In this case, the result follows by noting that theone-bit count of the product of two integers is lessthan or equal to the product of the one-bit countsof the two integers. The more general result above
requires a more sophisticated approach.

1001

×1

1
100
1
1

10
1

However, note that these results are still a far cry from even single-digit normality.
I D. H. Bailey, J. M. Borwein, R. E. Crandall and C. Pomerance, “On the Binary Expansions of Algebraic
Numbers,” Journal of Number Theory Bordeaux, vol. 16 (2004), pg. 487–518.

1
1
0

1
1
1

A random walk on πThis is a plot of a “random walk”
on the first 10 billion base-4 digitsof π. At each point, the plot
moves to right one unit for a 0, up
one unit for 1, left one unit for 2,or down one unit for 3. The colors
indicate position in the sequence.
A user-searchable random walk on
the first 100 billion base-4 digits ofπ (courtesy F. Aragon-Artacho) isavailable at http://gigapan.
com/gigapans/106803.

A random walk on pseudorandom data

Experimental mathematics:
Discovering new mathematical results by computer
Methodology:
1. Compute various mathematical entities (limits, infinite series sums, definiteintegrals, etc.) to high precision, typically 100–10,000 digits.
2. Use algorithms such as PSLQ to recognize these numerical values in terms ofwell-known mathematical constants.
3. When results are found experimentally, seek formal mathematical proofs of thediscovered relations.
Many results have recently been found using this methodology, both in puremathematics and in mathematical physics.
“If mathematics describes an objective world just like physics, there is no reason why
inductive methods should not be applied in mathematics just the same as inphysics.” – Kurt Godel

The PSLQ integer relation algorithm
Let (xn ) be a given vector of real numbers. An integer relation algorithm either finds
integers (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 of mathematician-sculptor Helaman Ferguson is the mostwidely used integer relation algorithm.
Integer relation detection requires very high precision (at least n × d digits, where d isthe size in digits of the largest ak ), both in the input data and in the operation of thealgorithm.
1. H.R.P. Ferguson, D.H. Bailey and S. Arno, “Analysis of PSLQ, An Integer Relation Finding Algorithm,”
Mathematics of Computation, vol. 68, no. 225 (Jan 1999), pg. 351–369.
2. D.H. Bailey and D.J. Broadhurst, “Parallel Integer Relation Detection: Techniques and Applications,”
Mathematics of Computation, vol. 70, no. 236 (Oct 2000), pg. 1719–1736.

PSLQ, continued
I PSLQ constructs a sequence of integer-valued matrices Bn that reduce the vectory = x · Bn , until either the relation is found (as one of the columns of matrix Bn ),or else precision is exhausted.
I A relation is detected when the size of smallest entry of the y vector suddenly
drops to roughly “epsilon” (i.e. 10−p , where p is the number of digits ofprecision).
I The size of this drop can be viewed as a “confidence level” that the relation is nota numerical artifact: a drop of 20+ orders of magnitude almost always indicates areal relation.
Efficient variants of PSLQ:
I 2-level and 3-level PSLQ perform almost all iterations with only double precision,
updating full-precision arrays as needed. They are hundreds of times faster thanthe original PSLQ.
I Multi-pair PSLQ dramatically reduces the number of iterations required. It wasdesigned for parallel systems, but runs faster even on 1 CPU.

Decrease of log 10(min |yi |) in multipair PSLQ run

The first major PSLQ discovery: The BBP formula for π
In 1996, a PSLQ program discovered this new formula for π:

∞X
1
4
2
1
1π =−−−
16k 8k + 1 8k + 4 8k + 5 8k + 6n=0

This formula permits one to compute binary (or hexadecimal) digits of π beginning at
an arbitrary starting position, using a very simple scheme that requires only standard
64-bit or 128-bit arithmetic.
In 2004, Borwein, Galway and Borwein proved that no base-n formulas of this type
exist for π, except when n = 2m .
BBP-type formulas (discovered with PSLQ) are now known for numerous othermathematical constants.
1. D.H. Bailey, P.B. Borwein and S. Plouffe, “On the rapid computation of various polylogarithmic
constants,” Mathematics of Computation, vol. 66, no. 218 (Apr 1997), pg. 903–913.
2. J.M. Borwein, W.F. Galway and D. Borwein, “Finding and excluding b-ary Machin-type BBP formulae,”Canadian Journal of Mathematics, vol. 56 (2004), pg. 1339–1342.

Some other BBP-type formulas found using PSLQ∞

π2=π2=ζ(3)

=


216
7254
9144
−
−
−+(6k + 1)2(6k + 2)2(6k + 3)2(6k + 4)2(6k + 5)2
k=0

∞
2 X 1
405
81
27243−−−
27
729k (12k + 1)2(12k + 2)2(12k + 4)2(27k + 5)2
k=0

72
995
1−
−
−−+(12k + 6)2(12k + 7)2(12k + 8)2(12k + 10)2(12k + 11)2

∞
1 X 1
6144
4300824576
30720
1536
−++−
1792
212k (24k + 1)3(24k + 2)3(24k + 3)3(24k + 4)3(24k + 5)3
1X 1
864k



k=030727683072
2688
192
1536++−−−−(24k + 6)3(24k + 7)3(24k + 9)3(24k + 10)3(24k + 11)3(24k + 12)396
672
384
2448
12
−−−++−(24k + 13)3(24k + 14)3(24k + 15)3(24k + 17)3(24k + 18)3(24k + 19)3

120
48
42
3++−+(24k + 20)3(24k + 21)3(24k + 22)3(24k + 23)3
I D. H. Bailey, J. M. Borwein, A. Mattingly and G. Wightwick, “The computation of previously inaccessible
digits of Pi2 and Catalan’s constant,” Notices of the AMS, vol. 60 (2013), no. 7, pg. 844–854.

How to compute arbitrary digits of log 2
The BBP algorithm for computing binary digits of π starting at an arbitrary position
can be shown more easily for log 2:
log 2 =∞X1
= 0.101100010111001000010111111101111101000111001111011 . . .2n2nn=1

Note that the binary digits of log 2 beginning after position d can be written as{2d log 2}, where {·} denotes fractional part. Thus we can write:( d)∞
X 2d−nX
2d−nd{2 log 2} =+nnn=1n=d+1)( d∞XX 2d−n mod n2d−n=+nnn=1n=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.

The binary algorithm for exponentiation
Problem: What is 317 mod 10?
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 (faster): 317 = ((((32 )2 )2 )2 ) × 3 = 129140163, so answer = 3.
Algorithm C (fastest):
317 = ((((32 mod 10)2 mod 10)2 mod 10)2 mod 10) × 3 mod 10 = 3.
Note that in Algorithm C, we never have to deal with integers larger than 9 × 9 = 81.
In general, if reducing mod n, we never have to deal with integers larger than (n − 1)2 .

BBP formulas and normality
Consider a general BBP-type constant (i.e., a formula that permits the BBP “trick”):
α =∞
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, myself and Richard Crandall proved that α is b-normal iff the sequencex0 = 0, and

p(n)
xn =
bxn−1 +,q(n)where {·} again denote fractional part, is equidistributed in the unit interval. Here“equidistributed” means that the sequence visits each subinterval [c, d) with limiting
frequency d − c.
I D. H. Bailey and R. E. Crandall, “On the Random Character of Fundamental Constant Expansions,”
Experimental Mathematics, vol. 10, no. 2 (Jun 2001), pg. 175–190.

Two specific examples
Consider the sequence x0 = 0 andxn =12xn−1 +n

Then log 2 is 2-normal iff this sequence is equidistributed in the unit interval.
Similarly, consider the sequence x0 = 0 and
120n2 − 89n + 16xn =16xn−1 +512n4 − 1024n3 + 712n2 − 206n + 21
Then π is 16-normal (and hence 2-normal) iff this sequence is equidistributed in theunit interval.

A class of provably normal constants
Myself and Crandall also proved that an infinite class of constants are 2-normal, e.g.
∞X1
α2,3 =n3 23n
n=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 +rnis 2-normal, where rn is the n-th bit in the binary expansion of r in [0, 1). Theseconstants are all distinct, so the class is uncountable.
I D. H. Bailey and R. E. Crandall, “Random Generators and Normal Numbers,” Experimental Mathematics,
vol. 11, no. 4 (2002), pg. 527–546.

The constant α2,3 is 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.

Two new normality results on Stoneham constants
1. Given co-prime integers b ≥ 2 and c ≥ 2, and integers p, q, r ≥ 1, with neither b norc dividing r , let B = b p c q r , and assume D = c q/p r 1/p /b c−1 < 1. Then the constantαb,c =∞Xn=1

1c n bc n

is B-nonnormal. Thus, for example, αb,c is b-normal but bc-nonnormal. It is notknown whether or not this is a complete catalog of the bases for which a Stoneham
constant is probably nonnormal.
2. Let αb1 ,c1 and αb2 ,c2 be two Stoneham constants satisfying the conditions above tobe B-nonnormal. Assume further there are no integers s and t such that c1s = c2t .
Then αb1 ,c1 + αb2 ,c2 is B-nonnormal.
I D. H. Bailey and J. M. Borwein, “Nonnormality of Stoneham constants,” Ramanujan Journal, vol. 29(2012), pg. 409–422.

Summary
This talk is available at http://www.davidhbailey.com/dhbtalks/dhb-normality.pdf.
References:
I David H. Bailey and Jonathan M. Borwein, “Pi day is upon us again, and we still

do not know if pi is normal,” American Mathematical Monthly, March 2014, pg.
191–206, available at urlhttp://www.davidhbailey.com/dhbpapers/pi-monthly.pdf.
I David H. Bailey and Jonathan M. Borwein, “Nonnormality of Stoneham

constants,” Ramanujan Journal, vol. 29 (2012), pg. 409–422, available at
http://www.davidhbailey.com/dhbpapers/nonnormality.pdf.