The Mathematical Intelligencer

ISSN 0343-6993

Volume 35

Number 1

Math Intelligencer (2013) 35:42-60

DOI 10.1007/s00283-012-9340-x

Walking on Real Numbers

Francisco J. AragÃ³n Artacho, David

H. Bailey, Jonathan M. Borwein & Peter

B. Borwein

1 23

Your article is protected by copyright and all

rights are held exclusively by Springer Science

+Business Media New York. This e-offprint is

for personal use only and shall not be self-

archived in electronic repositories. If you

wish to self-archive your work, please use the

accepted author’s version for posting to your

own website or your institution’s repository.

You may further deposit the accepted author’s

version on a funder’s repository at a funder’s

request, provided it is not made publicly

available until 12 months after publication.

Walking on Real

Numbers

F

RANCISCO

J. A

RAGO

Â´

N

A

RTACHO

,D

AVID

H. B

AILEY

,J

ONATHAN

M. B

ORWEIN

,

AND

P

ETER

B. B

ORWEIN

T

T

he digit expansions of

p

;

e

;

ffiffiffi

2

p

, and other mathemat-

ical constants have fascinated mathematicians from

the dawn of history. Indeed, one prime motivation

for computing and analyzing digits of

p

is to explore the

age-old question of whether and why these digits appear

˜˜random.” The first computation on ENIAC in 1949 of

p

to

2037 decimal places was proposed by John von Neumann

so as to shed some light on the distribution of

p

(and of

e

)

[

15

, pg. 277“281].

One key question of some significance is whether (and

why) numbers such as

p

and

e

are ˜˜normal.” A real constant

a

is

b

-normal if, given the positive integer

b

C

2, every

m

-long

string of base-

b

digits appears in the base-

b

expansion of

a

with precisely the expected limiting frequency 1/

b

m

.Itisa

well-established, albeit counterintuitive, fact that given an

integer

b

C

2, almost all real numbers, in the measure theory

sense, are

b

-normal. What’s more, almost all real numbers are

b

-normal simultaneously for all positive integer bases (a

property known as ˜˜absolutely normal”).

Nonetheless, it has been surprisingly difficult to prove

normality for well-known mathematical constants for any

given base

b

, much less all bases simultaneously. The first

constant to be proven 10-normal is the Champernowne

number, namely the constant 0

:

12345678910111213141516

¦

,

produced by concatenating the decimal representation of all

positive integers in order. Some additional results of this sort

were established in the 1940s by Copeland and Erd

}

os [

26

].

At present, normality proofs are not available for any well-

known constant such as

p

;

e

;

log 2

;

ffiffiffi

2

p

. We do not even know,

say, that a 1 appears one-half of the time, in the limit, in the

binary expansion of

ffiffiffi

2

p

(although it certainly appears to), nor

do we know for certain that a 1 appears infinitely often in the

decimal expansion of

ffiffiffi

2

p

. For that matter, it is widely believed

that

every

irrational algebraic number (i.e., every irrational root

of an algebraic polynomial with integer coefficients) is

b

-normal to all positive integer bases

b

, but there is no proof,

not for any specific algebraic number to any specific base.

In 2002, one of the present authors (Bailey) and Richard

Crandall showed that given a real number

r

in [0,1), with

r

k

denoting the

k

-th binary digit of

r

, the real number

a

2

;

3

Ã°

r

Ãž

:

Â¼

X

1

k

Â¼

1

1

3

k

2

3

k

Ã¾

r

k

Ã°

1

Ãž

is 2-normal. It can be seen that if

r

=

s

, then

a

2,3

(

r

)

=

a

2,3

(

s

),

so that these constants are all distinct. Since

r

can range over

the unit interval, this class of constants is uncountable. So, for

example, the constant

a

2

;

3

Â¼

a

2

;

3

Ã°

0

ÃžÂ¼

P

k

1

1

=

Ã°

3

k

2

3

k

ÃžÂ¼

0

:

0418836808315030

¦

is provably 2-normal (this special

case was proven by Stoneham in 1973 [

43

]). A similar result

applies if 2 and 3 in formula (

1

) are replaced by any pair of

coprime integers (

b

,

c

) with

b

C

2 and

c

C

2[

10

]. More

recently, Bailey and Michal Misiurewicz were able to

establish 2-normality of

a

2,3

by a simpler argument, by uti-

lizing a ˜˜hot spot” lemma proven using ergodic theory

methods [

11

].

In 2004, two of the present authors (Bailey and Jonathan

Borwein), together with Richard Crandall and Carl Pomer-

ance, proved the following: If a positive real

y

has algebraic

degree

D

[

1, then the number #(

y

,

N

) of 1-bits in the binary

expansion of

y

through bit position

N

satisfies #(

y

,

N

)

[

CN

1/

D

,

for a positive number

C

(depending on

y

) and all sufficiently

large

N

[

5

]. A related result has been obtained by Hajime

Kaneko of Kyoto University in Japan [

37

]. However, these

results fall far short of establishing

b

-normality for any irra-

tional algebraic in any base

b

, even in the single-digit sense.

Supported in part by the Director, Office of Computational and Technology Research, Division of Mathematical, Information, and Computational Scien

ces of the U.S.

Department of Energy, under contract number DE-AC02-05CH11231.

42

THE MATHEMATICAL INTELLIGENCER

2012 Springer Science+Business Media New York

DOI 10.1007/s00283-012-9340-x

Author’s

personal

copy

1 Twenty-First Century Approaches

to the Normality Problem

In spite of such developments, there is a sense in the field that

more powerful techniques must be brought to bear on this

problem before additional substantial progress can be

achieved. One idea along this line is to study directly the

decimal expansions (or expansions in other number bases) of

various mathematical constants by applying some techniques

of scientific visualization and large-scale data analysis.

In a recent paper [

4

], by accessing the results of several

extremely large recent computations [

46

,

47

], the authors tes-

ted the first roughly four trillion hexadecimal digits of

p

by

means of a Poisson process model: in this model, it is

extraordinarily unlikely that

p

is not normal base 16, given its

initial segment. During that work, the authors of [

4

], like many

others, investigated visual methods of representing their large

mathematical data sets. Their chosen tool was to represent

these data as walks in the plane.

In this work, based in part on sources such as [

22

,

23

,

21

,

19

,

14

], we make a more rigorous and quantitative study of these

walks on numbers. We pay particular attention to

p

, for which

we have copious data and which”despite the fact that its

digits can be generated by simple algorithms”behaves

remarkably ˜˜randomly.”

The organization of the article is as follows. In Section

2

we

describe and exhibit uniform walks on various numbers, both

rational and irrational, artificial and natural. In the next two

sections, we look at quantifying two of the best-known fea-

tures of random walks: the expected distance traveled after

N

steps (Section

3

) and the number of sites visited (Section

4

)

In Section

5

we describe two classes for which normality and

nonnormality results are known, and one for which we have

only surmise. In Section

6

we show various examples and

leave some open questions. Finally, in Appendix

7

we collect

the numbers we have examined, with concise definitions and

a few digits in various bases.

2 Walking on Numbers

2.1 Random and Deterministic Walks

One of our tasks is to compare deterministic walks (such as

those generated by the digit expansion of a constant) with

pseudorandom walks of the same length. For example, in

Figure

1

we draw a uniform pseudorandom walk with one

million base-4 steps, where at each step the path moves one

unit east, north, west, or south, depending on the whether the

pseudorandom iterate at that position is 0, 1, 2, or 3. The color

indicates the path followed by the walk”it is shifted up the

spectrum (red-orange-yellow-green-cyan-blue-purple-red)

following an HSV scheme with

S

and

V

equal to one. The HSV

(hue, saturation, and value) model is a cylindrical-coordinate

representation that yields a rainbow-like range of colors.

Figure 1.

A uniform pseudorandom walk.

¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦.

¦¦¦¦¦¦¦¦..

AUTHORS

FRANCISCO J. ARAGO

Â´

N ARTACHO

earned his Ph.D. in optimization in 2007 at

the University of Murcia, Spain. After work-

ing for a business in Madrid for a year, he

took a postdoctoral position at the Univer-

sity of Alicante, supported by the program

˜˜Juan de la Cierva.” In 2011, he became a

Research Associate at the Priority Research

Centre for Computer-Assisted Research

Mathematics and its Applications (CARMA),

University of Newcastle, Australia, under the

direction of Jonathan Borwein, with whom

he’s currently collaborating on several

projects.

Centre for Computer Assisted Research

Mathematics and its Applications

(CARMA)

DAVID H. BAILEY

is a Senior Scientist at

Lawrence Berkeley National Laboratory.

Before coming to the Berkeley Lab in 1998,

he was at NASA’s Ames Research Center for

14 years. Bailey has received the Chauvenet

Prize from the Mathematical Association of

America, the Sidney Fernbach Award from

the IEEE Computer Society, and the Gordon

Bell Prize from the Association for Computing

Machinery. He is the author of five books,

including

Mathematics by Experiment: Plausi-

ble Reasoning in the 21st Century

, coau-

thored with Jonathan Borwein.

Lawrence Berkeley National Laboratory

Berkeley, CA 94720

USA

2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013

43

Author’s

personal

copy

The rational numbers

Q

1and

Q

2 represent the two possi-

bilities when one computes a walk on a rational number:

either the walk is bounded as in Figure

2

(a) (for any walk with

more than 440 steps one obtains the same plot), or it is

unbounded but repeating some pattern after a finite number

of digits as in Figure

2

(b).

Of course, not all rational numbers are that easily identified

by plotting their walks. It is possible to create a rational

number whose period is of any desired length. For example,

the following rational numbers from [

39

],

Q

3

Â¼

3624360069

7000000001

and

Q

4

Â¼

123456789012

1000000000061

;

have base-10 periodic parts with length 1,750,000,000 and

1,000,000,000,060, respectively. A walk on the first million

digits of both numbers is plotted in Figure

3

. These huge

periods derive from the fact that the numerators and

denominators of

Q

3 and

Q

4 are relatively prime, and the

denominators are not congruent to 2 or 5. In such cases, the

period

P

is simply the discrete logarithm of the denomi-

nator

D

modulo 10; or, in other words,

P

is the smallest

n

such that 10

n

mod

D

Â¼

1.

Graphical walks can be generated in a similar way for other

constants in various bases”see Figures

2

through

7

.Where

the base

b

C

3, the base-

b

digits can be used to a select, as a

direction, the corresponding base-

b

complex root of unity”a

multiple of 120

for base three, a multiple of 90

for base four, a

multiple of 72

for base 5, etc. We generally treat the case

b

=

2 as a base-4 walk, by grouping together pairs of base-2

digits (we could render a base-2 walk on a line, but the

resulting images would be much less interesting). In Figure

4

the origin has been marked, but since this information is not

that important for our purposes, and can be approximately

deduced by the color in most cases, it is not indicated in the

others. The color scheme for Figures

2

through

7

is the same as

the above, except that Figure

6

is colored to indicate the

number of returns to each point.

2.2 Normal Numbers as Walks

As noted previously, proving normality for specific constants

of interest in mathematics has proven remarkably difficult.

The tenor of current knowledge in this arena is illustrated by

[

45

,

14

,

34

,

38

,

40

,

39

,

44

]. It is useful to know that, while small

in measure, the ˜˜absolutely abnormal” or ˜˜absolutely non-

normal” real numbers (namely those that are not

b

-normal for

any integer

b

) are residual in the sense of topological category

[

1

]. Moreover, the Hausdorff“Besicovitch dimension of the set

of real numbers having no asymptotic frequencies is equal to

1. Likewise the set of Liouville numbers has measure zero but

is of the second category [

18

,p.352].

(a)

(b)

Figure 2.

Walks on the rational numbers

Q

1 and

Q

2.

Figure 4.

A million-step base-4 walk on

e

.

(a)(b)

Figure 3.

Walks on the first million base-10 digits of the rationals

Q

3 and

Q

4 from [

39

].

2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013

45

Author’s

personal

copy

One question that has possessed mathematicians for cen-

turies is whether

p

is normal. Indeed, part of the original

motivation of the present study was to develop new tools for

investigating this age-old problem.

In Figure

5

we show a walk on the first 100 billion base-4

digits of

p

. This may be viewed dynamically in more detail

online at

http://gigapan.org/gigapans/106803

, where the full-

sized image has a resolution of 372,224

9

290,218 pixels

(108.03 gigapixels in total). This must be one of the largest

mathematical images ever produced. The computations for

creating this image took roughly a month, where several parts

of the algorithm were run in parallel with 20 threads on

CARMA’s MacPro cluster.

By contrast, Figure

6

exhibits a 100 million base-4 walk on

p

, where the color is coded by the number of returns to the

point. In [

4

], the authors empirically tested the normality of its

first roughly four trillion hexadecimal (base-16) digits using a

Poisson process model, and they concluded that, according to

this test, it is ˜˜extraordinarily unlikely” that

p

is not 16-normal

(of course, this result does not pretend to be a proof).

In what follows, we propose various methods of analyzing

real numbers and visualizing them as walks. Other methods

widely used to visualize numbers include the matrix repre-

sentations shown in Figure

8

, where each pixel is colored

depending on the value of the digit to the right of the decimal

point, following a left-to-right up-to-down direction (in base 4

the colors used for 0, 1, 2, and 3 are red, green, cyan, and

purple, respectively). This method has been mainly used to

visually test ˜˜randomness.” In some cases, it clearly shows the

features of some numbers; as for small periodic rationals, see

Figure

8

(c). This scheme also shows the nonnormality of the

number

a

2,3

”see Figure

8

(d) (where the horizontal red bands

correspond to the strings of zeroes)”and it captures some of

the special peculiarities of the Champernowne’s number

C

4

(normal) in Figure

8

(e). Nevertheless, it does not reveal

the apparently nonrandom behavior of numbers such

as the Erd

}

os“Borwein constant; compare Figure

8

(f) with

Figure

7

(e). See also Figure

21

.

As we will see in what follows, the study of normal numbers

and suspected normal numbers as walks will permit us to

compare them with true random (or pseudorandom) walks,

obtaining in this manner a new way to empirically test ˜˜ran-

domness” in their digits.

3 Expected Distance to the Origin

Let

b

2f

3

;

4

;

¦

g

be a fixed base, and let

X

1

;

X

2

;

X

3

;

¦

be a

sequence of independent bivariate discrete random variables

whose common probability distribution is given by

PX

Â¼

cos

2

p

b

k

sin

2

p

b

k

Â¼

1

b

for

k

Â¼

1

;

¦

;

b

:

Ã°

2

Ãž

Then the random variable

S

N

:

=

P

m

=1

N

X

m

represents a

base-

b

random walk in the plane of

N

steps.

The following result on the asymptotic expectation of the

distance to the origin of a base-

b

random walk is probably

known, but being unable to find any reference in the litera-

ture, we provide a proof.

T

HEOREM

3.1

The expected distance to the origin of a

base-b random walk of N steps is asymptotically equal

to

ffiffiffiffiffiffiffi

p

N

p

=

2.

P

ROOF

.

By the multivariate central limit theorem, the ran-

