27
$\begingroup$

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]

enter image description here

Maybe some Reap and Sow approach or whatever else?

$\endgroup$
12
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 1, 2012 at 21:20
  • 2
    $\begingroup$ I wonder if someone could leverage a spigot algorithm for this... $\endgroup$ Jun 2, 2012 at 1:10
  • 5
    $\begingroup$ A very good question but the title is quite abstract and perhaps should be more specific. $\endgroup$
    – faleichik
    Jun 2, 2012 at 9:46
  • 1
    $\begingroup$ @Artes How about "Detecting consecutive digits in the decimal expansion of pi?" $\endgroup$
    – faleichik
    Jun 2, 2012 at 12:33
  • 3
    $\begingroup$ Seems like BBP was part of MMA: reference.wolfram.com/legacy/explorer/RefGuide/… $\endgroup$
    – s0rce
    Jun 5, 2012 at 3:42

1 Answer 1

13
$\begingroup$

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;
strm = OpenRead["... download directory ...\\ pi-billion.txt"];
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];
digitslist = StringJoin@Read[strm, ConstantArray[Character, {10000010}]];
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

enter image description here

(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

enter image description here

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" ==
  IntegerString[FileHash["... your download directory ...\\pi-billion.txt", "MD5"], 16, 32]
  • 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.)
$\endgroup$
4
  • $\begingroup$ It might be possible to use this technique with these files? numberworld.org/digits/Pi/#Download $\endgroup$
    – chris
    Jun 5, 2012 at 7:02
  • $\begingroup$ @chris, I was hoping we could find the link to these files. (The second link on the MIT page to Kondo's website was broken). Thank you. $\endgroup$
    – kglr
    Jun 5, 2012 at 7:21
  • $\begingroup$ @kguler Thanks for your support +1. Nevertheless I am a bit dissapointed that so far no one suggested a self-sufficient solution which one could easily apply for other transcendental numbers. Moreover we would benefit from the technique. $\endgroup$
    – Artes
    Jun 5, 2012 at 10:07
  • $\begingroup$ @Artes, thank you for the upvote. Judging from the comments on your question, I would not be surprised if someone is already working on a solution. $\endgroup$
    – kglr
    Jun 5, 2012 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.