Teaser 3105: Roman primes
From The Sunday Times, 27th March 2022 [link] [link]
Romulus played a game using several identical six-sided dice. Each die face shows a different single-character Roman numeral. He rolled two dice and was able to form a prime number in Roman numerals by arranging the two characters. Romulus rolled more dice and, after each roll, formed a prime number with one more character, rearranging the sequence as needed, until he could no longer form a prime number less than 100. He was using standard notation where a character before another that is 5 or 10 times larger is subtracted from the larger one, e.g., IX = 9.
After playing many games he realised that there were exactly three primes less than 100 that could not occur in any of the sequences.
In decimal notation and in ascending order, what were those prime numbers?
I found two different scenarios that fit the puzzle text, but lead to two different answers. So I have marked the puzzle as flawed.
[teaser3105]
Hugh+Casement, and 
Robert Brown are discussing. 
GeoffR and 
Frits and 
Alex.T.Sutherland, and 1 other are discussing. 
S2T2 
Jim Randell 5:28 pm on 25 March 2022 Permalink |
To represent numbers from 1 to 99 using Roman numerals requires five characters I, V, X, L, C. So we know those must be on the dice. The other symbol is probably D (= 500), which lets us express numbers up to 899 (with sufficient dice; it takes 12 to make 888 = DCCCLXXXVIII).
I’m assuming that Romulus rolls 2 dice, arranges them to make the first prime in the sequence. Then rolls another single die, and arranges the 3 dice (without changing the numerals shown by the first two) to make the second prime, and so on. Rolling a single new die at each step until he is unable to rearrange the dice to make a prime, or he runs out of dice.
Then we can find a scenario where there are three primes that cannot occur in any sequence.
This Python program runs in 51ms.
Run: [ @replit ]
from enigma import (primes, int2roman, group, join, multiset, printf) # primes less than 100 prms = list(primes.between(2, 99)) # record primes by their roman numeral content d = group(prms, by=(lambda n: join(sorted(int2roman(n))))) # find length n extensions of ks in d def extend(d, ks, n): ss = list(multiset.from_seq(k) for k in ks) for k in d.keys(): if len(k) == n: s = multiset.from_seq(k) if any(s.issuperset(s_) for s_ in ss): yield k # generate possible throws with increasing lengths def generate(d, n=2): # start with length n sequences ks = list(k for k in d.keys() if len(k) == n) while ks: yield (n, ks) # find keys that are one longer n += 1 ks = list(extend(d, ks, n)) # start with the complete set of primes ps = set(prms) for (n, ks) in generate(d, 2): # and remove those reachable after n dice for k in ks: ps.difference_update(d[k]) # we have a solution if there are 3 primes remaining if len(ps) == 3: printf("{n} dice -> {ps}", ps=sorted(ps))Solution: The prime numbers are: 5, 37, 83.
This is the solution in the scenario where Romulus has 6 dice, with the symbols I, V, X, L, C, and one other.
5 (= V) only requires 1 die, so cannot be constructed using 2-6 dice.
83 (= LXXXIII) requires 7 dice, so cannot be constructed using 2-6 dice.
37 (= XXXVII) can be constructed using 6 dice, but there is no predecessor prime using 5 dice.
Possible predecessor numbers for 37 are: 27, 32, 34, 46. None of which are prime.
However I was able to find another scenario (see below), where Romulus has more than 6 dice, with the symbols I, V, X, L, and two others, that do not include C.
In this scenario 5 and 37 cannot be constructed (as above), but 83 can be constructed using 7 dice.
However the standard representation of 97 in Roman numerals is XCVII, which cannot be constructed if the symbol C is not available. (In fact none of the numbers in [90, 499] can be constructed with these dice).
So the solution in this scenario is: 5, 37, 97.
It seems that this second scenario is what the setter had in mind (it is the published answer), although it seems less plausible to me.
Perhaps the following would have been a better representation of the intended puzzle:
The published solution is: “5, 37 and 97”.
LikeLike
Robert Brown 7:39 am on 26 March 2022 Permalink |
When the text says ‘after many games’ I assumed that some of these would start with II (=2) and some with XI (=11). Clearly cannot find 5 (V) as it is length 1, but I only have one more prime which cannot be made with one of the two starting pairs.
LikeLike
Jim Randell 8:57 am on 26 March 2022 Permalink |
@Robert: It looks like you are 2/3 of the way to the answer.
There is a scenario that satisfies the wording of the puzzle text, and there are three primes that are not constructible. And each of the three primes is non-constructible for a different reason.
LikeLike
Jim Randell 12:51 pm on 26 March 2022 Permalink |
I think there is potentially an alternative scenario that also gives three non-constructible primes:
If the dice have the symbols I, V, X, L, D, M on them (so not C), then one of the primes is not constructible (using “standard” Roman numerals), no matter how many dice are used.
We can modify the program for this scenario by only considering primes that don’t include C when constructing the dictionary
d:Or here is a version of my code that tries all possible combinations of 6 of the 7 symbols I, V, X, L, C, D, M for the dice [ @replit ], it finds three possibilities corresponding to the two scenarios outlined above.
from enigma import (primes, int2roman, group, join, multiset, subsets, printf) # primes less than 100 prms = list(primes.between(2, 99)) # find length n extensions of ks in d def extend(d, ks, n): ss = list(multiset.from_seq(k) for k in ks) for k in d.keys(): if len(k) == n: s = multiset.from_seq(k) if any(s.issuperset(s_) for s_ in ss): yield k def generate(d, n=2): # start with length n sequences ks = list(k for k in d.keys() if len(k) == n) while ks: yield (n, ks) # find keys that are one longer n += 1 ks = list(extend(d, ks, n)) # solve the puzzle for allowable symbols def solve(symbols): # record primes their roman numeral content d = group(prms, by=(lambda n: join(sorted(int2roman(n))))) # remove keys with invalid symbols d = dict((k, v) for (k, v) in d.items() if symbols.issuperset(k)) # start with the complete set of primes ps = set(prms) for (n, ks) in generate(d, 2): # remove those reachable after n dice for k in ks: ps.difference_update(d[k]) # we have a solution if there are 3 primes remaining if len(ps) == 3: printf("{syms}: {n} dice -> {ps}", syms=join(sorted(symbols)), ps=sorted(ps)) # choose 6 symbols for the dice for syms in subsets('IVXLCDM', size=6, fn=set): solve(syms)I think I prefer the original scenario given above, where a sufficient number of dice can be used to give the numbers from 1 to 899. A set of dice without C would only be able to go consecutively up to 89 (the next smallest constructible number would be 500). D and M don’t come into play until 400 and 900 respectively.
LikeLike
Jim Randell 9:58 am on 1 April 2022 Permalink |
Depending on the shape of the glyphs used on the dice, it may be possible to use a V on its side to represent C, which would leave only 2 primes non-constructible in this second scenario (unless the number of dice is limited – and then we get the same solution as my first scenario).
LikeLike
Hugh+Casement 1:21 pm on 26 March 2022 Permalink |
I came to the same conclusion as Robert. I feel the setter of this puzzle has played a trick on us, but Jim rumbled it (before he came up with the alternative scenario ). It would have been neater, to my mind, if the puzzle text had stated that there were just two primes less than 100 that could not occur.
LikeLike
Jim Randell 3:58 pm on 26 March 2022 Permalink |
There’s definitely some trickery going on, as what you might expect to be the normal interpretation does not give 3 non-constructible primes.
We would need to have more information about the symbols or number of dice to work out which scenario the setter had in mind.
LikeLike