Enigmatic Code

Programming Enigma Puzzles

Enigma 1186: Always or never a semi-prime

From New Scientist #2342, 11th May 2002

At snooker a player scores 1 point for potting one of the 15 red balls, but 2, 3, 4, 5, 6 or 7 points for potting one of the 6 “colours”.

Whyte potted his first red, then his first colour, then his second red, then his second colour, and so on until he had potted all 15 reds, each followed by a colour. Since the colours are at this stage always put back on the table after being potted, the same colour can be potted repeatedly.

After Whyte had potted each of the 15 colours his cumulative score called by the referee was always a semi-prime. A semi-prime is the product of two prime numbers; the square of a prime number counts as a semi-prime.

After potting the 15 reds and 15 colours a player tries to pot (in this order) the balls scoring 2, 3, 4, 5, 6 and 7 points. Whyte did so to complete a total “clearance”, but his cumulative score after each of those six pots was never a semi-prime.

What was his final score?

Thanks to Hugh Casement for providing a complete transcript for this puzzle.

[enigma1186]

Advertisements

4 responses to “Enigma 1186: Always or never a semi-prime

  1. Jim Randell 4 January 2016 at 7:57 am

    This Python 3 program runs in 190ms.

    from enigma import factor, cached, printf
    
    # points for the coloured balls
    colours = (2, 3, 4, 5, 6, 7)
    
    # semi-prime check (for positive integers)
    @cached
    def is_semi_prime(n):
      return len(factor(n)) == 2
    
    # pot the reds
    def solve(s, t):
      # are we done? (have we potted 15 pairs of balls)
      if len(s) == 30:
        yield (s, t)
      else:
        # pot a red and choose a colour to go with it
        for c in colours:
          t1 = t + c + 1
          if is_semi_prime(t1):
            yield from solve(s + [1, c], t1)
    
    # start with the reds
    for (s, t) in solve([], 0):
      # now pot the colours in order
      for c in colours:
        t += c
        if is_semi_prime(t): break
      else:
        # loop was not exited via break
        printf("final score = {t}, {s} + {colours}", s=tuple(s))
    

    Solution: Whyte’s final score was 114.

    There are many ways (1848) to achieve a final score of 114, here’s one:

    1. red (1) + green (3), total = 4 (2×2)
    2. red (1) + brown (4), total = 9 (3×3)
    3. red (1) + brown (4), total = 14 (2×7)
    4. red (1) + pink (6), total = 21 (3×7)
    5. red (1) + green (3), total = 25 (5×5)
    6. red (1) + black (7), total = 33 (3×11)
    7. red (1) + brown (4), total = 38 (2×19)
    8. red (1) + black (7), total = 46 (2×23)
    9. red (1) + yellow (2), total = 49 (7×7)
    10. red (1) + blue (5), total = 55 (5×11)
    11. red (1) + pink (6), total = 62 (2×31)
    12. red (1) + pink (6), total = 69 (3×23)
    13. red (1) + brown (4), total = 74 (2×37)
    14. red (1) + black (7), total = 82 (2×41)
    15. red (1) + brown (4), total = 87 (3×29)

    16. yellow (2), total = 89 (prime)
    17. green (3), total = 92 (2×2×23)
    18. brown (4), total = 96 (2×2×2×2×2×3)
    19. blue (5), total = 101 (prime)
    20. pink (6), total = 107 (prime)
    21. black (7), total = 114 (2×3×19)

  2. Brian Gladman 6 January 2016 at 3:12 pm

    Not very different:

    from itertools import accumulate
    from number_theory import factors
    
    # produce a set of semi-primes up to the maximum snooker score
    sp = set(n for n in range(150) if len(list(factors(n))) == 2)
    
    # accumulate scores for the first (red + 'colour') phase
    def cumulative_score(score, no):
      if no == 15:
        # yield score if we have potted 15 pairs
        yield score
      else:
        # consider next cumulative scores that are semi-primes
        # (between the minimum and maximum scores per round)
        for v in range(score + 3, score + 9):
          if v in sp:
            yield from cumulative_score(v, no + 1)
    
    # find the cumulative sums for the final 'colour' phase
    colour_sum = list(accumulate(range(2, 8)))
    
    sol = set()
    # consider the possible scores for the (red + 'colour') phase 
    for score in cumulative_score(0, 0):
      # cumulative scores in the final phase are not semi-primes
      if all(score + v not in sp for v in colour_sum):
        sol.add(score + colour_sum[-1])
    print('His final score was {}.'.format(*sol))
    
  3. Julian Gray 6 January 2016 at 5:40 pm

    Yes, there are only two final scores (114 and 138) that enable the second stage of the game to have all non-semi-prime scores and, of those, 138 requires the first stage to have scores that leap from 95 to 106. A neat pencil-and-paper Enigma.

    • Jim Randell 6 January 2016 at 5:54 pm

      Indeed. Armed with a list of semi-primes we can see that the only possible (semi-prime) scores after the reds are cleared are 87 or 111, as these are the only ones such that adding the colours (2, 3, 4, 5, 6, 7) cumulatively give a sequence of non-semi-primes. These correspond to a final score of 114 and 138 respectively.

      The points for a red + a colour must be one of (3, 4, 5, 6, 7, 8), so, for 111, the only possible score before the last red + colour must be 106 (= 111 − 5), and there are no possibilities for the score before that (all of 98 – 103 are semi-prime).

      So the only possible solution is score of 87 after all the reds are potted, giving a total score of 114. And, as my program finds, there are many ways to achieve this.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: