Enigmatic Code

Programming Enigma Puzzles

Enigma 186: Cereal numbers

From New Scientist #1331, 11th November 1982 [link]

No morning papers — hence a glassy rumination of my Honeyed Weety Fingees, contents and package both. Slowly, the significance of four crude over-printed stock numbers percolated my abstractions.

The numbers each had the same number of digits. The smallest plus the next-to smallest numbers summed to another of the numbers; the total was identical to the smallest number except that the order of the digits was exactly reversed. Adding the smallest number to the total just obtained produced a new total which was one of the two numerical palindromes featured in the group.

But for two exceptions, the digits 1 to 9 were all evident, but 0 was not. I noticed at least two digits which each appeared four times within the group, all other digits appeared just twice each.

What was the highest number within the group?

[enigma186]

Advertisements

2 responses to “Enigma 186: Cereal numbers

  1. Jim Randell 24 April 2014 at 7:38 am

    A bit of analysis narrows down the possible digit lengths of the numbers. This recursive Python program runs in 2.1s (under PyPy).

    from itertools import combinations, permutations
    from collections import Counter
    from enigma import irange, diff, printf
    
    # there are 7 digits used (chosen from 1 to 9), at least two of them
    # are used 4 times and the rest are used twice.
    #
    # 4s  2s  total  digits per number
    #  2   5     18  -
    #  3   4     20  5
    #  4   3     22  -
    #  5   2     24  6
    #  6   1     26  -
    #  7   0     28  7
    
    # suppose the numbers are A < B < C < D, then:
    # A + B = C = rev(A), so B = rev(A) - A
    # A + rev(A) = D
    # B and D are palindromes
    
    # both A and rev(A) are numbers on the list, so any digit used in A
    # cannot appear more than twice (otherwise that digit will appear more
    # than 4 times when all the numbers are considered).
    
    digits = '123456789'
    
    def solve(A):
      # is A an acceptable length?
      n = len(A)
      if n in (5, 6, 7):
        check(A, n)
      if n < 7:
        # extend A
        for d in digits:
          # but don't allow more than 2 repeated digits
          if A.count(d) < 2:
            solve(A + d)
    
    def check(A, n):
      a = int(A)
      # C is the reverse of A
      C = A[::-1]
      c = int(C)
      # B = C - A
      b = c - a
      if not(a < b): return
      B = str(b)
      # B is an n-digit number, not containing 0 and a palindrome
      if len(B) != n or '0' in B or B != B[::-1]: return
      # D = A + C
      d = a + c
      D = str(d)
      # D is an n-digit number, not containing 0 and a palindrome  
      if len(D) != n or '0' in D or D != D[::-1]: return
      # count the digits used in all the numbers
      ds = Counter(A + B + C + D).values()
      # 7 digits should be used altogether
      if len(ds) != 7: return
      # now count the counts
      ds = Counter(ds)
      # there should be more than one 4, and the rest should be 2
      if not(ds[4] > 1 and 2 * ds[4] + ds[2] == 2 * n): return
      printf("A={A} B={B} C={C} D={D}")
    
    solve('')
    

    Solution: The highest number of the group is 774477.

    The numbers (in order) are: 112266, 549945, 662211, 774477.

    If we accept that “all other digits appeared just twice” means that there is at least one digit that appears twice, then we can restrict the search to only examining 5 and 6 digit numbers. With this modification the program runs in 384ms.

  2. Brian Gladman 24 April 2014 at 10:56 pm
    # Since three digits are absent and there are two or four of each digit 
    # present; if x is the number of digits that occur four times there are
    # 14 + 2.x digits. Since this must be divisible by 4, x is odd and must
    # hence be 3 or 5. So the four numbers have either 5 or 6 digits.
    for nd in (5, 6):
      lo, hi = 10 ** (nd - 1), 10 ** nd
      # If the numbers are a, b, c and d, c = a + b = rev(a) shows
      # that b = rev(a) - a and d = rev(a) + a
      # The numbers are hence a, rev(a) - a, rev(a), rev(a) + a
      for a in range(lo, hi):
        # compute b, c and d
        sa = str(a)
        c = int(sa[::-1])
        b, d = c - a, c + a
        # b must be larger than a and d must be of the same length 
        if b > a and d < hi:
          sb, sd = str(b), str(d)
          # b and d must be palindromes
          if sb == sb[::-1] and sd == sd[::-1]:
            s = sa + sb + sa + sd
            # we must have seven different digits not including any zeros
            if '0' not in s and len(set(s)) == 7:
              # and each digit must occur either two or four times
              if all(s.count(x) in (2, 4) for x in set(s)):
                print(a, b, c, d)
    

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: