Sunday Times Teaser 3003 – All That Glitters

by Nick MacKinnon

Published Sunday April 12 2020 (link)

My aunt has a collection of sovereigns, and she set me a challenge. “You can have the coins if you can work out the dates, which (in increasing order) are equally spaced and all in the 20th century. The number of coins is an odd prime. The highest common factor of each pair of dates is an odd prime. The sum of the number of factors of each of the dates (including 1 and the date itself) is an odd prime.” I worked out the dates, though the gift was much less valuable than I’d hoped.

What were the dates?

3 Comments Leave one →

Brian Gladman permalink

Using my number theory library (recently updated).


from itertools import combinations
from number_theory import Primes, gcd as hcf, tau

# the set of odd primes less than 2000
pr_set = Primes().set(3, 2000)

# consider the lowest and highest dated sovereigns
for y_lo, y_hi in combinations(range(1900, 2000), 2):
  
  # their dates must have a highest common factor
  # that is an odd prime
  if hcf(y_lo, y_hi) not in pr_set:
    continue
  
  # consider the number of sovereigns (an odd prime)
  for ns in Primes().range(3):
    # calculate the gap between each of the dates 
    inc, r = divmod(y_hi - y_lo, ns - 1)
    if not inc:
      break
    if not r:
      # the dates for all sovereigns
      dates = tuple(y_lo + i * inc for i in range(ns))
      
      # all pairs of dates have highest common factors that are odd primes
      if not all(hcf(a, b) in pr_set for a, b in combinations(dates, 2)):
        continue
      
      # the sum of the numbers of divisors for the dates is an odd prime
      if sum(tau(y) for y in dates) in pr_set:
        f, s, l = ', '.join(f"{x}" for x in dates).rpartition(', ')
        print(f"The dates were {f} and {l}.")

from itertools import combinations

from number_theory import Primes, gcd as hcf, tau

# the set of odd primes less than 2000

pr_set = Primes().set(3, 2000)

# consider the lowest and highest dated sovereigns

for y_lo, y_hi in combinations(range(1900, 2000), 2):

# their dates must have a highest common factor

# that is an odd prime

if hcf(y_lo, y_hi) not in pr_set:

continue

# consider the number of sovereigns (an odd prime)

for ns in Primes().range(3):

# calculate the gap between each of the dates

inc, r = divmod(y_hi - y_lo, ns - 1)

if not inc:

break

if not r:

# the dates for all sovereigns

dates = tuple(y_lo + i * inc for i in range(ns))

# all pairs of dates have highest common factors that are odd primes

if not all(hcf(a, b) in pr_set for a, b in combinations(dates, 2)):

continue

# the sum of the numbers of divisors for the dates is an odd prime

if sum(tau(y) for y in dates) in pr_set:

f, s, l = ', '.join(f"{x}" for x in dates).rpartition(', ')

print(f"The dates were {f} and {l}.")

Tony Smith permalink

Hi Brian

I would be interested to know how you chose the size of pr_set.

When considering the hcf of pairs of dates it is immediately obvious that the maximum possible value is 97.

When considering the sum of tau values it is not immediately obvious that 2000 is an upper bound.

Best wishes
Tony

Reply
- Brian Gladman permalink
  
  Hi Tony, I didn’t do anything sophisticated in choosing 2000 since I didn’t need to. The cost of producing the set is insignificant and the cost of asking if something is in a set in Python doesn’t depend on set size. I knew that 2000 was good for the hcf’s and a small amount of thought convinced me that the sum of the numbers of factors would be well below this maximum (I didn’t do the sum but if all 100 dates were included the sum of the tau values would be 867).
  
  Reply

Sunday Times Teaser 3003 – All That Glitters

by Nick MacKinnon

Published Sunday April 12 2020 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta