Project Euler Problem 610 Solution

Project Euler Problem 610 Statement

A random generator produces a sequence of symbols drawn from the set {I, V, X, L, C, D, M, #}. Each item in the sequence is determined by selecting one of these symbols at random, independently of the other items in the sequence. At each step, the seven letters are equally likely to be selected, with probability 14% each, but the # symbol only has a 2% chance of selection.

We write down the sequence of letters from left to right as they are generated, and we stop at the first occurrence of the # symbol (without writing it). However, we stipulate that what we have written down must always (when non-empty) be a valid Roman numeral representation in minimal form. If appending the next letter would contravene this then we simply skip it and try again with the next symbol generated.

Please take careful note of About... Roman Numerals for the definitive rules for this problem on what constitutes a "valid Roman numeral representation" and "minimal form". For example, the (only) sequence that represents 49 is XLIX. The subtractive combination IL is invalid because of rule (ii), while XXXXIX is valid but not minimal. The rules do not place any restriction on the number of occurrences of M, so all positive integers have a valid representation. These are the same rules as were used in Problem 89, and members are invited to solve that problem first.

Find the expected value of the number represented by what we have written down when we stop. (If nothing is written down then count that as zero.) Give your answer rounded to 8 places after the decimal point.

Solution

Project Euler Problem 610 overview:

Generate a string of symbols, left to right, from the set {I,V,X,L,C,D,M,#} with 14% for each letter and 2% for # and keep only valid minimal Roman numerals (or 0 if empty), stopping at the first #. Find the expected (average) value of the resulting numerals, rounded to 8 decimals.

Solution Summary

Note:

• $R$ is a list of all valid minimal Roman numbers (I, II, XI, XL, etc.) between $1$ and $999$, with $R[0]=∅$
• $r2n$ is a dict that converts a Roman number to its arithmetic value $r2n['XL']=40$
• $succ$ for successor (not success) that keeps valid successors for a given value. For example, $succ[40]=[41,45]$, i.e. the only valid roman digits after XL are I and V
• Lastly, $E[n]$ = the expected final value given that your current written numeral already equals $n$ (1...999) and you continue the “draw & skip invalid” process until #.

This solution models only the sub-1000 part of Roman numerals as a tiny finite state space and handles leading M’s analytically. We precompute the unique minimal Roman string for every value 0–999, then build a transition graph where an edge from $n$ to $t$ exists iff appending a letter keeps the string a valid minimal Roman under 1000; invalid draws are simply skipped.

For a state with value $v$ and $k$ valid appends, the expected value satisfies

E[v] = (p·v + q·Σ E[next]) / (p + q·k),

solved in one backward pass since successors are larger values.

Finally, from the empty state we fold in an unbounded run of leading 'M'’s via

E0 = q/(1−q)·(1000 + Σ E[c] for c∈{I,V,X,L,C,D}),

yielding the exact expectation.

Crucial modeling idea: split off the thousands

n = 1000*k + r    with k ≥ 0 and 0 ≤ r ≤ 999

The thousands block is just M repeated $k$ times and the remainder $r$ is a minimal Roman numeral below $1000$. So, if we can model the sub-1000 suffix exactly, we can treat the leading M’s analytically.

Finite state space (0–999) via canonical Roman strings

R = [H[i//100] + T[(i//10)%10] + O[i%10] for i in range(1000)]
r2n={s:i for i,s in enumerate(R)}

$O$, $T$, $H$ are the standard minimal patterns for ones/tens/hundreds.

$R[n]$ is the (possibly empty) Roman string for $n$.

$r2n$ maps string → value so we can ask “if I append a letter, what numeric value is that minimal Roman number?”

Valid transitions: append only if the result is still minimal and < 1000

From any sub-1000 state $n>0$, we can try appending each letter in "IVXLCDM". We keep only those appended results that are still valid minimal Roman numbers below $1000$:

succ=[[t for c in 'IVXLCDM' if (t:=r2n.get(R[n]+c)) is not None] for n in range(1000)]

If $R[n]+c$ is a valid minimal Roman under $1000$, r2n.get(...) returns its integer value $t$; otherwise $None$. This combines all Roman number rules into the transition graph.

Why no cycles?

Appending a Roman letter increases the numeric value (you’re adding $≥1$), so from any $n$ all successors $t$ satisfy $t>n$. Hence the graph on $[1, 999]$ is a Directed Acyclic Graph (DAG) oriented by numeric value.

The “skip invalid” probability equation

At a given (sub-1000) state with current value v and k valid appends:

• With prob $p=0.02$: we draw # and stop with value $v$.
• With prob $q=0.14$ each for the $k$ valid letters: we move to successor states.
• With prob $q$ each for the invalid letters: we ignore and try again (state unchanged).

Because invalid letters just cause a retry, the process is memoryless between “decisive events” (either we see # or we successfully append a valid letter). The per-attempt probability of a decisive event is:

r = p + q*k

E[v] = ( p * v + q * Σ E[next] ) / ( p + q*k )

k=len(succ[n])
E[n] = n if k==0 else (p*n + q*sum(E[m] for m in succ[n])) / (p + q*k)

Base case: if $k=0$ (no valid append <$1000$), on the next decisive event it must be #, so $E[n]=n$.

Because successors always have larger numeric value, we can compute $E[n]$ in decreasing $n$ and have $E[m]$ ready.

The “infinite M’s” trick for the empty state

• All seven letters are valid starts: I,V,X,L,C,D,M.
• If the next decisive symbol is:
  • # (prob $p$ each attempt): we stop with $0$.
  • M (prob $q$ each attempt): we write $1000$ and… we’re back in the same situation (the “suffix” is still empty).
  • One of I,V,X,L,C,D (prob $q$ each attempt): we jump into the corresponding sub-1000 state with expectation $E$.

Let E0 be the expected final value from the empty state. On a decisive event (which again happens with prob r = p + 7q = 1, since all 7 letters are valid from empty), we have:

E0 = p*0 + q*(1000 + E0) + q*Σ E[c],   c∈{I,V,X,L,C,D}

Rearrange:

E0 - q*E0 = q*(1000 + Σ E[c])
E0 = q/(1 - q) * (1000 + Σ E[c])

Which is the print line:

print(f"{q/(1-q)*(1000+sum(E[r2n[c]] for c in 'IVXLCD')):.8f}")

That “solves away” the unbounded 'M' prefix in one line.

p, q = 0.02, 0.14
O = ("","I","II","III","IV","V","VI","VII","VIII","IX")
T = ("","X","XX","XXX","XL","L","LX","LXX","LXXX","XC")
H = ("","C","CC","CCC","CD","D","DC","DCC","DCCC","CM")

R = [H[i//100] + T[(i//10)%10] + O[i%10] for i in range(1000)]
r2n = {s:i for i,s in enumerate(R)}
succ = [[t for c in "IVXLCDM" if (t:=r2n.get(R[n]+c)) is not None] for n in range(1000)]

E = [0.0]*1000
for n in range(999,0,-1):
    k = len(succ[n])
    E[n] = n if not k else (p*n+q*sum(E[m] for m in succ[n]))/(p+q*k)

print(f"{q/(1-q)*(1000 + sum(E[r2n[c]] for c in 'IVXLCD')):.8f}")