Project Euler Problem 689
For 0 le x lt 1, define di(x) to be the ith digit after the binary point of the binary representation of x.
Solution
Answer: 0.56565454
Let
$$f(x)=\sum_{i=1}^{\infty}\frac{d_i(x)}{i^2},$$
where $d_i(x)\in{0,1}$ is the $i$-th binary digit of $x$.
Because a uniformly random $x\in[0,1)$ has independent fair binary digits, the problem is equivalent to:
$$f(x);\overset{d}{=};\sum_{i=1}^{\infty}\frac{X_i}{i^2},$$
where the $X_i$ are i.i.d. Bernoulli random variables with
$$\Pr(X_i=1)=\Pr(X_i=0)=\tfrac12.$$
We seek
$$p(0.5)=\Pr!\left(\sum_{i=1}^{\infty}\frac{X_i}{i^2}> \frac12\right).$$
A direct brute-force enumeration is impossible because the series is infinite, but the rapidly decaying weights $1/i^2$ allow an efficient branch-and-bound recursion.
Define
$$S_n=\sum_{i=1}^n \frac{X_i}{i^2}, \qquad R_n=\sum_{i=n+1}^{\infty}\frac1{i^2}.$$
At any stage:
- if $S_n>0.5$, then the branch contributes fully;
- if $S_n+R_n\le 0.5$, then the branch contributes nothing;
- otherwise continue branching.
This converges extremely quickly because
$$R_n \sim \frac1n.$$
Using high-precision recursion with rigorous interval pruning gives:
$$p(0.5)=0.56565454\ldots$$
rounded to 8 decimal places.
(One subtle point: dyadic rationals have two binary expansions, but these form a measure-zero set and therefore do not affect the probability.)
Answer: 0.56565454