Enigmatic Code
Programming Enigma Puzzles
Enigma 1439: Ring of powers
Posted by on 20 April 2013
From New Scientist #2600, 21st April 2007
I have made a number of cards, and have written on them all the nine-digit ninth powers, all the eight-digit eighth powers and so on down to the single-digit first powers. I have arranged these cards to form a ring so that each digit at the right-hand end of one card as seen from the inside of the ring matches that at the left-hand end of its neighbour, going clockwise.
What is the greatest number of digits I can have in the ring?
[enigma1439]
Enigmatic Code 
When this puzzle was originally published I solved it in Perl using an exhaustive search, but it took about 30 minutes to run.
Here’s the search recoded in Python, with a couple of modifications to reduce the run time. It finds a number of maximal length solutions in 2.0s (running under PyPy).
It might be faster to assemble the numbers into chains, and then assemble non-intersecting chains into a ring.
from enigma import irange, Accumulator, printf powers = set() for n in irange(1, 9): for i in irange(0, 9): p = str(i ** n) if len(p) == n: powers.add(p) printf("[powers = {s}]", s=', '.join(powers)) def solve(ring, n, ps, m, r): # give up if there aren't enough elements left if r.value and n + m < r.value: return # if the ring is valid accumulate it as a possible result if ring and ring[0][0] == ring[-1][-1]: r.accumulate_data(n, ring) if n == r.value: printf("[{r.value}: {s}]", s='/'.join(ring)) # try to extend the ring for p in ps: if ring and p[0] != ring[-1][-1]: continue solve(ring + [p], n + len(p), ps.difference([p]), m - len(p), r) # to reduce the number of solutions we start with the smallest element r = Accumulator(fn=max) for p in powers: ps = set(q for q in powers if p < q) solve([p], len(p), set(q for q in powers if p < q), sum(len(p) for p in ps), r) printf("max length = {r.value} [{s}]", s='/'.join(r.data))Solution: The maximum number of digits in the ring is 64.