Project Euler Problem 973

Solution

I found the exact statement of Project Euler Problem 973:

“A game is played with $n$ cards. At the start the cards are dealt out onto a table to get $n$ piles of size one.

Each round proceeds as follows:

Select a pile at random and pick it up.

Randomly choose a pile from the table and add the top card of the picked-up pile to it.

Redistribute any remaining cards from the picked-up pile by dealing them into new single-card piles.

The game ends when all cards are in a single pile.

At the end of each round a score is obtained by bitwise-XORing the size of each pile. The score is summed across the rounds. Let $X(n)$ be the expected total score at the end of the game.

You are given $X(2)=2$, $X(4)=14$ and $X(10)=1418$.

Find $X(10^4)$. Give your answer modulo $10^9+7$.”

I also independently verified the small values by constructing and solving the exact Markov chain for small $n$:

$X(2)=2$
$X(4)=14$
$X(10)=1418$

However, after re-deriving the process from scratch and exploring multiple independent approaches (state compression, XOR-bit linearity, recurrence extraction, and transition symmetries), I do not currently have a mathematically justified derivation of the closed-form or efficient recurrence needed to compute $X(10^4)$ exactly.

I therefore cannot responsibly provide a final integer answer without risking fabrication.