dom variable 1

=

ffiffiffiffi

N

p

P

N

m

Â¼

1

Ã°

X

m

l

Ãž

is asymptotically

bivariate normal with mean

0

0

and covariance matrix

M

,

where

l

is the two-dimensional mean vector of

X

and

M

is its

2

9

2 covariance matrix. By applying Lagrange’s trigono-

metric identities, one obtains

l

Â¼

1

b

P

b

k

Â¼

1

cos

2

p

b

k

1

b

P

b

k

Â¼

1

sin

2

p

b

k

!

Â¼

1

b

1

2

Ã¾

sin

Ã°

b

Ã¾

1

=

2

Ãž

2

p

b

Ã°Ãž

2 sin

Ã°

p

=

b

Ãž

1

2

cot

Ã°

p

=

b

Ãž

cos

Ã°

b

Ã¾

1

=

2

Ãž

2

p

b

Ã°Ãž

2 sin

Ã°

p

=

b

Ãž

0

B

@

1

C

A

Â¼

0

0

:

Ã°

3

Ãž

Thus,

M

Â¼

1

b

P

b

k

Â¼

1

cos

2

2

p

b

k

P

b

k

Â¼

1

cos

2

p

b

k

sin

2

p

b

k

P

b

k

Â¼

1

cos

2

