Skip to content

Instantly share code, notes, and snippets.

@girving
Created December 3, 2016 18:05
Show Gist options
  • Save girving/b81f1006b87c03a63e4c03e5ece83f7e to your computer and use it in GitHub Desktop.
Save girving/b81f1006b87c03a63e4c03e5ece83f7e to your computer and use it in GitHub Desktop.
The complete works of Shakespeare in binary have length
s = 8 * 5.3M = 8 * 5458199 = 43665592
Let S be the set of numbers that contain the complete works of Shakespeare in binary.
If N is the number of occurrences of the complete works of Shakespeare, N is approximately
Poisson distributed with mean
E(N) = (lg n - s) 2^-s = mu
where n is viewed as a random number with the given number of digits. We have
Pr(n not in S) = Pr(N = 0)
= e^-mu
= exp(-(log n / log 2 - s) 2^-s)
= exp(-log n * 2^-s / log 2 ) exp(s 2^-s / log 2)
= exp(-A log n) B
= n^-A B
where
A = 2^-s / log 2
B = exp(s 2^-s / log 2) ~ 1
The harmonic sum of -S is about
H = sum_{n not in S} 1 / n
~ sum_n Pr(n not in S) / n
~ sum_n n^-A / n
~ sum_n n^-(1 + A)
~ int_t t^-(1 + A)
~ t^-A / A ]_1^inf
~ 1 / A
= 1 / (2^-s / log 2)
~ 2^s log 2
log10 H ~ log10 (2^s) + log10 (log 2)
= s log10 2 + log10 (log 2)
= 13144652.811250633
H ~ 6e13144652
~ 10^(10^7.1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment