Project Euler

Roman Numerals II

Count valid representations in a modified Roman numeral system.

Source sync Apr 19, 2026

Problem #0610

Level Level 18

Solved By 732

Languages C++, Python

Answer 319.30207833

Length 108 words

brute_forcedynamic_programmingsearch

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

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.

Problem 610: Roman Numerals II

Mathematical Analysis

Dynamic programming on the structure of Roman numeral representations.

Derivation

The solution follows from the mathematical analysis above.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

Time: See implementation.
Space: See implementation.

Answer

\boxed{319.30207833}

C++ project_euler/problem_610/solution.cpp

#include <bits/stdc++.h>
using namespace std;

string int_to_roman(int n) {
    int vals[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
    string syms[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
    string result;
    for (int i = 0; i < 13; i++)
        while (n >= vals[i]) { result += syms[i]; n -= vals[i]; }
    return result;
}

int main() {
    int max_len = 0;
    for (int n = 1; n < 4000; n++) {
        int len = int_to_roman(n).size();
        max_len = max(max_len, len);
    }
    cout << "Max Roman numeral length: " << max_len << endl;
    return 0;
}

Python project_euler/problem_610/solution.py

"""
Problem 610: Roman Numerals II
Count valid representations in modified Roman numeral system.
"""

def roman_to_int(s):
    """Convert Roman numeral string to integer."""
    values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    for i in range(len(s)):
        if i + 1 < len(s) and values[s[i]] < values[s[i+1]]:
            total -= values[s[i]]
        else:
            total += values[s[i]]
    return total

def int_to_roman(n):
    """Convert integer to standard Roman numeral."""
    vals = [(1000,'M'),(900,'CM'),(500,'D'),(400,'CD'),
            (100,'C'),(90,'XC'),(50,'L'),(40,'XL'),
            (10,'X'),(9,'IX'),(5,'V'),(4,'IV'),(1,'I')]
    result = ''
    for val, sym in vals:
        while n >= val:
            result += sym
            n -= val
    return result

# Verify
assert roman_to_int("XIV") == 14
assert roman_to_int("MCMXCIV") == 1994
assert int_to_roman(1994) == "MCMXCIV"

# Count lengths of Roman numerals
lengths = {}
for n in range(1, 4000):
    r = int_to_roman(n)
    lengths[n] = len(r)

print(f"Longest Roman numeral under 4000: {max(lengths.values())} chars")
longest_n = max(lengths, key=lengths.get)
print(f"  Number: {longest_n} = {int_to_roman(longest_n)}")