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]

Advertisements

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:
          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.

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: