Enigmatic Code

Programming Enigma Puzzles

Enigma 1384: Power grid

From New Scientist #2544, 25th March 2006

Enigma 1384

I have drawn a grid of five rows of nine boxes and have placed in each box a digit so that each digit occurs its own number of times (e.g. 4 occurs four times). The digits in one row form a number which is a fourth power, and another row contains only two different digits and is divisible by 33. Two other rows between them contain all the digits and are both fifth powers.

In ascending order, what are the nine digits occupying the remaining row?

[enigma1384]

One response to “Enigma 1384: Power grid

  1. Jim Randell 12 October 2013 at 9:26 am

    This program looks for one arrangement of the number composed of only two different digits (as “anagrams” of this number won’t change the overall solution). It runs in 38ms.

    from collections import Counter
    from itertools import combinations
    from enigma import irange, intc, printf
    
    # there are 45 boxes and 45 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9,
    # so every digit is used in the solution.
    
    digits = Counter(dict((d, int(d)) for d in '0123456789'))
    
    # check the string provided doesn't exceed the digit count
    def check(s):
      return not any(v > digits[k] for (k, v) in Counter(s).items())
    
    # find nth powers with 9 digits that don't exceed the digit count
    def powers(n):
      ps = list()
      f = 1.0 / n
      for i in irange(intc(100000000 ** f), int(999999999 ** f)):
        s = str(i ** n)
        if check(s): ps.append(s)
      return ps
    
    # we need to find 4th and 5th powers with 9 digits
    p4s = powers(4)
    p5s = powers(5)
    
    # choose 2 of the 5th powers
    for (p5a, p5b) in combinations(p5s, 2):
      if not check(p5a + p5b): continue
      if not all(d in p5a + p5b for d in '123456789'): continue
      # choose the 4th powers
      for p4 in p4s:
        if not check(p4 + p5a + p5b): continue
        # what digits are left?
        ds = digits - Counter(p4 + p5a + p5b)
        # choose two of them
        for (d1, d2) in combinations(ds.keys(), 2):
          if ds[d1] + ds[d2] < 9: continue
          (d1, d2) = sorted((d1, d2), key=lambda x: ds[x])
          # decide how many of the lesser digit to use
          for n in irange(1, max(ds[d1], 9 - ds[d2])):
            # will the resulting number be divisible by 3?
            if (n * int(d1) + (9 - n) * int(d2)) % 3: continue
            # and the positions it will occur in
            for ps in combinations(irange(0, 8), n):
              # create the number
              n2 = ''.join((d1 if i in ps else d2) for i in irange(0, 8))
              # check the disibility
              if int(n2) % 33: continue
              # and what's left?
              r = ''.join(sorted((ds - Counter(n2)).elements()))
    
              printf("r={r} [p4={p4} p5a={p5a} p5b={p5b} n2={n2}]")
    
              # we don't need to find further possibilities for n2
              break
    

    Solution: The digits in the remaining row are: 3, 4, 5, 5, 8, 8, 8, 8, 8.

    There are, in fact, 30 possibilities for the number composed of only two different digits, but the 4th and 5th powers are unique.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: