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]

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)
```