Solution

Answer: 6.3551758451

Let $T$ be the first index $N$ such that the cumulative bitwise OR becomes all ones:

$$x_N = 2^{32}-1.$$

We want $\mathbb E[T]$.

Step 1 — Understand the process

Each $y_i$ is a uniformly random 32-bit integer.

Focus on a single bit position $b$.

In one random integer, bit $b$ is:
$1$ with probability $1/2$,
$0$ with probability $1/2$.

After $k$ rounds, that bit is still unset iff every one of the $k$ sampled integers had a $0$ in that position:

$$P(\text{bit } b \text{ still }0\text{ after }k\text{ rounds}) = \left(\frac12\right)^k.$$

Therefore,

$$P(\text{bit } b \text{ is set after }k\text{ rounds}) = 1-2^{-k}.$$

The 32 bit positions are independent, so:

$$P(x_k = 2^{32}-1) = (1-2^{-k})^{32}.$$

Hence

$$P(T > k) = 1-(1-2^{-k})^{32}.$$

Step 2 — Expected stopping time

For any nonnegative integer-valued random variable,

$$\mathbb E[T] = \sum_{k=0}^{\infty} P(T>k).$$

Thus,

$$\boxed{ \mathbb E[T] = \sum_{k=0}^{\infty} \left[ 1-(1-2^{-k})^{32} \right] }.$$

This converges extremely quickly because $2^{-k}$ decays exponentially.

Step 3 — Inclusion–Exclusion closed form

Expand using the binomial theorem:

$$(1-2^{-k})^{32} = \sum_{j=0}^{32} \binom{32}{j}(-1)^j2^{-kj}.$$

Therefore,

$$1-(1-2^{-k})^{32} = \sum_{j=1}^{32} (-1)^{j+1}\binom{32}{j}2^{-kj}.$$

Swap sums:

$$\mathbb E[T] = \sum_{j=1}^{32} (-1)^{j+1}\binom{32}{j} \sum_{k=0}^{\infty}2^{-kj}.$$

The inner sum is geometric:

$$\sum_{k=0}^{\infty}2^{-kj} = \frac1{1-2^{-j}}.$$

Hence

$$\boxed{ \mathbb E[T] = \sum_{j=1}^{32} (-1)^{j+1} \binom{32}{j} \frac1{1-2^{-j}} }.$$

This is exact.

Step 4 — Python implementation

from math import comb

# Compute the exact expectation using inclusion-exclusion
E = 0.0

for j in range(1, 33):
    term = ((-1) ** (j + 1)) * comb(32, j) / (1 - 2**(-j))
    E += term

# Print rounded to 10 decimal places
print(f"{E:.10f}")

Step 5 — Code walkthrough

from math import comb

Imports the binomial coefficient function.

E = 0.0

Accumulator for the expectation.

for j in range(1, 33):

Iterate over the inclusion–exclusion terms.

term = ((-1) ** (j + 1)) * comb(32, j) / (1 - 2**(-j))

Computes

$$(-1)^{j+1}\binom{32}{j}\frac1{1-2^{-j}}.$$

E += term

Add the contribution.

print(f"{E:.10f}")

Formats to exactly 10 decimal places.

Step 6 — Numerical value

Evaluating the sum gives

$$\mathbb E[T] \approx 6.3551758451.$$

This makes sense:

after 1 round, each bit has probability $1/2$ of appearing,
after 6 rounds, probability a fixed bit is still missing is $2^{-6}=1/64$,
expected missing bits after 6 rounds is about $32/64=0.5$,
so completion around $6$-$7$ rounds is reasonable.

Therefore the result is consistent.

Answer: 6.3551758451

Project Euler Problem 323