Enigmatic Code

Programming Enigma Puzzles

Enigma 987: Two halves make a whole

2 Comments Posted by on 25 October 2019

From New Scientist #2142, 11th July 1998 [link]

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?

[enigma987]

enigma

2 responses to “Enigma 987: Two halves make a whole”

  1. Jim Randell 25 October 2019 at 8:46 am

    Every 2-digit prime is odd. So to construct it from the sum of 2 other numbers requires one of the numbers to odd and the other to be even.

    Each of Harry’s pairs consists of an odd value, greater than 50, and an even value, which must be less than 50.

    Each of Tom’s pairs consists of an even value, greater than 50, and an odd value, which must be less than 50.

    This Python program finds the solution in 130ms.

    Run: [ @repl.it ]

    from collections import defaultdict
from itertools import product
from enigma import Primes, irange, subsets, seq_all_different as all_different, printf

# primes < 100
primes = Primes(100)

# 2-digit semi-primes
semis = list(n for n in irange(10, 99) if len(primes.factor(n)) == 2)

# find pairs of semiprimes that sum to a 2-digit prime (map: larger -> smaller)
pairs = defaultdict(list)
for (a, b) in subsets(semis, size=2):
  p = a + b
  if 9 < p < 100 and p in primes:
    pairs[b].append(a)

# split keys > 50 by parity
k50 = (list(), list())
for k in pairs.keys():
  if k > 50:
    k50[k % 2].append(k)

# choose values for specified keys
values = lambda ks: product(*(pairs[k] for k in ks))

# choose three keys with parity 0 for Tom
for Tk in subsets(k50[0], size=3):
  # and for each key choose a value
  for Tv in values(Tk):
    if not all_different(Tv): continue

    # choose three keys with parity 1 for Harry
    for Hk in subsets(k50[1], size=3):
      # and for each key choose a value
      for Hv in values(Hk):
        if not all_different(Hv + Tv): continue
        # and all totals are different
        if not all_different(k + v for (k, v) in zip(Tk + Hk, Tv + Hv)): continue

        # choose three unused keys for Dick
        for Dk in subsets(pairs.keys(), size=3):
          if not all_different(Tk + Tv + Hk + Hv + Dk): continue
          # and for each key choose a value
          for Dv in values(Dk):
            # all semi-primes are different
            if not all_different(Tk + Tv + Hk + Hv + Dk + Dv): continue
            # all primes are different
            if not all_different(k + v for (k, v) in zip(Tk + Hk + Dk, Tv + Hv + Dv)): continue

            printf("D={Dk}+{Dv} [T={Tk}+{Tv} H={Hk}+{Hv}]")

    Solution: The setters pairs are: 25 + 34 (= 59), 26 + 35 (= 61), 33 + 38 (= 71).

    There is only one solution.

    Harry’s pairs are:

    10 + 57 = 67
    22 + 51 = 73
    14 + 65 = 79

    Each odd valued semi-prime is greater than 50.

    Tom’s pairs are:

    21 + 62 = 83
    15 + 74 = 89
    39 + 58 = 97

    Each even valued semi-prime is greater than 50.

    Dick’s pairs are:

    25 + 34 = 59
    26 + 35 = 61
    33 + 38 = 71

    Reply
  2. GeoffR 25 October 2019 at 5:13 pm 
    % A Solution in MiniZinc
include "globals.mzn";

% Harry's 2-digit odd semi-primes and primes
var 10..95: H1; var 10..95: H2; var 10..95: H3;
var 10..95: H4; var 10..95: H5; var 10..95: H6;
var 11..97: HP1; var 11..97: HP2; var 11..97: HP3;

% Tom's 2-digit even semi-primes and primes
var 10..95: T1; var 10..95: T2; var 10..95: T3;
var 10..95: T4; var 10..95: T5; var 10..95: T6;
var 11..97: TP1; var 11..97: TP2; var 11..97: TP3;

% My 2-digit semi-primes and primes
var 10..97: M1; var 10..97: M2; var 10..97: M3;
var 10..97: M4; var 10..97: M5; var 10..97: M6;
var 11..97: MP1; var 11..97: MP2; var 11..97: MP3;

