Enigmatic Code

Programming Enigma Puzzles

Enigma 1228: Long run

From New Scientist #2384, 1st March 2003 [link]

The entrants for the marathon formed a long line. They were told to number themselves from 1 upwards using the large stock of sticky-backed digits. This went well until it got to me. My number was an even three-figure perfect square.

The next person added one to my number, collected up the appropriate digits, but then stuck them on his back in the wrong order. The next person added one to that incorrect three-figure number, collected up the appropriate digits, but then stuck them on his back in the wrong order. The next person added one to that incorrect three-figure number, collected up the appropriate digits, but then stuck them on his back in the wrong order, and so on, and so on, and so on. The funny thing was that every third runner after me had a number which was a perfect square.

I only realised that something was wrong when, during the race, I overtook a runner with the same number as mine.

What was that number?

[enigma1228]

Advertisements

2 responses to “Enigma 1228: Long run

  1. Jim Randell 4 June 2015 at 8:47 am

    This Python 3 program runs in 60ms.

    from itertools import permutations
    from collections import defaultdict
    from enigma import irange, flatten, printf
    
    # possibilities for the successor of n
    def successor(n):
      if not(n < 999): return # must be 3 digits
      s = str(n + 1)
      seen = { s: 1 } # ignore the correct successor
      for p in permutations(s):
        if p[0] == '0': continue # ignore leading zeros
        t = ''.join(p)
        if t in seen: continue # ignore duplicates
        yield int(t)
        seen[t] = 1
    
    # make chains of length n
    def chain(ss, n):
      if n == 0:
        yield ss
      else:
        for t in successor(ss[-1]):
          yield from chain(ss + [t], n - 1)
    
    # 3-digit squares
    squares = set(i * i for i in irange(10, 31))
    
    # find possible chains of length 4 beginning and ending with a square
    chains = list()
    for s in squares:
      for c in chain([s], 3):
        if c[-1] in squares:
          chains.append(c)
    
    # extend sequence <ss> using <chains> until it is extended with a
    # chain containing <n>
    def solve(n, ss, chains):
      for (i, c) in enumerate(chains):
        # does the chain extend the sequence?
        (c0, c1) = (c[0], c[1:])
        if c0 == ss[-1]:
          ss1 = ss + c1
          # is the number repeated in the sequence?
          if n in c1: yield ss1
          # solve for the remaining chains
          yield from solve(n, ss1, chains[:i] + chains[i + 1:])
    
    # look for solutions starting with an even square
    for n in squares:
      if n % 2 == 0:
        for ss in solve(n, [n], chains):
          printf("n={n} {ss}")
    

    Solution: The number was 256.

    The only possible sequences that start with an even 3-digit square, and then repeat that square later on are:

    256, (527), (258), 529, (305), (630), 361, (263), (624), 256
    256, (527), (258), 529, (305), (630), 361, (623), (264), 256
    256, (527), (258), 529, (350), (135), 361, (263), (624), 256
    256, (527), (258), 529, (350), (135), 361, (623), (264), 256
    256, (527), (258), 529, (350), (315), 361, (263), (624), 256
    256, (527), (258), 529, (350), (315), 361, (623), (264), 256

    The numbers in brackets are those that are not required to be squares, and, indeed, none of them are squares.

    In fact, none of the candidate chains of four numbers that both start and end with a square contain a square in the intermediate positions, so we can just consider transitions between squares. The graph of all such transitions between squares looks like this:

    Enigma 1228 - Graph

    Even squares are shown in red, as are transitions that form a cycle in the graph.

    We can see that the only path through the graph starting at an even square and including that square more than once is to start at 256 and go around the cycle of red arrows as many times as you like. It is possible to end the path by exiting the cycle and finishing on the edge to 625 with the last three runners to take numbers. (If there are a suitable number of runners involved (i.e. three, four or five remaining when we get to 361)). If we arrive at a node with only one or two runners remaining to allocate numbers to, we can exit that node without worrying that we need to subsequently allocate a square number.

  2. Brian Gladman 5 June 2015 at 11:53 am
    from itertools import permutations
    
    # find the set of numbers that could follow the number n
    def seq(n):
      # list the integers created by permuting the digits of n + 1
      t = set(int(''.join(p)) for p in permutations(str(n + 1)))
      # remove those that don't have 3 digits or are correct 
      return set(x for x in t if 100 <= x < 1000 and x != n + 1)
    
    # check if a number n is a perfect square
    def is_sqr(n):
      return int(n ** 0.5 + 0.5) ** 2 == n
    
    # find sequences of four numbers that start and end with squares
    s4 = set((s, t, u, v) for s in (x * x for x in range(10, 32)) 
           for t in seq(s) for u in seq(t) for v in seq(u) if is_sqr(v))
    
    # find sequences of 4-tuples that can form a chain starting
    # and ending with the same (even) square
    def solve(s):
      # is the chain complete
      if s[0][0] == s[-1][3]:
        yield (s[0][0],) + tuple(x for y in s for x in y[1:])  
      else:
        for t in s4:
          # extend the chain if possible
          if t[0] == s[-1][3] and t not in s:
            yield from solve(s + [t])
    
    # for all even starting squares
    for t in s4:
      if t[0] % 2 == 0:
        # find a chain starting and ending with this square
        for seq in solve([t]):
          print('Number = {} {}'.format(seq[0], seq))
    

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: