# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1439: Ring of powers

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]

### One response to “Enigma 1439: Ring of powers”

1. Jim Randell 20 April 2013 at 9:12 am

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:

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.