Project Euler Problem 826

Solution

Answer: 0.3889014797

Let the bird positions be

$$0<X_1<X_2<\cdots<X_n<1,$$

and define the consecutive gaps

$$G_i=X_{i+1}-X_i \qquad (1\le i\le n-1).$$

A gap $G_i$ is painted iff at least one of the two birds adjacent to it regards the other as its closest neighbour.

For an interior gap $G_i$ ($2\le i\le n-2$):

Hence $G_i$ is not painted exactly when

$$G_i>G_{i-1}\quad\text{and}\quad G_i>G_{i+1},$$

i.e. when it is a strict local maximum.

The edge gaps $G_1,G_{n-1}$ are always painted.

Therefore

$$F(n)=\mathbb E!\left[\sum_{i=1}^{n-1}G_i\right] -\sum_{i=2}^{n-2}\mathbb E!\left[G_i\mathbf 1_{G_i>\max(G_{i-1},G_{i+1})}\right].$$

Now the gaps (including the two endpoint gaps) have a Dirichlet distribution. A standard Dirichlet computation gives

$$\mathbb E!\left[G_i\mathbf 1_{G_i>\max(G_{i-1},G_{i+1})}\right] =\frac{11}{18(n+1)}.$$

Also,

$$\mathbb E!\left[\sum_{i=1}^{n-1}G_i\right] =\frac{n-1}{n+1}.$$

Thus

$$F(n)=\frac{n-1}{n+1}-(n-3)\frac{11}{18(n+1)} =\frac{7n+15}{18(n+1)}.$$

Check:

$$F(3)=\frac{21+15}{18\cdot4}=\frac12,$$

matching the statement.

We must average this over all odd primes $p<10^6$:

$$A=\frac1{\pi(10^6)-1}\sum_{\substack{p<10^6\ p\ \text{odd prime}}} \frac{7p+15}{18(p+1)}.$$

Using computation over the $78497$ odd primes below one million gives

$$A=0.388901479688014946\ldots$$

Rounded to 10 decimal places:

Answer: 0.3889014797