Enigmatic Code

Programming Enigma Puzzles

Enigma 1189: Prime performance

From New Scientist #2345, 1st June 2002 [link]

I recently bought a compilation of archive recordings by the Prime Players, issued as a set of three CDs. Each CD has a different playing time of not more than one hour and contains four tracks. Within each CD each track lasts a different prime whole number of minutes, and any combination of three different tracks on that CD lasts a prime whole number of minutes.

For each CD, give its playing time and the length of its longest track.

[enigma1189]

Advertisements

2 responses to “Enigma 1189: Prime performance

  1. Jim Randell 14 December 2015 at 9:39 am

    This Python program runs in 36ms.

    from itertools import combinations
    from collections import defaultdict
    from enigma import Primes, printf
    
    # primes up to 60
    primes = Primes(60)
    
    # record sequences by total sum
    r = defaultdict(list)
    # consider sequences of 4 primes that sum to 60 or less
    for ts in combinations(primes, 4):
      t = sum(ts)
      if t > 60: continue
    
      # check all combinations of size 3 are also prime
      if any(sum(s) not in primes for s in combinations(ts, 3)): continue
    
      r[t].append(ts)
    
    # are there three possible totals?
    ks = r.keys()
    if len(ks) > 2:
      for t in sorted(ks):
        printf("total = {t}")
        for ts in r[t]:
          printf(" {ts}")
    

    Solution: One CD has a total time of 48 minutes, and its longest track is 19 minutes. Another CD has a total time of 54 minutes, and its longest track is 23 minutes. The third CD has a total time of 60 minutes, and its longest track is also 23 minutes.

    There are only three possible CDs:

    5 + 7 + 17 + 19 = 48
    7 + 11 + 13 + 23 = 54
    7 + 13 + 17 + 23 = 60

  2. Brian Gladman 14 December 2015 at 5:24 pm
    from itertools import combinations, product
    from collections import defaultdict
    
    # primes less than 60
    pr = [2, 3, 5, 7]
    pr += [x for x in range(11, 60, 2) if all(x % p for p in pr)]
          
    # collect four different primes with a sum of sixty or less,
    # any three of which also have a sum that is prime
    cd = defaultdict(list)
    for c4 in combinations(pr, 4):
      ln = sum(c4)
      if ln <= 60 and all(ln - x in pr for x in c4):
        cd[ln] += [c4]
    
    # pick three different CD total track lengths
    for k3 in combinations(sorted(cd.keys()), 3):
      # now compose selections of three CDs of these lengths
      for cds in product(*(cd[k] for k in k3)):
        print('The 3 CDs:', *((sum(x), x) for x in cds))

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: