On the normality of Stoneham numbers, pi and log(2)David H. Bailey
http://www.davidhbailey.com
Lawrence Berkeley National Laboratory (retired)
University of California, Davis, Department of Computer Science

1 / 28

DHB receives a fax from the Simpsons
On 9 October 1992, I received this fax from thestaff of the Simpsons TV show, requesting the
40,000th digit of π. I computed the first 40,000
digits, and faxed the result back (noting thatthe 40,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, “I can recite 40,000 digits of π, and thelast digit is a 1.

2 / 28

√“Exact” value of π = 17 − 8 3 = 3.1435935394 . . .
In November 2016, the IOSR Journal of Mathematics
published the following paper:
Abstract: It is believed that pi (π) is atranscendental number. In author’s opinion, it
is not the fact. The paper aims at showingthat pi (π) is√an algebraic number with exact
value 17 − 8 3. The derivation of this value is
supported by several geometricalconstructions, arithmetic calculations and useof some simple algebraic formulae.
Another author has been√distributing manuscripts
insisting that π = (14 − 2)/4 = 3.1464466094 . . .
√I Laxman S. Gogawale, “Exact value of pi π(17 − 8 3),” IOSR Journal of Mathematics, vol. 12(Nov.-Dec. 2016), http://www.iosrjournals.org/iosr-jm/papers/Vol12-issue6/Version-1/B1206010408.pdf.

3 / 28

Normal numbers
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 for agiven 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 the above constants, for any base b, oreven for m = 1, much less for all m or all b.
Until recently, normality proofs were known only for a few constants, such as
Champernowne’s constant = 0.12345678910111213141516 . . . (which is 10-normal).
4 / 28

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.
√√
Example: The first n binary digits of 2 must have at least n one bits.
In this case, the result follows by noting that the
one-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.

1

0

0

1

×
1

1
1
0

0
1
1

1
0
1

1
1
0

1
1
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 ofalgebraic numbers,” Journal of Number Theory Bordeaux, vol. 16 (2004), 487–518.
5 / 28

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), 351–369.
2. D. H. Bailey and D. J. Broadhurst, “Parallel integer relation detection: Techniques andapplications,” Mathematics of Computation, vol. 70, no. 236 (Oct 2000), 1719–1736.
6 / 28

Helaman Ferguson’s “Syzygy” sculpture at Hamilton College, New York7 / 28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 precision level in digits).
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 was

designed for parallel systems, but runs faster even on 1 CPU.
8 / 28

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

9 / 28

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 .

10 / 28

How to compute binary digits of log 2 beginning at an arbitrary position
1996 result: Consider this well-known formula for log 2:
log 2 =∞
X1
= 0.101100010111001000010111111101111101000111001111011 . . .2n2nn=1Note 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−n{2d log 2} =
+
n
n
n=1
n=d+1
( d
) ( ∞
)
X 2d−nX 2d−n mod n
+
,
=
n
n
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 using the binary algorithm for exponentiation, using only standard arithmetic.
11 / 28

General BBP-type formulas
For any real constant α that can be written in the form
α=

∞
X
p(n)
,
b n q(n)n=0where p and q are integer polynomials, deg p < deg q, and q has no zeroes for n ≥ 0,
the same technique can be employed to compute base-b digits beginning at anarbitrary position.
What other well-known mathematical constants can be written by such a formula?
Can π be written in this form?

12 / 28

The BBP formula for π
In 1996, a PSLQ program discovered this new formula for π:


∞
X
4
1
2
1
1
π=
−
−
−
.
16k 8k + 1 8k + 4 8k + 5 8k + 6
n=0This formula permits one to compute binary (or hexadecimal) digits of π beginning at
an arbitrary starting position.
This is the first known instance of a computer program discovering a fundamentallynew formula for π.
BBP-type formulas (also discovered using PSLQ) are now known for numerous othermathematical constants.

I D. H. Bailey, P. B. Borwein and S. Plouffe, “On the rapid computation of various polylogarithmic

constants,” Mathematics of Computation, vol. 66 (Apr 1997), 903–913.
13 / 28

Some other BBP-type
formulas found using PSLQ

∞


216
72
54
9
144
−
−
−
+
(6k + 1)2
(6k + 2)2
(6k + 3)2
(6k + 4)2
(6k + 5)2
k=0

∞
2 X 1
405
81
27
243
π2 =
−
−
−
27
729k (12k + 1)2(12k + 2)2(12k + 4)2(27k + 5)2
k=0

9
9
5
1
72
−
−
−
+
−
(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
8
64k

k=0

3072
768
3072
2688
192
1536
+
+
−
−
−
−
(24k + 6)3(24k + 7)3(24k + 9)3(24k + 10)3
(24k + 11)3
(24k + 12)3
672
384
24
48
12
96
−
−
+
+
−
−
(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), 844–854.
14 / 28

BBP formulas and normality
Consider a general BBP-type constant (i.e., a formula that permits the BBP “trick”):
∞
X
p(n)
α =
,
b n q(n)n=0where p and q are integer polynomials, deg p < deg q, and q has no zeroes for n ≥ 0.
In 2001, Richard Crandall and I proved that α is b-normal iff the sequence x0 = 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 (Jun 2001), 175–190.
15 / 28

Two specific examples
Consider the sequence x0 = 0 and
xn =2xn−1 +

1n.

Then log 2 is 2-normal iff this sequence (the “BBP sequence for log 2”) is
equidistributed in the unit interval.
Similarly, consider the sequence x0 = 0 and
120n2 − 89n + 16
xn = 16xn−1 +.
512n4 − 1024n3 + 712n2 − 206n + 21
Then π is 16-normal and hence 2-normal iff this sequence (the “BBP sequence for π”)
is equidistributed in the unit interval.
Sadly, we have not yet been able to prove equidistribution for either sequence.
16 / 28

A class of provably normal constants
Crandall and I proved that an infinite class of constants are 2-normal, e.g.
∞X1
α2,3 =
n3 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 ) =

∞
X
n=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.
I D. H. Bailey and R. E. Crandall, “Random generators and normal numbers,” Experimental

Mathematics, vol. 11, no. 4 (2002), 527–546.

17 / 28

A (weak) hot spot theorem
The previous result on the normality of Stoneham numbers can now be proven much
more easily using this result from ergodic theory:
The (weak) hot spot theorem: Given the real constant α, if there exists some B suchthat for every subinterval [c, d) of [0, 1),#0≤j≤m {b j α} ∈ [c, d)≤Blim supm(d − c)m≥1then α is b-normal.
In other words, if α is not b-normal, then:
I There is some interval [c1 , d1 ) that is visited 10 times too often by shifts of thebase-b expansion of alpha;
I The is some other interval [c2 , d2 ) that is visited 100 times too often;
I There is some other interval [c3 , d3 ) that is visited 1000 times too often; etc.
However, one cannot conclude that these intervals are necessarily nested.
I L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, Dover, 1974, 77.

18 / 28

A strong hot spot theorem
In 2006 Michal Misiurewicz and I proved a stronger version of this result, using
methods of ergodic theory:
The strong hot spot theorem: Let 0.x1 x2 . . . xn be the base-b expansion of x out toposition n, so that [cn (x), dn (x)) = [0.x1 x2 . . . xn , 0.x1 x2 . . . (xn + 1)) is the n-long digit
interval containing x. If for every x in [0, 1),#0≤j<m {b j α} ∈ [cn (x), dn (x))<∞
lim inf lim sup
n≥1
mb −n
m≥1
then α is b-normal.
In other words: If α is not b-normal, then there is at least one “hot spot,” namely
some x ∈ [0, 1) such that shifts of the base-b expansion of α visit all sufficiently small
digit neighborhoods of x too often, by an arbitrarily large factor.
Conversely, if one can establish that there is no such “hot spot,” then α is b-normal.
I D. H. Bailey and M. Misiurewicz, “A strong hot spot theorem,” Proceedings of the American

Mathematical Society, vol. 134 (2006), 2495-2501.

19 / 28

Simple examples of hot spots
Consider the rational fraction 1/28:
0.0357142857142857142857142857142857142857142857142857142857142857142857 . . .

Examine the sequence of shifts of its decimal expansion:
0.3571428571428571428571428571428571428571428571428571428571428571428571 . . .
0.5714285714285714285714285714285714285714285714285714285714285714285714 . . .
0.7142857142857142857142857142857142857142857142857142857142857142857142 . . .
0.1428571428571428571428571428571428571428571428571428571428571428571428 . . .
0.4285714285714285714285714285714285714285714285714285714285714285714285 . . .
0.2857142857142857142857142857142857142857142857142857142857142857142857 . . .
0.8571428571428571428571428571428571428571428571428571428571428571428571 . . .

This sequence visits each of the six points 1/7, 2/7, 3/7, · · · , 6/7 one-sixth of the time,
which, relative to the size of a sufficiently small neighborhood around each of thesepoints, is too often by an arbitrarily large factor. Thus 1/28 is not 10-normal.
In a similar way, the constant 1/10 + 1/104 + 1/109 + 1/1016 + 1/1025 + · · · =0.10010000100000010000000010000000000100000000000010000000000000010000000 . . .

is irrational, but not 10-normal, since zero is clearly a hot spot for this constant.
20 / 28

The BBP sequence associated with α2,3
It is fairly easy to show that the BBP sequence corresponding to
α2,3 =∞
Xn=1

1
3n 23nis the following. Note that each section is repeated three times, and the sequence
evenly fills in the unit interval with all fractions of the form k3−p :0, 0, 0,1 2 1 2 1 2, , , , , ,3 3 3 3 3 3
4 8 7 5 1 2, , , , , , (repeated 3 times),
9 9 9 9 9 913 26 25 23 19 11 22 17 7 14 1 2 4 8 16 5 10 20
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
, ,
,
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27(repeated 3 times), etc.
21 / 28

Proof that α2,3 is 2-normal using the hot spot theorem
Given any x in (0, 1), let c = 0.x1 x2 . . . xn , and d = 0.x1 x2 . . . (xn + 1), so that [c, d) is
an n-digit interval containing x. Let m be any integer m > 22n , and let 3p be suchthat 3p ≤ m < 3p+1 .
Note that for j > 2n, we have [c − 1/(2j), d + 1/(2j)) is a subset of[c2−n−1 , d + 2−n−1 ). Since the length of this interval is 2−n+1 , it contains at most
3p 2−n+1 + 1 instances of k3−p for 0 ≤ k < 3p .
Therefore#0≤j<m {2j α} ∈ [c, d)
2n + #2n ≤j<m zj ∈ [c − 2−n−1 , d + 2−n−1 )
≤
m2−n
m2−n
n
p
−n+1
2 + 3(3 2
+ 1)
≤
< 8
−n
m2
Thus by the hot spot theorem (either one), α2,3 is 2-normal.
22 / 28

The constant α2,3 is not 6-normal
Consider the base-6 expansion 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 nonnormality. 23 / 28

Two more general nonnormality results on Stoneham constants
1. Given co-prime integers b ≥ 2 and c ≥ 2, and integers p, q, r ≥ 1, with neither b nor
c 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

1
c 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 provably 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), 409–422.
24 / 28

Walk on the first 100 billion base-4 digits of π

http://gigapan.com/gigapans/106803

25 / 28

Walk on pseudorandom data

26 / 28

Walk on α2,3 : Base 2 (normal) vs base 6 (nonnormal)

27 / 28

Thanks!
This talk is available at
http://www.davidhbailey.com/dhbtalks/dhb-vienna.pdf
References:
I D. H. Bailey and J. M. Borwein, “Pi day is upon us again, and we still do notknow if pi is normal,” American Mathematical Monthly, March 2014, 191–206.
I D. H. Bailey and M. Misiurewicz, “A strong hot spot theorem,” Proceedings of
the American Mathematical Society, vol. 134 (2006), 2495-2501.
I D. H. Bailey and J. M. Borwein, “Nonnormality of Stoneham constants,”
Ramanujan Journal, vol. 29 (2012), 409–422.
I F. J. Aragon Artacho, D. H. Bailey, J. M. Borwein and P. B. Borwein, “Walking
on real numbers,” Mathematical Intelligencer, vol. 35 (2013), 42–60.

28 / 28