New Scientist Enigma 989 – Prime Progressions

1. 
   Brian Gladman permalink

   Python

   from collections import defaultdict from itertools import count from number_theory import Primes # a set for holding primes pr = set() # a dictionary for holding sequences of primes # in arithmetic progression, indexed on length lts = defaultdict(list) # try progressively increasing primes as the # highest numbers in potential progressions for p in Primes(): pr.add(p) # look for sequences of 5, 6 and 7 primes for ln in (5, 6, 7): # only keep two progressions for each length if len(lts[ln]) == 2: continue # consider an increasing increment for the progression for d in count(2, 2): # and stop if the smallest value is too small p_min = p - (ln - 1) * d if p_min < 3: break # if the smallest value is a prime if p_min in pr: # save the progression if all its values are prime if all(p_min + x * d in pr for x in range(1, ln - 1)): lts[ln].append((p_min, d)) break # stop if we have all the sequences we need if all(len(v) == 2 for v in lts.values()): break # output Harry and Tom's sequences for i in (0, 1): print(f"{['Harry', 'Tom'][i]}'s sequences:") for ln in (5, 6, 7): p, d = lts[ln][i] print(f" {tuple(p + x * d for x in range(ln))}")

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

   from collections import defaultdict from itertools import count from number_theory import Primes   # a set for holding primes pr = set()   # a dictionary for holding sequences of primes # in arithmetic progression, indexed on length lts = defaultdict(list)   # try progressively increasing primes as the # highest numbers in potential progressions for p in Primes():   pr.add(p)      # look for sequences of 5, 6 and 7 primes   for ln in (5, 6, 7):     # only keep two progressions for each length     if len(lts[ln]) == 2:       continue          # consider an increasing increment for the progression     for d in count(2, 2):       # and stop if the smallest value is too small       p_min = p - (ln - 1) * d       if p_min < 3:         break              # if the smallest value is a prime       if p_min in pr:         # save the progression if all its values are prime         if all(p_min + x * d in pr for x in range(1, ln - 1)):           lts[ln].append((p_min, d))           break            # stop if we have all the sequences we need   if all(len(v) == 2 for v in lts.values()):     break   # output Harry and Tom's sequences for i in (0, 1):   print(f"{['Harry', 'Tom'][i]}'s sequences:")   for ln in (5, 6, 7):     p, d = lts[ln][i]     print(f"   {tuple(p + x * d for x in range(ln))}")

Comments are closed.