20

2

# Background

This challenge is inspired by this website, which published the following diagram:

This diagram shows us that the longest Roman Numeral expression under 250 is that of 188, which requires 9 numerals to express.

# Challenge

The standard symbols used to express most Roman Numerals are the following: {`I`

, `V`

, `X`

, `L`

, `C`

, `D`

, `M`

}, where the characters' numeric values are `M`

=1000, `D`

=500, `C`

=100, `L`

=50, `X`

=10, `V`

=5, `I`

=1.

In this challenge, your goal is to, given an positive integer *n*, compute the number of valid Roman Numeral representations that can be composed through concatenating *n* of the standard symbols.

Then, your program must output the result of this computation!

**Input**: A positive integer *n*.

**Output**: The number of valid roman numeral expressions of length *n*.

# Rules for Roman Numeral Expressions

Roman Numerals originally only had "additive" pairing, meaning that numerals were always written in descending order, and the sum of the values of all the numerals was the value of the number.

Later on, subtractive pairing, the use of placing a smaller numeral in front of a larger in order to subtract the smaller from the larger, became commonplace to shorten Roman Numeral expressions. Subtractive pairs cannot be chained, like in the following invalid expression: `IXL`

.

The following are the modern day rules for additive and subtractive pairing.

- Only one I, X, and C can be used as the leading numeral in part of a subtractive pair.
- I can only be placed before V or X in a subtractive pair.
- X can only be placed before L or C in a subtractive pair.
- C can only be placed before D or M in a subtractive pair.
- Other than subtractive pairs, numerals must be in descending order (meaning that if you drop the leading numeral of each subtractive pair, then the numerals will be in descending order).
- M, C, and X cannot be equalled or exceeded by smaller denominations.
- D, L, and V can each only appear once.
- Only M can be repeated 4 or more times.

# Further Notes

We will not be using the

*bar*notation; rather, we will simply add more*M*s to express any number.These are the

**only**rules that we will follow for our roman numerals. That means that odd expressions, such as`IVI`

, will also be considered valid in our system.Also remember that we are not counting the number of numbers that have expressions of length

*n*, since some numbers have multiple expressions. Instead, we are solely counting the number of valid expressions.

# Test Cases

`1`

→ `7`

`2`

→ `31`

`3`

→ `105`

I checked the above by hand, so please make sure to double check the test cases, and add more if you can!

# Winning Criteria

This is a code-golf challenge, so have fun! I will only accept solutions that can handle at least inputs from 1 through 9. Any more is bonus!

# Edit

As requested by commenters, find below, or at this pastebin link, the 105 combos I counted for *n*=3

III IVI IXI IXV IXX VII XII XIV XIX XVI XXI XXV XXX XLI XLV XLX XCI XCV XCX XCL XCC LII LIV LIX LVI LXI LXV LXX CII CIV CIX CVI CXI CXV CXX CXL CXC CLI CLV CLX CCI CCV CCX CCL CCC CDI CDV CDX CDL CDC CMI CMV CMX CML CMC CMD CMM DII DIV DIX DVI DXI DXV DXX DXL DXC DLI DLV DLX DCI DCV DCX DCL DCC MII MIV MIX MVI MXI MXV MXX MXL MXC MLI MLV MLX MCI MCV MCX MCL MCC MCD MCM MDI MDV MDX MDL MDC MMI MMV MMX MML MMC MMD MMM

# Edit 2:

Use the following non-golfed code, as courtesy of Jonathan Allan to check your results.

# Edit 3:

I apologize for all of the errors in this challenge. I'll make sure to do a better job next time!

Comments are not for extended discussion; this conversation has been moved to chat.

– Mego – 2018-08-11T00:20:56.260