New Scientist Enigma 987 – Two Halves Make a Whole

by Richard England

From New Scientist #2142, 11th July 1998

A semi-prime is the product of two prime numbers; the square of a prime counts as a semi-prime.

Harry, Tom and I were trying to find pairs of 2-digit semi-primes such that if we added the two semi-primes together we formed a 2-digit prime. We each found three such pairs; the 18 semi-primes we used and the 9 primes that were formed were all different.

Harry’s three odd semi-primes were all greater than 50; Tom’s three even semi-primes were all greater than 50.

What were my three pairs of semi-primes?

One Comment Leave one →

Brian Gladman permalink

First use of Python 3.8’s assignment expressions!


from itertools import combinations, combinations_with_replacement as cwr
from collections import defaultdict

# the set of one and two digit primes
prms1 = {2, 3, 5, 7}
prms2 = set(x for x in range(11, 100, 2) if all(x % p for p in prms1))

# tuple of two digit semi-primes (using a Python 3.8 assignmemt expression!)
sp = sorted(t for x, y in cwr(prms1| prms2, 2) if 10 <= (t:= x * y) < 100)

# map two digit semi-primes (h > 50) to sets of semi-primes (l < 50)
# that sum with them to give two digit primes
map_h2l = defaultdict(set)
for l, h in combinations(sp, 2):
  if l + h in prms2:
    map_h2l[h].add(l)

# the sets of higher semi-primes for Harry (odd) and Tom (even)
hh = set(h for h in map_h2l.keys() if h > 50 and (h & 1))
th = set(h for h in map_h2l.keys() if h > 50 and not (h & 1))

# generate triples of different semi-prime pairs from the map (mh2l)
def solve(mh2l, usp=set(), tsp=()):
  if len(tsp) == 3:
    # return triples of semi-prime pairs and 
    # the semi-prime set used so far
    yield tsp, usp
  else:
    # try unused high values
    for h in mh2l.difference(usp):
      # order semi-prime pairs to avoid duplicate solutions
      if not tsp or h > tsp[-1][0]:
        # try unused low values
        for l in map_h2l[h].difference(usp):
          yield from solve(mh2l, usp.union((h, l)), tsp + ((h, l),))

# consider high values for Harry
for h, sh in solve(hh):
  # form Harry's primes
  hp3 = set(x + y for x, y in h)
  
  # consider high values for Tom
  for t, st in solve(th, sh):
    # Tom's primes
    tp3 = set(x + y for x, y in t)
    # ensure Harry and Tom have different primes
    if len(hp3 | tp3) == 6:
      
      # consider high values for Dick
      for d, _ in solve(set(map_h2l.keys()), sh | st):
        # Dick's primes
        dp3  = set(x + y for x, y in d)
        # we must have nine different primes
        if len(hp3 | tp3 | dp3) == 9:
          print(f"Dick:  {d}\nHarry: {h}\nTom:   {t}")

from itertools import combinations, combinations_with_replacement as cwr

from collections import defaultdict

# the set of one and two digit primes

prms1 = {2, 3, 5, 7}

prms2 = set(x for x in range(11, 100, 2) if all(x % p for p in prms1))

# tuple of two digit semi-primes (using a Python 3.8 assignmemt expression!)

sp = sorted(t for x, y in cwr(prms1| prms2, 2) if 10 <= (t:= x * y) < 100)

# map two digit semi-primes (h > 50) to sets of semi-primes (l < 50)

# that sum with them to give two digit primes

map_h2l = defaultdict(set)

for l, h in combinations(sp, 2):

if l + h in prms2:

map_h2l[h].add(l)

# the sets of higher semi-primes for Harry (odd) and Tom (even)

hh = set(h for h in map_h2l.keys() if h > 50 and (h & 1))

th = set(h for h in map_h2l.keys() if h > 50 and not (h & 1))

# generate triples of different semi-prime pairs from the map (mh2l)

def solve(mh2l, usp=set(), tsp=()):

if len(tsp) == 3:

# return triples of semi-prime pairs and

# the semi-prime set used so far

yield tsp, usp

else:

# try unused high values

for h in mh2l.difference(usp):

# order semi-prime pairs to avoid duplicate solutions

if not tsp or h > tsp[-1][0]:

# try unused low values

for l in map_h2l[h].difference(usp):

yield from solve(mh2l, usp.union((h, l)), tsp + ((h, l),))

# consider high values for Harry

for h, sh in solve(hh):

# form Harry's primes

hp3 = set(x + y for x, y in h)

# consider high values for Tom

for t, st in solve(th, sh):

# Tom's primes

tp3 = set(x + y for x, y in t)

# ensure Harry and Tom have different primes

if len(hp3 | tp3) == 6:

# consider high values for Dick

for d, _ in solve(set(map_h2l.keys()), sh | st):

# Dick's primes

dp3 = set(x + y for x, y in d)

# we must have nine different primes

if len(hp3 | tp3 | dp3) == 9:

print(f"Dick: {d}\nHarry: {h}\nTom: {t}")

New Scientist Enigma 987 – Two Halves Make a Whole

by Richard England

From New Scientist #2142, 11th July 1998

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta