Enigmatic Code

Programming Enigma Puzzles

Enigma 1326: Roman squares

From New Scientist #2485, 5th February 2005

Harry and Tom each chose two consecutive integers between 1 and 20 and wrote down their squares as Roman numerals. I challenged each of them independently to replace each letter of his Roman numerals with a digit (with any given letter always replaced by the same digit, different letters by different digits and leading zeroes not permitted) in such a way that the numbers they created from their Roman squares were themselves consecutive perfect squares.

I leave you to discover the connections between their solutions, but will add that from their ascending Roman squares Harry created descending consecutive numerical squares and Tom created ascending consecutive numerical squares. Submit both the two Roman squares and the two numerical squares created from them that (a) Harry and (b) Tom came up with.

[enigma1326]

Advertisements

One response to “Enigma 1326: Roman squares

  1. Jim Randell 8 May 2014 at 7:23 am

    This was a bit more involved than I was expecting. This Python program uses the int2roman() routine from the enigma.py library. It runs in 81ms.

    from itertools import count, product
    from collections import defaultdict
    from enigma import irange, int2roman, printf
    
    # single digits
    digits = set(irange(0, 9))
    
    # make roman numeral squares and find the max length
    romans = dict()
    m = 0
    for i in irange(1, 20):
      r = int2roman(i * i)
      romans[i] = r
      m = max(m, len(r))
      printf("[{i} => {r}]")
    
    # find squares up to m digits (as strings)
    squares = defaultdict(list)
    root = dict()
    for i in count(0):
      s = str(i * i)
      n = len(s)
      if n > m: break
      squares[n].append(s)
      root[s] = i
    
    # consistenly update a map with some (k, v) pairs
    def update(d, ps):
      for (k, v) in ps:
        if k in d:
          if d[k] != v:
            return None
        elif v in d.values():
          return None
        else:
          d[k] = v
      return d
    
    # for each roman numeral find valid mappings
    i2d = defaultdict(list)
    for (i, r) in romans.items():
      # find matching squares
      for s in squares[len(r)]:
        d = update(dict(), zip(r, s))
        if d: i2d[i].append(d)
    
    # now find consecutive numbers with compatible mappings
    for (i1, ds1) in i2d.items():
      i2 = i1 + 1
      if i2 not in i2d: continue
      ds2 = i2d[i2]
    
      # find consistent combined maps
      for (d1, d2) in product(ds1, ds2):
        d = update(dict(d1), d2.items())
        if d is None: continue
    
        # make the roman to digit substitution
        (r1, r2) = (romans[i] for i in (i1, i2))
        (s1, s2) = (''.join(d[x] for x in i) for i in (r1, r2))
        (n1, n2) = (root[i] for i in (s1, s2))
    
        # find consective squares after substitution
        if n1 - n2 == +1:
          printf("H: {i1}, {i2} => {r1}, {r2} => {s1}, {s2} ({n1}, {n2})")
        elif n1 - n2 == -1:
          printf("T: {i1}, {i2} => {r1}, {r2} => {s1}, {s2} ({n1}, {n2})")
    

    Solution: (a) Harry’s Roman squares were XVI and XXV (16 = 4² and 25 = 5²), the corresponding numerical squares are 256 and 225 (16² and 15²). (b) Tom’s Roman squares were CCXXV and CCLVI (225 = 15² and 256 = 16²), the corresponding numerical squares are 99225 and 99856 (315² and 316²).

    The connection between them is that the consecutive numbers whose squares give Harry’s pair of numerical squares are the same numbers that Tom chose at the beginning.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: