Project Euler Problem 869

Solution

Answer: 14.97696693

Let the set of primes $\le N$ be $P_N$, and let $\pi(N)=|P_N|$.

The game proceeds from the least significant bit (LSB) upward. After each guess:

You learn whether the guess was correct.
You learn whether the number ended.

Because the bit alphabet is only ${0,1}$, if a guess is wrong, the actual bit is immediately deduced. Thus after every round the player knows the exact bit that occurred and hence the exact prefix (from the LSB side) of the prime.

Therefore the optimal strategy is greedy at every state:

At a given known suffix/prefix state, guess whichever next bit (0 or 1) is more common among remaining candidate primes.

This turns the problem into a binary trie over the primes written from LSB to MSB.

For any trie node $v$:

let $c_0(v)$ = number of candidate primes whose next bit is 0,
let $c_1(v)$ = number of candidate primes whose next bit is 1.

At node $v$, the optimal expected score contribution is simply

$$\max(c_0(v),c_1(v))$$

weighted by $1/\pi(N)$, since each prime is equally likely.

Hence

$$E(N) = \frac{1}{\pi(N)} \sum_{v} \max(c_0(v),c_1(v)),$$

where the sum runs over all reachable trie states.

Using an efficient prime sieve up to $10^8$ and aggregating suffix counts by bit-length gives:

$$E(10^8)=14.976966927639143\ldots$$

Rounded to eight decimal places:

Answer: 14.97696693