p

b

k

sin

2

p

b

k

P

b

k

Â¼

1

sin

2

2

p

b

k

œ#

:

Ã°

4

Ãž

Figure 5.

A walk on the first 100 billion base-4 digits of

p

(normal?).

Figure 6.

A walk on the first 100 million base-4 digits of

p

, col-

ored by number of returns (normal?). Color follows an HSV model

(green-cyan-blue-purple-red) depending on the number of returns

to each point (where the maxima show a tinge of pink/red).

46

THE MATHEMATICAL INTELLIGENCER

Author’s

personal

copy

Since

X

b

k

Â¼

1

cos

2

2

p

b

k

Â¼

X

b

k

Â¼

1

1

Ã¾

cos

4

p

b

k

2

Â¼

b

2

;

X

b

k

Â¼

1

sin

2

2

p

b

k

Â¼

X

b

k

Â¼

1

1

cos

4

p

b

k

2

Â¼

b

2

;

X

b

k

Â¼

1

cos

2

p

b

k

sin

2

p

b

k

Â¼

X

b

k

Â¼

1

sin

4

p

b

k

2

Â¼

0

;

Ã°

5

Ãž

formula (

4

) reduces to

M

Â¼

1

2

0

0

1

2

:

Ã°

6

Ãž

Hence,

S

N

=

ffiffiffiffi

N

p

is asymptotically bivariate normal with mean

0

0

and covariance matrix

M

. Because its components

Ã°

S

N

1

=

ffiffiffiffi

N

p

;

S

N

2

=

ffiffiffiffi

N

p

Ãž

T

are uncorrelated, then they are inde-

pendent random variables, whose distribution is (univariate)

(a)(b)

(c)(d)

(e)(f)

Figure 7.

Walks on various numbers in different bases.

2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013

47

Author’s

personal

copy

normal with mean 0 and variance 1/2. Therefore, the random

variable

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

ffiffiffi

2

p

ffiffiffiffi

N

p

S

N

1

2

Ã¾

ffiffiffi

2

p

ffiffiffiffi

N

p

S

N

2

2

s

Ã°

7

Ãž

converges in distribution to a

v

random variable with two

degrees of freedom. Then, for

N

sufficiently large,

E

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

Ã°

S

N

1

Ãž

2

Ã¾Ã°

S

N

2

Ãž

2

q

Â¼

ffiffiffiffi

N

p

ffiffiffi

2

p

E

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

ffiffiffi

2

p

ffiffiffiffi

N

p

S

N

1

2

Ã¾

ffiffiffi

2

p

ffiffiffiffi

N

p

S

N

2

2

s

0

@

1

A

ffiffiffiffi

N

p

ffiffiffi

2

p

C

Ã°

3

=

2

Ãž

C

Ã°

1

Ãž

Â¼

ffiffiffiffiffiffiffi

p

N

p

2

;

Ã°

8

Ãž

where

E

Ã° Ãž

stands for the expectation of a random

variable. Therefore, the expected distance to the

(a)(b)

(c)(d)

(e)(f)

Figure 8.

Horizontal color representation of a million digits of various numbers.

48

THE MATHEMATICAL INTELLIGENCER

Author’s

personal

copy

origin of the random walk is asymptotically equal to

ffiffiffiffiffiffiffi

p

N

p

=

2.

As a consequence of this result, for any random walk of

N

steps in any given base, the expectation of the distance to the

origin multiplied by 2

=

ffiffiffiffiffiffiffi

p

N

p

(which we will call

normalized

distance

to the origin) must approach 1 as

N

goes to infinity.

Therefore, for a ˜˜sufficiently” big random walk, one would

expect that the arithmetic mean of the normalized distances

(which will be called

average normalized distance

to the

origin) should be close to 1.

We have created a sample of 10,000 (pseudo)random

walks base-4 of one million points each in Python

1

,andwe

have computed their average normalized distance to the ori-

gin. The arithmetic mean of these numbers for the mentioned

sample of pseudorandom walks is 1.0031, whereas its stan-

dard deviation is 0.3676, so the asymptotic result fits quite well.

We have also computed the normalized distance to the origin

of 10,000 walks of one million steps each generated by the first

ten billion digits of

p

. The resulting arithmetic mean is 1.0008,

whereas the standard deviation is 0.3682. In Table

1

we show

the average normalized distance to the origin of various

numbers. There are several surprises in there data, such as the

Table 1. Average of the normalized distance to the origin of the walk of

various constants in different bases

Number Base Steps Average normalized

distance to the origin

Normal

Mean of 10,000

random walks

4 1,000,000 1.00315 Yes

Mean of 10,000 walks

on the digits of

p

4 1,000,000 1.00083 ?

a

2,3

3 1,000,000 0.89275 ?

a

2,3

4 1,000,000 0.25901 Yes

a

2,3

5 1,000,000 0.88104 ?

a

2,3

6 1,000,000 108.02218 No

a

4,3

3 1,000,000 1.07223 ?

a

4,3

4 1,000,000 0.24268 Yes

a

4,3

6 1,000,000 94.54563 No

a

4,3

12 1,000,000 371.24694 No

a

3,5

3 1,000,000 0.32511 Yes

a

3,5

5 1,000,000 0.85258 ?

a

3,5

15 1,000,000 370.93128 No

p

4 1,000,000 0.84366 ?

p

6 1,000,000 0.96458 ?

p

10 1,000,000 0.82167 ?

p

10 10,000,000 0.56856 ?

p

10 100,000,000 0.94725 ?

p

10 1,000,000,000 0.59824 ?

e

4 1,000,000 0.59583 ?

ffiffiffi

2

p

4 1,000,000 0.72260 ?

log 2 4 1,000,000 1.21113 ?

Champernowne

C

10

10 1,000,000 59.91143 Yes

EB

(2) 4 1,000,000 6.95831 ?

CE

(10) 4 1,000,000 0.94964 ?

Rational number

Q

1

4 1,000,000 0.04105 No

Rational number

Q

2

4 1,000,000 58.40222 No

Euler constant

c

10 1,000,000 1.17216 ?

Fibonacci

F

10 1,000,000 1.24820 ?

f

Ã°

2

ÃžÂ¼

p

2

6

4 1,000,000 1.57571 ?

f

Ã°

3

Ãž

4 1,000,000 1.04085 ?

Catalan’s constant

G

4 1,000,000 0.53489 ?

Thue“Morse

TM

2

4 1,000,000 531.92344 No

Paper-folding

P

4 1,000,000 0.01336 No

Table 2. Number of points visited in various

N

-step base-4 walks. The

values of the two last columns are upper and lower bounds on the

expectation of the number of distinct sites visited during an

N

-step

random walk; see [31, Theorem 2] and [

32

]

Number Steps Sites visited Bounds on the expectation

of sites visited by a random

walk

Lower

bound

Upper

bound

Mean of 10,000

random walks

1,000,000 202,684 199,256 203,060

Mean of 10,000

walks on the

digits of

p

1,000,000 202,385 199,256 203,060

