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[0] != fs[1]:
        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[0]].append(s)
      d1[s[1]].append(s)
      d2[s[2]].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[0] in v)
        S1 = list(v for v in vs2 if v != D2 and D2[1] 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.
    All of these sequences start with 77.

    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[0] in t3 and d3[1] 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]}).")
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: