# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1687: Predictive powers

From New Scientist #2854, 3rd March 2012 [link]

On my mobile phone the buttons can be used for more than one letter, and the machine predicts your intended word. So, for example, to text “STOP” I type the buttons shown below, but the machine could also interpret that as “SUMS”.

This desire for compact gadgetry has spread to calculators. The digits of mine are on just five buttons, A to E, as shown below. So when I type in a number the machine has to predict what I want. Recently I pushed buttons intending to display a three-figure prime number, but the machine displayed a different three-figure prime. Then I pushed some more buttons intending to display a three-figure square, but the machine displayed a different three-figure square. When typing these two numbers I had pushed each button at least once.

Which six buttons, listed in order, did I push?

[enigma1687]

### 2 responses to “Enigma 1687: Predictive powers”

1. Jim Randell 29 February 2012 at 9:51 pm

The following Python code runs in 45ms.

```from collections import defaultdict
from enigma import is_prime, printf

# map numbers to buttons
button = {
'0': 'A', '1': 'A', '2': 'B', '3': 'B', '4': 'C',
'5': 'C', '6': 'D', '7': 'D', '8': 'E', '9': 'E'
}

# collect 3-digit primes by code
p = defaultdict(list)
for n in range(101, 1001, 2):
if not is_prime(n): continue
keys = ''.join(button[i] for i in list(str(n)))
p[keys].append(n)

# collect 3-digit squares by code
s = defaultdict(list)
for i in range(10, 32):
n = pow(i, 2)
keys = ''.join(button[i] for i in list(str(n)))
s[keys].append(n)

# look for multiple squares with the same code
for sk, sv in s.items():
if len(sv) < 2: continue
# look for primes with the remaining letters
letters = set(list('ABCDE')).difference(list(sk))
for (pk, pv) in p.items():
if len(pv) < 2: continue
if not letters.issubset(set(list(pk))): continue
printf("prime={pk} {pv}, square={sk} {sv}")
```

Solution: The buttons pushed are: D, A, E, B, B, C.

2. Brian Gladman 3 March 2012 at 10:02 am

Here is an alternative version:

```from itertools import product
from collections import defaultdict

# create a dictionary of primes
def prime_dict(n) :
sieve = [False, False] + [True] * (n - 1)
for i in range(2, int(n ** 0.5) + 1):
if sieve[i] :
m = n // i - i
sieve[i * i : n + 1 : i] = [False] * (m + 1)
return dict((i, 1) for i in range(n + 1) if sieve[i])

pr = prime_dict(1000)

# create a dictionary of squares
sq = dict((x ** 2, x) for x in range(10, 32))

# compute possible primes and squares for each sequence
# of 3 key presses and put them in dictionaries indexed
# on the key sequence (dp for primes, dq for squares)
dp, dq = defaultdict(list), defaultdict(list)
for k in product(range(5), repeat=3):
# each sequence must have at least two different keys
if len(set(k)) > 1:
# now look at all the combinations of the two
# possible interpretations of each key to
# find 3 digit primes and squares
rk = (range(2 * i, 2 * i + 2) for i in k)
for k1, k2, k3 in product(*rk):
n = 10 * (10 * k1 + k2) + k3
if 100 <= n < 1000:
if n in pr:
dp[k] += [n]
if n in sq:
dq[k] += [n]

for p in dp:
# for each key sequence that gives two or more primes
if len(dp[p]) > 1:
for q in dq:
# for each key sequence that gives two or more squares
if len(dq[q]) > 1:
# if all keys are used at least once
if len(set(p) | set(q)) >= 5:
print(tuple(chr(ord('A') + x) for x in (p + q)))
```