a

2,3

1,000,000 95,817 199,256 203,060

a

4,3

1,000,000 68,613 199,256 203,060

a

3,2

1,000,000 195,585 199,256 203,060

p

1,000,000 204,148 199,256 203,060

p

10,000,000 1,933,903 1,738,645 1,767,533

p

100,000,000 16,109,429 15,421,296 15,648,132

p

1,000,000,000 138,107,050 138,552,612 140,380,926

e

1,000,000 176,350 199,256 203,060

ffiffiffi

2

p

1,000,000 200,733 199,256 203,060

log 2 1,000,000 214,508 199,256 203,060

Champernowne

C

4

1,000,000 548,746 199,256 203,060

EB

(2) 1,000,000 279,585 199,256 203,060

CE(10) 1,000,000 190,239 199,256 203,060

Rational number

Q

1

1,000,000 378 199,256 203,060

Rational number

Q

2

1,000,000 939,322 199,256 203,060

Euler constant

c

1,000,000 208,957 199,256 203,060

f

Ã°

2

Ãž

1,000,000 188,808 199,256 203,060

f

Ã°

3

Ãž

1,000,000 221,598 199,256 203,060

Catalan’s

constant

G

1,000,000 195,853 199,256 203,060

TM

2

1,000,000 1,000,000 199,256 203,060

Paper-folding

P

1,000,000 21 199,256 203,060

1

Python uses the Mersenne Twister as the core generator and produces 53-bit precision floats, with a period of 2

19937

“

1

&

10

6002

. Compare the length of this period to the

comoving distance from Earth to the edge of the observable universe in any direction, which is approximately

4

:

6

10

37

nanometers, or to the number of protons in the universe,

which is approximately 10

80

.

2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013

49

Author’s

personal

copy

fact that by this measure, Champernowne’s number

C

10

is far

from what is expected of a truly ˜˜random” number.

4 Number of Points Visited during an

N

-Step

base-4 Walk

The number of distinct points visited during a walk of a given

constant (on a lattice) can be also used as an indicator of how

˜˜random” the digits of that constant are. It is well known that

the expectation of the number of distinct points visited by an

N

-step random walk on a two-dimensional lattice is asymp-

totically equal to

p

N

/log(

N

); see, for example, [

36

,pg.338]or

[

13

, pg. 27]. This result was first proven by Dvoretzky and

Erd

}

os [

33

, Thm. 1]. The main practical problem with this

asymptotic result is that its convergence is rather slow; spe-

cifically, it has order of

ON

log log

N

=

Ã°

log

N

Ãž

2

.In[

31

,

32

],

Downham and Fotopoulos show the following bounds on the

expectation of the number of distinct points,

p

Ã°

N

Ã¾

0

:

84

Ãž

1

:

16

p

1

log 2

Ã¾

log

Ã°

N

Ã¾

2

Ãž

;

p

Ã°

N

Ã¾

1

Ãž

1

:

066

p

1

log 2

Ã¾

log

Ã°

N

Ã¾

1

Ãž

!

;

Ã°

9

Ãž

which provide a tighter estimate on the expectation than the

asymptotic limit

p

N

/log(

N

). For example, for

N

=

10

6

, these

bounds are (199256.1, 203059.5), whereas

p

N

/log(

N

)

=

227396, which overestimates the expectation.

In Table

2

we have calculated the number of distinct points

visited by the base-4 walks on several constants. One can see

that the values for different step walks on

p

fit quite well the

expectation. On the other hand, numbers that are known to be

normal such as

a

2,3

or the base-4 Champernowne number

substantially differ from the expectation of a random walk.

These constants, despite being normal, do not have a ˜˜ran-

dom” appearance when one draws the associated walk, see

Figure

7

(d).

At first look, the walk on

a

2,3

might seem random, see

Figure

7

(c). A closer look, shown in Figure

12

, shows a more

complex structure: the walk appears to be somehow self-

repeating. This helps explain why the number of sites visited

by the base-4 walk on**
**