Problem 610
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Problem 610
Are "CMD" and "MCD" both minimal, valid representations of 1400? Is only "MCD" valid?
I couldn't find anything disallowing something like "CMD" in the About page: https://projecteuler.net/about=roman_numerals.
I couldn't find anything disallowing something like "CMD" in the About page: https://projecteuler.net/about=roman_numerals.

 Posts: 74
 Joined: Thu Nov 03, 2016 4:32 pm
Re: Problem 610
CMD is invalid representantion of a roman numeral.

 Posts: 74
 Joined: Thu Nov 03, 2016 4:32 pm
Re: Problem 610
To write a roman numeral you do so by using 'greedy' algorithm.
Let's say we want to express number 1400 as a roman numeral. With our greedy algorithm we will write it like this:
MCD > 1000 + 400
If we check your example:
CMD > 900 + 500
In the first step we did not use our best option, with CM we only add 900 to our number and not the maximum value 1000 posible using M.
I hope this helps.
Let's say we want to express number 1400 as a roman numeral. With our greedy algorithm we will write it like this:
MCD > 1000 + 400
If we check your example:
CMD > 900 + 500
In the first step we did not use our best option, with CM we only add 900 to our number and not the maximum value 1000 posible using M.
I hope this helps.
Re: Problem 610
Yes, Thank you.
This was the method I considered in my solution. Still couldn't get the right answer though
This was the method I considered in my solution. Still couldn't get the right answer though

 Posts: 495
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: Problem 610
What is the right way to write 14903 in Roman Numeral?
Is it "MMMMMMMMMMMMMMCMIII"???
Is it "MMMMMMMMMMMMMMCMIII"???
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

 Posts: 495
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: Problem 610
Thank you Hot_Sauce.
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
Re: Problem 610
The trouble is, neither the problem nor "About... Roman Numerals" mention a greedy algorithm. I agree that CMD is not a minimal representation of 1400 (I'd say it wasn't a valid representation at all), but that comes from external experience. Excluding it needs a bit of reading between the lines.LilStalker wrote: ↑Sun Sep 24, 2017 1:16 pm To write a roman numeral you do so by using 'greedy' algorithm.
For problem 610, we've got a string of symbols, and we want to know if it is a minimal form. We start with CMD and ask which of the seven rules it violates. The only violation of the first rule is the M following C, but that's allowed for subtraction. We don't have enough smaller denominations to make up M, C, or X. D is only there once. C is used as the leading numeral in a subtractive pair, and it's before M. X and I don't appear, so the rules involving them don't apply.
No rules are broken (if the first is modified as subtraction requires), so surely CMD is a valid representation. And it's minimal, as there is no shorter representation of the same number.
The intended definition of minimality appears to be that a representation is minimal if and only if it is the result of applying the first set of rules to some number, followed by the second set, in two separate steps. If CMD was valid, it would have the value 1400. By the first three rules, that can only be written as MCCCC. Then we apply subtraction. We don't have enough Ms or Ds to do anything, but we can replace CCCC with CD giving MCD. This is not CMD, so CMD is not minimal.
(There's another rule that this example doesn't use: no symbol except M can appear five times. IIIII must be replaced with V, and so on.
This is a consequence of wanting to make a shorter representation).
I think a lot of people's confusion is because this definition is only implied. The rules as stated can be read as contradicting it. It only works if you read them not as conditions to be tested, but as an indirect way of specifying a process. The way it's written sort of implies that, but it's not very clear.
Re: Problem 610
Forgive me if I've misunderstood the About page (I also relied on external information about Roman numerals rather than just this page), but is the interpretation of this rule when subtraction is included not to treat 'CM' as a lower denomination than 'M', and so 'CM' plus 'D' are being used to exceed 'M'? In the same way that we treat 'IX' as one number (9) to decide (using the first rule) that 19 is not IXX but XIX.
 RobertStanforth
 Administrator
 Posts: 1690
 Joined: Mon Dec 30, 2013 11:25 pm
Re: Problem 610
'CM' is indeed considered a lower denomination than 'M', which is how 'CMD' is excluded by the second rule in the About page.
Using a symbol (other than 'M') five times will also violate that rule as it will equal or exceed the next greater symbol.
Using a symbol (other than 'M') five times will also violate that rule as it will equal or exceed the next greater symbol.
Re: Problem 610
That's what I was missing. I wasn't clear what a 'denomination' was.RobertStanforth wrote: ↑Wed Sep 27, 2017 7:12 pm 'CM' is indeed considered a lower denomination than 'M'
Re: Problem 610
What happens if the symbol "#" is selected as the first one? It passes the "what we have written down must always (when nonempty) be a valid Roman numeral representation in minimal form" rule by virtue of being empty, but I am not sure an empty string should indeed be accepted (it would probably map to 0 if accepted)?
Thanks for the clarification.
Thanks for the clarification.
Re: Problem 610
Please read on to the last paragraph:
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.
Re: Problem 610
What does "minimal form" mean?(there is no definition on problem page or on "About... Roman Numerals" page) Does every positive integer number has exactly one "valid Roman numeral representation in minimal form"?
Re: Problem 610
From the "About...Roman Numerals" page:
Which means that IL would be considered to be an invalid way of writing fortynine, and whereas XXXXIIIIIIIII, XXXXVIIII, XXXXIX, XLIIIIIIIII, XLVIIII, and XLIX are all quite legitimate, the latter is the preferred (minimal) form.
XLIX is the minimal form of 49.The minimal form is the valid form that requires the least number of characters.
(You can read that too in the wording of Problem 89 (View Problem)
Re: Problem 610
Hello. I solved 610 last night, and DJohn's post was helpful in formulating my solution.
To be clear, in answering the problem, CMD is indeed considered invalid, as well as many of the other examples in the thread for problem 89. However, I'm not sure that this is definitively ruled out by the About Roman Numerals page.
However, if we interpret CMD as C(MD), then C(MD)=(1000+500)100=1400 and as D does not exceed M, MD is valid so that the second rule is not broken by this. Since C appears before M, rule iv. is fine as well. (Arguably though, C appears before MD in this interpretation.) Thus, interpreted in this way CMD does not appear to break any of the rules.
Given that problem 89 appeared over 14 years ago, I'm not suggesting any alterations to either problem formulation or the About page, but it seems that DJohn's sequential procedure or the greedy algorithm is needed to definitively define the minimal representation. I provide another interpretation in the solution forum, but I don't want to mention it here as it could provide hints on how to solve this problem.
To be clear, in answering the problem, CMD is indeed considered invalid, as well as many of the other examples in the thread for problem 89. However, I'm not sure that this is definitively ruled out by the About Roman Numerals page.
This implies that since CM=900 and D=500, CM+D>M, which is correctly ruled out by the second rule.RobertStanforth wrote: ↑Wed Sep 27, 2017 7:12 pm 'CM' is indeed considered a lower denomination than 'M', which is how 'CMD' is excluded by the second rule in the About page.
However, if we interpret CMD as C(MD), then C(MD)=(1000+500)100=1400 and as D does not exceed M, MD is valid so that the second rule is not broken by this. Since C appears before M, rule iv. is fine as well. (Arguably though, C appears before MD in this interpretation.) Thus, interpreted in this way CMD does not appear to break any of the rules.
Given that problem 89 appeared over 14 years ago, I'm not suggesting any alterations to either problem formulation or the About page, but it seems that DJohn's sequential procedure or the greedy algorithm is needed to definitively define the minimal representation. I provide another interpretation in the solution forum, but I don't want to mention it here as it could provide hints on how to solve this problem.
level = lambda number_solved: number_solved // 25
Re: Problem 610
The question states
but doesn't explain how to get negative integers, and I got the tick with an answer which assumes that negative integers don't have a valid representation. I think that the question should be edited to say either "all positive integers" or "all nonnegative integers".The rules do not place any restriction on the number of occurrences of M, so all integers have a valid representation.
 RobertStanforth
 Administrator
 Posts: 1690
 Joined: Mon Dec 30, 2013 11:25 pm
Re: Problem 610
Thank you for flagging this  you are correct. I have corrected the wording to "all positive integers".pjt33 wrote: ↑Tue Feb 11, 2020 9:18 pm The question statesbut doesn't explain how to get negative integers, and I got the tick with an answer which assumes that negative integers don't have a valid representation. I think that the question should be edited to say either "all positive integers" or "all nonnegative integers".The rules do not place any restriction on the number of occurrences of M, so all integers have a valid representation.