constraint all_different ([H1 ,H2, H3, H4, H5, H6,
T1, T2, T3, T4, T5 ,T6, M1, M2, M3, M4, M5, M6]);

constraint all_different([HP1 ,HP2, HP3,
TP1 ,TP2, TP3, MP1, MP2, MP3]);

% Set of primes up to 97
set of int: primes = {2} union (2..97 diff { i | i in 2..97, 
j in 2..ceil(sqrt(i)) where i mod j = 0});
                     
% Set of semi-primes up to 97
set of int: semi_primes = {i * j | i in primes, 
j in primes where i * j <= 97};

% Harry's semi-primes and primes - odd semi-primes > 50
constraint H1 + H2 == HP1 /\ H1 in semi_primes 
/\ H2 in semi_primes /\ HP1 in primes;

constraint H1 mod 2 == 1 /\ H2 mod 2 == 0 /\ H1 > 50; 

constraint H3 + H4 == HP2 /\ H3 in semi_primes 
/\ H4 in semi_primes /\ HP2 in primes;

constraint H3 mod 2 == 1 /\ H4 mod 2 == 0 /\ H3 > 50; 

constraint H5 + H6 == HP3 /\ H5 in semi_primes 
/\ H6 in semi_primes /\ HP3 in primes;

constraint H5 mod 2 == 1 /\ H6 mod 2 == 0 /\ H5 > 50; 

% Tom's semi_primes and primes - even semi primes > 50
constraint T1 + T2 == TP1 /\ T1 in semi_primes 
/\ T2 in semi_primes /\ TP1 in primes;

constraint T1 mod 2 == 1 /\ T2 mod 2 == 0 /\ T2 > 50;

constraint T3 + T4 == TP2 /\ T3 in semi_primes 
/\ T4 in semi_primes /\ TP2 in primes;

constraint T3 mod 2 == 1 /\ T4 mod 2 == 0 /\ T4 > 50;

constraint T5 + T6 == TP3 /\ T5 in semi_primes 
/\ T6 in semi_primes /\ TP3 in primes;

constraint T5 mod 2 == 1 /\ T6 mod 2 == 0 /\ T6 > 50;

% My semi-primes and primes
constraint M1 + M2 == MP1 /\ M1 in semi_primes 
/\ M2 in semi_primes /\ MP1 in primes;

constraint M3 + M4 == MP2 /\ M3 in semi_primes 
/\ M4 in semi_primes /\ MP2 in primes;

constraint M5 + M6 == MP3 /\ M5 in semi_primes 
/\ M6 in semi_primes /\ MP3 in primes;

solve satisfy;

output [ "Harrys numbers\n"] 
++  [show(H1) ++ " + " ++ show(H2) ++ " = " ++ show(HP1)] 
++ [ "\n" ++ show(H3) ++ " + " ++ show(H4) ++ " = " ++ show(HP2)] 
++ [ "\n"  ++ show(H5) ++ " + " ++ show(H6) ++ " = " ++ show(HP3)]
++ ["\nTom's numbers"]
++ [ "\n"  ++ show(T1) ++ " + " ++ show(T2) ++ " = " ++ show(TP1)]
++ [ "\n"  ++ show(T3) ++ " + " ++ show(T4) ++ " = " ++ show(TP2)]
++ [ "\n"  ++ show(T5) ++ " + " ++ show(T6) ++ " = " ++ show(TP3)]
++ ["\nMy numbers"]
++ [ "\n"  ++ show(M1) ++ " + " ++ show(M2) ++ " = " ++ show(MP1)]
++ [ "\n"  ++ show(M3) ++ " + " ++ show(M4) ++ " = " ++ show(MP2)]
++ [ "\n"  ++ show(M5) ++ " + " ++ show(M6) ++ " = " ++ show(MP3)];

% Harrys numbers
% 51 + 22 = 73
% 65 + 14 = 79
% 57 + 10 = 67
% Tom's numbers
% 15 + 74 = 89
% 21 + 62 = 83
% 39 + 58 = 97
% My numbers
% 35 + 26 = 61
% 34 + 25 = 59
% 38 + 33 = 71
% ----------
% Finished in 460msec
    Reply

Leave a Comment

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