# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1083: Trios of semi-primes

From New Scientist #2239, 20th May 2000 [link]

A semi-prime is the product of two prime numbers. Harry, Tom and I each chose a set of three two-digit semi-primes which formed an arithmetic progression, such that the six factors of the three semi-primes in any one set were all different. The first (lowest) number in each of our sets was identical.

We then each chose another such set. This time the middle number in each of our sets was identical.

We then each chose another such set. This time the last (highest) number in each of our sets was identical, and of the other two semi-primes in my set one also appeared in Harry’s set and the other also appeared in Tom’s set.

The nine sets that we chose between us were all different, but one semi-prime appeared in all three sets that I chose.

List the three sets that I chose in the order in which I chose them, with the numbers in each set in ascending order.

[enigma1083]

### 2 responses to “Enigma 1083: Trios of semi-primes”

1. Jim Randell 18 December 2017 at 8:24 am

It’s a bit fiddly to check all the necessary conditions, but at the end of it you can determine all of the sequences (although we can’t distinguish between Tom and Harry, so we don’t know who chose which of their possible sequences).

This Python program runs in 45ms.

Run: [ @repl.it ]

```from itertools import combinations
from collections import defaultdict
from enigma import irange, factor, diff, printf

# find 2-digit semiprimes with different factors
sps = list()
for n in irange(10, 99):
fs = factor(n)
if len(fs) == 2 and fs != fs:
sps.append(n)

# find 3 semiprimes in arithmetic progression with no shared factors
seqs = list()
for (a, b) in combinations(sps, 2):
c = b + b - a
if c in sps and len(set(factor(a * b * c))) == 6:
seqs.append((a, b, c))

# index the sequences by 1st, 2nd, 3rd element
(d0, d1, d2) = (defaultdict(list), defaultdict(list), defaultdict(list))
for s in seqs:
d0[s].append(s)
d1[s].append(s)
d2[s].append(s)

# consider sets that share the final element
for (k2, vs2) in d2.items():
if len(vs2) < 3: continue
# choose Dick's third set
for D2 in vs2:
# find sets which share the first value and second value
S0 = list(v for v in vs2 if v != D2 and D2 in v)
S1 = list(v for v in vs2 if v != D2 and D2 in v)
if not(S0 and S1): continue

# consider sets that share the middle element
for (k1, vs1) in d1.items():
if len(vs1) < 3: continue
# choose Dick's second set
for D1 in vs1:
# common numbers in D1 and D2
n12 = set(D2).intersection(D1)
if not(n12): continue

# finally consider sets that share the first element
for (k0, vs0) in d0.items():
if len(vs0) < 3: continue
# choose Dick's first set
for D0 in vs0:
# must be a shared number with D1 and D2
n = n12.intersection(D0)
if not(n): continue

printf("1st: D={D0}, H/T={HT}", HT=diff(vs0, [D0]))
printf("2nd: D={D1}, H/T={HT}", HT=diff(vs1, [D1]))
printf("3rd: D={D2}, H/T={S0} / {S1}")
printf()
```

Solution: Dick’s sequences are: 1st (77, 86, 95); 2nd (21, 58, 95); 3rd (91, 93, 95).

Dick’s first sequence of numbers was 77 (7 × 11), 86 (2 × 43), 95 (5 × 19), with a common difference of 9.
Harry and Tom’s first sequences were: 77 (7 × 11), 82 (2 × 41), 87 (3 × 29), with a common difference of 5; and 77 (7 × 11), 85 (5 × 17), 93 (3 × 31) with a common difference of 8.

Dick’s second sequence was: 21 (3 × 7), 58 (2 × 29), 95 (5 × 19), with a common difference of 37.
Harry and Tom’s second sequences were: 39 (3 × 13), 58 (2 × 29), 77 (7 × 11), with a common difference of 19; and 51 (3 × 17), 58 (2 × 29), 65 (5 × 13), with a common difference of 7.
All of these sequences have 58 in the middle.

Dick’s third sequence was: 91 (7 × 13), 93 (3 × 31), 95 (5 × 19), with a common difference of 2.
Harry and Tom’s third sequences were: 87 (3 × 29), 91 (7 × 13), 95 (5 × 19), with a common difference of 4; 93 (3 × 31), 94 (2 × 47), 95 (5 × 19), with a common difference of 1.
All of these sequences end with 95, and the first and second elements of Dick’s sequence (91 and 93) appear in Harry and Tom’s sequences.

Each of Dick’s sequences ends with the number 95.

2. Brian Gladman 18 December 2017 at 3:56 pm
```from itertools import combinations, permutations
from collections import defaultdict

# create the set of primes below 50
pr = {2, 3, 5, 7}
pr |= {x for x in range(11, 50, 2) if all(x % p for p in pr)}

# create a map from two digit semi-primes to their prime factors
sp = {x * y:{x, y} for x, y in combinations(pr, 2) if 9 < x * y < 100}

# now collect semiprime triples that are in arithmetic progression and
# collect them based on their common first, second and third values
s1, s2, s3 = ld = [defaultdict(list) for i in range(3)]
for t in combinations(sorted(sp.keys()), 3):
a, b, c = t
if 2 * b == a + c and len(sp[a] | sp[b] | sp[c]) == 6:
for i in range(3):
ld[i][t[i]].append(t)

# select the third set of triples for Tom, Dick and Harry
for i in s3.keys():
for t3, d3, h3 in permutations(s3[i], 3):
# one of Dick's two lowest numbers is shared with Tom
# and the other is shared with Harry
if d3 in t3 and d3 in h3:
# now select the second set of triples for Tom, Dick and Harry
for j in s2:
for t2, d2, h2 in permutations(s2[j], 3):
# Dick's second and third triples share a common number
cv = set(d3).intersection(d2)
if len(cv) >= 1:
# now select the first set of triples for Tom, Dick and Harry
for k in s1:
for t1, d1, h1 in permutations(s1[k], 3):
# Dick's first triple shares a common number with
# his second and third triples
if cv & set(d3).intersection(d1):
# the nine triples are all different
if len(set((t1, t2, t3, d1, d2, d3, h1, h2, h3))) == 9:
print(f"Dick's: {d1}, {d2} and {d3}"
f" (Tom's: {[t1, t2, t3]}, Harry's: {[h1, h2, h3]}).")
```

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