Detailed mathematical approach

Problem Summary

We want to simulate a fair \(n\)-sided outcome by rolling only fair 5-sided and 6-sided dice. After each roll we may choose again which source die to use, so the strategy is adaptive rather than fixed in advance.

For each target size \(n\), let \(R(n)\) be the minimum expected number of source-die rolls needed to finish the simulation. The quantity required by the problem is

$S(N)=\sum_{n=2}^{N} R(n),$

and the implementation evaluates this sum at \(N=1000\).

Mathematical Approach

The key observation is that the full roll history is unnecessary. After every partial sequence, all that matters is how many equally likely unresolved branches remain.

Step 1: Compress the History into a Remainder State

Suppose we are trying to simulate one of \(n\) equally likely outcomes. After some rolls, part of the sample space may already be assignable to the final outcomes, while a leftover part is still unresolved. If that leftover contains \(r\) equally likely branches, then the future depends only on \(r\), not on the exact path that produced it.

Thus the process can be modeled by states

$r\in\{0,1,\dots,n-1\}.$

State \(r=0\) means the simulation has already finished. The initial state is \(r=1\), because before any roll there is exactly one unresolved branch.

Step 2: One Roll of a 5-Sided or 6-Sided Die

From a live state \(r\), choose a die with \(m\) faces, where \(m\in\{5,6\}\). Each unresolved branch splits into \(m\) equally likely subbranches, so the unresolved pool temporarily contains \(mr\) equiprobable cases.

Now divide \(mr\) by \(n\):

$mr=qn+r',\qquad q=\left\lfloor\frac{mr}{n}\right\rfloor,\qquad r'=mr\bmod n.$

The first \(qn\) cases can be partitioned into \(q\) complete sets of size \(n\), and each complete set can be assigned evenly to the \(n\) target outcomes. Only the leftover \(r'\) cases remain unresolved.

Therefore, after choosing die \(m\), the process continues with probability

$\Pr(\text{continue}\mid r,m)=\frac{r'}{mr}=\frac{mr\bmod n}{mr},$

and, conditional on continuation, the next state is exactly \(r'\).

Step 3: Bellman Equation for the Optimal Expectation

Let \(V_n(r)\) be the minimum expected number of additional rolls needed from state \(r\). Then the absorbing state satisfies

$V_n(0)=0.$

For every live state \(1\le r\le n-1\), one roll is spent immediately, and then we continue only if the leftover remainder is nonzero. Hence

$V_n(r)=\min_{m\in\{5,6\}}\left(1+\frac{mr\bmod n}{mr}\,V_n(mr\bmod n)\right).$

This is the Bellman optimality equation for the finite decision process. The quantity asked for one target size is

$R(n)=V_n(1).$

Step 4: Why This State Description Is Complete

Two partial roll histories with the same leftover count \(r\) are strategically identical. In both cases there are \(r\) unresolved branches, all equally likely, and the next choice only depends on how a new 5-way or 6-way split interacts with the target size \(n\).

This symmetry collapses a potentially huge decision tree into only \(n\) states and two available actions per live state. After computing \(R(n)\) for each target size, the outer problem is simply

$S(N)=\sum_{n=2}^{N} R(n).$

Worked Example: \(n=8\)

The checkpoint \(R(8)\) can be derived directly from the recurrence. Start with some useful intermediate states.

From \(r=4\), choosing the 6-sided die gives

$6\cdot 4=24=3\cdot 8+0,$

so the process certainly ends after one more roll. Therefore

$V_8(4)=1.$

From \(r=6\), choosing the 6-sided die gives remainder \(4\), so

$V_8(6)=1+\frac{4}{36}V_8(4)=1+\frac{1}{9}=\frac{10}{9}.$

At \(r=5\), the 5-sided die gives remainder \(1\), hence

$V_8(5)=1+\frac{1}{25}V_8(1).$

The 6-sided die would instead give

$1+\frac{6}{30}V_8(6)=1+\frac{1}{5}\cdot\frac{10}{9}=\frac{11}{9}.$

From the initial state \(r=1\), choosing the 5-sided die sends us to \(r=5\) with certainty, so

$V_8(1)=1+V_8(5).$

Combining the two 5-die equations gives

$V_8(1)=2+\frac{1}{25}V_8(1),$

which solves to

$R(8)=V_8(1)=\frac{25}{12}=2.083333333333\ldots$

Substituting back shows \(V_8(5)=13/12\), which is indeed smaller than \(11/9\), so the chosen actions are self-consistent. This matches the checkpoint used by the C++, Python, and Java implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same numerical plan. For a fixed \(n\), they first precompute, for every live state \(r\), the two possible next remainders and the two continuation factors corresponding to choosing the 5-sided or 6-sided die.

They then keep two value arrays and repeatedly apply the Bellman update

$V_{\text{new}}(r)=\min\left(1+\rho_5(r)V_{\text{old}}(r_5),\ 1+\rho_6(r)V_{\text{old}}(r_6)\right),$

where \(r_5,r_6\) are the next remainders and \(\rho_5(r),\rho_6(r)\) are the corresponding continuation probabilities. Iteration stops when the largest absolute change across all states falls below \(10^{-18}\), or when the fixed safety cap of 2000 sweeps is reached.

The value at the initial state \(r=1\) is recorded as \(R(n)\). An outer loop evaluates every \(n\) from \(2\) through \(1000\) and accumulates their sum.

Complexity Analysis

For one target size \(n\), building the transition data costs \(O(n)\) time and \(O(n)\) memory. Each relaxation sweep also costs \(O(n)\), because each live state compares exactly two actions.

If \(I_n\) sweeps are needed before the stopping rule is met, then computing \(R(n)\) costs \(O(nI_n)\) time and \(O(n)\) memory. Therefore the full sum up to \(N\) costs

$\sum_{n=2}^{N} O(nI_n).$

Because the implementation also imposes a fixed cap of 2000 sweeps, the worst-case growth is quadratic in \(N\) up to that constant factor. In practice the numerical updates stabilize much earlier.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=863
2. Bellman equation: Wikipedia - Bellman equation
3. Markov decision process: Wikipedia - Markov decision process
4. Rejection sampling: Wikipedia - Rejection sampling
5. Expected value: Wikipedia - Expected value