It is widely believed that π is a “normal number,” which would mean that you can find any integer sequence you want inside the digits of π, in any base, if you look long enough.
So for Pi Day, I wanted to find c0ffee inside the hexadecimal representation of π. First I used TinyPI, a demonstration program included with the LibBF arbitrary precision floating point library, to find π 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 occurrence 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)³)
time to compute n digits of π.
NERSC.gov used to have a service to search for ASCII strings in Pi, but it seems to be gone now. Two friends and I would occasionally communicate by sending lists of hex offsets.
I’m tempted to resurrect it per your example, then send the resulting messages through Signal or ProtonMail.
A quick sanity check – you should expect to see c0ffee (a string of six hex digits) every 16^6 or about 16 million digits, so four times in the first 100 million digits isn’t too far off the mark.
“wanted to find c0ffee inside the hexadecimal representation of π”
Excellent way of saying it, and that’s exactly what you did.
I had a problem (embedded system, long story) where I had to find something like 0xC0FFEE in a long byte stream, /but it wasn’t required to be nibble-aligned/
I don’t think grep can do it, but have you tried to find the earliest occurrence of those 24 bits /anywhere/ in the binary representation of π? Obviously in non-aligned cases, some of the first bits and/or ending bits would be “don’t cares”.
Now THIS is what I call applied mathematics!
Dan, “c0ffee” when bit-aligned can be thought of as a sequence of 8 patterns. The first matches the exact 6-byte string “c0ffee”. The other patterns match 7 bytes, caused by successive bit-shifts of the required 0 and 1 bits. Consider the pattern which matches shifting “c0ffee” by 1 bit. The first 6 terms are (1|\xb1)(\x98)(3)(3)(2)(\xb2). That is, the first byte must be chr(ord(“c”)>>1) or chr((ord(“c”)>>1) + (1<<7)), the second byte must be chr(((ord("c") & 1)<>1)), the third byte must be chr(((ord(“0”) & 1)<>1)) (which is ‘3’), etc. The 7the byte can be any byte where bit 7 is set, because ord(“e”)&1 is true. That is, the last term in the pattern matches 128 bytes of 256. Repeat for the other 6 bit-shifts to give all 8 patterns.
The full regex is too long to give here. A Python regex to match a shift of 4 bits is: b'(\x06|\x16|\\&|6|F|V|f|v|\x86|\x96|\xa6|\xb6|\xc6|\xd6|\xe6|\xf6)(3)(\x06)(f)(f)(V)(P|Q|R|S|T|U|V|W|X|Y|Z|\\[|\\\\|\\]|\\^|_)’ assuming I did it correctly.