# Finding long strings of identical digits in transcendental numbers

### Introduction

Describing the three main streams of present-day mathematical philosophy (formalism, Platonism and intuitionism) in a well-known book, The Emperor's New Mind, R. Penrose says:

...it will perhaps be helpful if I refer to just a few of the problems. An example often referred to by Brouwer concerns the decimal expansion of $\pi = 3.141592653589793...$

Does there exists a succession of twenty consecutive sevens somewhere in this expansion, i.e. $$\pi = 3.141592653589793...77777777777777777777...$$ or does there not ?

In ordinary mathematical terms, all that we can say, as of now, is that either there does or there does not—and we do not know which! This would seem to be a harmless enough statement. However, the intuitionists would actually deny that one can validly say "either there exists a succession of twenty consecutive sevens somewhere in the decimal expansion of $\pi$, or else there does not"—unless and until one has (in some constructive way acceptable to the intuitionists) either established that there is indeed such a succession, or else established that there is none! A direct calculation could suffice to show that a succession of twenty consecutive sevens actually does exist somewhere in the decimal expansion of $\pi$, but some sort of mathematical theorem would be needed to establish that there is no such succession. No computer has yet proceeded far enough in the computation of $\pi$ to determine that there is indeed such a succession. One's expectation on probabilistic grounds would be that such a succession does actually exist, but even if the computer were to produce digits consistently at the rate of, say, $10^{10}$ per second, it would be likely to take something of the order of between one hundred and one thousand years to find the sequence!

### The actual problem

Since the above seems rather a bit beyond the scope of average computers I would like to find every sequence of length at least 10 of consecutive identical digits in the first $10^{9}$ digits of the decimal expansion of $\pi$. The solution would be better if it could be easily extensible to a multiple of $10^{9}$ digits, say the first $10^{10}$ digits of $\pi$.

We shouldn't restrict to the decimal digits of $\pi$, but preferable solutions should work with any finite numbers of digits any transcendental numbers, e.g. $e^\pi, {\sqrt 2}^{\sqrt 3}$, etc.

Techniques like parallelization, compilation, GPU support etc. are acceptable to achive any possibly efficient solutions.

### A step by step method not fulfilling expectations

In case of $\pi$ we could e.g. try something like a "step by step" approach:

l2 = Split[ First @ RealDigits[Pi, 10, 10000000, -20000000]];
Position[ Length /@ l2, Max @ (Length /@ l2)]
l2[[#]] & /@ Flatten @ %
(* {{4193044}}
{{7, 7, 7, 7, 7, 7, 7, 7, 7}} *)


and

l4 = Split[ First @ RealDigits[Pi, 10, 10000000, -40000000]];
Position[ Length /@ l4, Max @ (Length /@ l4)]
l4[[#]] & /@ Flatten @ %
(* {{5113613}, {5996894}}
{{6, 6, 6, 6, 6, 6, 6, 6, 6}, {8, 8, 8, 8, 8, 8, 8, 8, 8}} *)


Here we found only succsessions of length 9, so it is not exactly what I wanted but it helps to understand why this method suffers from time and memory problems, often yielding

No more memory available.
Mathematica kernel has shut down.
Try quitting other applications and then retry.


A "step by step" is too time-consuming because Mathematica needs to compute first decimal digits every time we want to proceed to the next step and the access time depends roughly linearly on number of steps, e.g. :

tunit = First[ Split[ First @ RealDigits[Pi, 10, 1000, -10000]]; // AbsoluteTiming];
timeT = 1/tunit Table[ First @ AbsoluteTiming[ Split[ First @ RealDigits[Pi, 10, 1000, -6000k]];],
{k, 60}];
ListLinePlot[timeT]


Maybe some Reap and Sow approach or whatever else?

-
Interesting question. After numbers of Pi are given the search for the repeat-sequence should be easily parallelizable due to complete independence of search for non-overlapping digit sub-sequences of Pi. Estimates on lower bound of computational time for an average machine or GPU could be useful. –  Vitaliy Kaurov Jun 1 '12 at 21:20
I wonder if someone could leverage a spigot algorithm for this... –  Ｊ. Ｍ. Jun 2 '12 at 1:10
A very good question but the title is quite abstract and perhaps should be more specific. –  faleichik Jun 2 '12 at 9:46
@Artes How about "Detecting consecutive digits in the decimal expansion of pi?" –  faleichik Jun 2 '12 at 12:33
Re spigots, the classic is en.wikipedia.org/wiki/Bailey–Borwein–Plouffe_formula, may be worth taking a look since it's able to produce limited numbers of digits from the middle of the sequence, potentially mitigating memory exhaustion. Perhaps could enable a moving-window-style solution? –  Reb.Cabin Jun 2 '12 at 15:11

While we wait for an MMA implementation of BBP formula to generate the digits of Pi, we can use published results to identify repeated digits and their locations. Searching through the one billion digits of Pi in the file pi-billion.txt, in chunks of 10 million digits, with built-in function StringPosition:

(patterns = Table[Table[i - 1, {9}], {i, 10}];
strngpatterns = FromCharacterCode[48 + #] & /@ patterns;
positions = {};
ii = 0;
While[ii < 99,
(* start from 10,000,000th digit and take chunks of 10,000,010 digits.*)
(* Reset the current stream position 10 digits back to account for patterns that might fall on chunk boundaries*)
begin = 10000000 + ii*10000000 - If[ii == 0, 0, 10];
SetStreamPosition[strm, begin];
positions = Join[positions, {{{begin},
MapIndexed[{#2 - 1, #1} &,
StringPosition[digitslist, #] & /@ strngpatterns] //
Select[#, (#[[2]] != {}) &] &}}];
ii++;]
Close[strm];
positions) // AbsoluteTiming


after about 10+ minutes (Intel Core2 Duo CPU T9600 2.80GHz, 8GB RAM on Windows Vista 64-bitOS, MMA V 8.0.4.0), we get

(Torn-edge image thanks to Heike's code)

Clean up the output and calculate the actual positions (subtract 1 to account for the decimal point):

{#[[2, 1 ;;, 1]], Flatten[#[[1, 1]] - 2 + #[[2, 1 ;;, 2 ;; -1]], 2]} & /@
Pick[positions, (Last@# != {}) & /@ positions] // Grid


Since StringPosition, by default, includes overlaps, we can conclude

• 6 is the only digit that appears 10 times in a row in the first one billion digits of Pi in positions (386,980,412 - 386,980,421)
• No digits appear 11 or more consecutive positions.
• Digits 1,6,7,8,9 appear 9 consecutive positions in various places.

Notes:

• The source file is quite large and takes considerable time to download. Make sure to verify that MD5 checksum provided on the website matches MD5 hash for the downloaded file.

That is, check that the following yields True:

 "3901670f41a84174103bd6a8f07651c0" ==

• Files containing 10,000,000,000,050 decimal digits of Pi are available for download at Alexander Yee`s website (Thanks to @chris for the link.)