Finding coffee in Pi
It is widely believed that I is a "normal number," which would mean that you can find any integer sequence you want inside the digits of I, in any base, if you look long enough.
So for Pi Day, I wanted to find c0ffee inside the hexadecimal representation of I. First I used TinyPI, a demonstration program included with the LibBF arbitrary precision floating point library, to find I to 100 million decimal places.
./tinypi -b 100000000 1e8.txt
This took five and a half minutes to run on my laptop. (I estimate it would take roughly an hour to find a billion decimal places [1].)
Note that the program takes its precision in terms of the number of decimal digits, even though the -b flag causes it to produce its output in hex. (Why 108 digits? Because I tried 106 and 107 without success.)
Next I want to search for where the string c0ffee appears.
grep -o -b c0ffee 1e8.txt
The output of TinyPi is one long string, so I don't want to print the matching line, just the match itself. That's what the -o option is for. I want to know where the match occurs, and that's what -b is for ('b' for byte offset).
This produced
19300792:c0ffee 34587678:c0ffee 70453409:c0ffee 81029400:c0ffee
This means the first occurrence of c0ffee starts in at the 193,000,791st position after the decimal point. Why's that? The first two characters in the output are "3.", but counting starts from 0, so we subtract 1 from the position reported by grep.
If you're not convinced about the position, here's a smaller example. We look for the first occurence of 888 in the hex representation of pi.
echo 3.243f6a8885a3 | grep -b -o 888
This reports 8:888 meaning it found 888 starting in the 8th position of "3.243f6a8885a3", counting from 0. And you can see that 888 starts in the 7th (hexa)decimal place.
By the way, if you'd like to search for cafe rather than c0ffee, you can find it first in position 156,230.
More Pi posts[1] This program uses the Chudnovsky algorithm, which takes
O(n (log n)^3)
time to compute n digits of I.