MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know it's likely that, given a finite sequence of digits, one can find that sequence in the digits of pi, but is there a proof that this is possible for all finite sequences? Or is it just very probable?

share|cite|improve this question

closed as no longer relevant by Felipe Voloch, Lee Mosher, Neil Strickland, Dmitri Pavlov, Douglas Zare May 29 '13 at 15:09

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

up vote 12 down vote accepted

This article contains the following statements.

Describing the normality property, Bailey explains that "in the familiar base 10 decimal number system, any single digit of a normal number occurs one tenth of the time, any two-digit combination occurs one one-hundredth of the time, and so on. It's like throwing a fair, ten-sided die forever and counting how often each side or combination of sides appears."

Pi certainly seems to behave this way. In the first six billion decimal places of pi, each of the digits from 0 through 9 shows up about six hundred million times. Yet such results, conceivably accidental, do not prove normality even in base 10, much less normality in other number bases.

In fact, not a single naturally occurring math constant has been proved normal in even one number base, to the chagrin of mathematicians. While many constants are believed to be normal -- including pi, the square root of 2, and the natural logarithm of 2, often written "log(2)" -- there are no proofs.

Edit: We seem to have lost Gerald Edgar's comment on another answer, which pointed out that the normality property implies but is not equivalent to the property of containing every finite sequence as a substring. For example, consider the sequence enumerating all possible finite strings, separated by increasingly huge oceans of zeros.

share|cite|improve this answer
Wow! Three simultaneous answers! – Joel David Hamkins Mar 16 '10 at 14:12
Does that mean someone deleted my comment? Or that there is a bug? – Gerald Edgar Mar 16 '10 at 16:37
It means that Pete deleted his answer, which was simultaneous and redundant with this answer. Your comment was attached to that question, so disappeared too. – Scott Morrison Mar 16 '10 at 17:00
The results mentioned in the lead to the article cited by Joel David Hamkins above are available at: "On the Random Character of Fundamental Constant Expansions" is paper no. 54. – grshutt Mar 16 '10 at 21:45

Numbers with this property belong to the set of normal numbers. All known normal numbers are "constructed"; it is not known whether a single "natural" number (square roots of nonsquares, pi, e, logarithms of integers $> 1$) is normal or not. It is believed, however, that these numbers are in fact normal (even independently from the chosen base), and thus have the desired property.

share|cite|improve this answer
I wouldn't call Chaitin's Omega "constructed" in this sense. You can view it as the probability that a binary program constructed by coin flips will halt. This is normal in each base. – Douglas Zare Mar 16 '10 at 14:29
You do have to make choices in the programming language, but it seems very different from specifying a number by its digits. – Douglas Zare Mar 16 '10 at 15:07
In light of Gerald Edgar's comment (which I mention at the end of my answer), your first sentence is the converse of what you mean to say. Namely, all normal numbers belong to the set of numbers with this property, but there are some numbers with the property that are not normal. – Joel David Hamkins Mar 18 '10 at 16:30

This is an expansion for Pi in base 16 numeric system:

$$\pi = \sum_{k = 0}^{\infty}\frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6} \right)$$

So to get k-th digit you have to get one term and take account for possible translation from a neighboring digit.

Thus to find the number of digit from which starts your arbitrary sequence, you should to solve a system of equations about the particular digits:

$$\frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6}\right)=a_1$$ $$\frac{1}{16^{k+1}} \left( \frac{4}{8(k+1) + 1} - \frac{2}{8(k+1) + 4} - \frac{1}{8(k+1) + 5} - \frac{1}{8(k+1) + 6}\right)=a_2$$ $$\frac{1}{16^{k+2}} \left( \frac{4}{8(k+2) + 1} - \frac{2}{8(k+2) + 4} - \frac{1}{8(k+2) + 5} - \frac{1}{8(k+2) + 6}\right)=a_3$$

etc. The numbers $a_k$ are unique for any sequence you are searching for.

If the system has no solution, it is likely that your sequence does not appear in the sequence of digits of Pi.

share|cite|improve this answer
The formula is due to Simon Plouffe. – S. Carnahan Nov 5 '10 at 8:58
I don't think you can get the $k$-th (decimal) digit from information about base 16 digits, which is what the formula gives you. Also, I don't see the relation between $a_1,a_2,\dots$ and the digit sequence we're trying to match. – Gerry Myerson Nov 5 '10 at 10:32
Yes, this is not for decimal digits. Only for bases 16 and 2. – Anixx Nov 5 '10 at 10:46
Maybe I'm being dumb, but I don't understand the proposed method. Since 8k+1, 8k+4, 8k+5 and 8k+6 usually won't be powers of 2, they will give infinite expansions in base 16. So, to calculate the j^{th} digit, I need to compute 1/n (in base 16) for roughly j different values of n. Your displayed equations seem to suggest that I only need to compute four values to get a given digit. – David Speyer Nov 5 '10 at 13:07
For example, how would you use this method to find an occurrence of B in the base 16 representation of pi? (Here the hexadecimal digits are 0123456789ABCDE.) – David Speyer Nov 5 '10 at 13:09

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