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]

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:

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))
```