Sunday Times Teaser 2695 – Powers Behind the Thrones

by Nick MacKinnon

I have eight coins minted in different years between 1817 and 1910 inclusive, the most recent being minted in 1902 or later.

The year for one coin is a perfect square and the product of the years for all coins is a perfect cube.

What are the years for the eight coins (in increasing order)?

One Comment Leave one →

brian gladman permalink


from collections import defaultdict
from number_theory import factor

# The year that is a perfect square is 1849 = 43^2. We need another
# 43 to make a product that is a cube and the only other year with
# 43 as a factor is 1892 = 2^2.11.43. These are hence two of the 
# eight coins. In the years from 1817 to 1911, all primes above 43
# occur less than three times so these cannot be factors of the
# years on the coins. For the most recent year (1902 to 1910) this
# leaves only 1904.  So three of the eight coins are:
#
#      1849 = 43^2,   1892 = 2^2.11.43,   1904 = 2^4.7.17
#
# So two of the remaining five coins must have 11 and 17 as factors

yrs3 = (1849, 1892, 1904)

# for each prime, find its power in the product of all years
# in the range 1817 to 1910 inclusive
d = defaultdict(int)
# map years to their prime factors as (prime, exponent)
f = defaultdict(tuple)
for y in range(1817, 1911):
  f[y] = t = tuple(factor(y))
  for p, e in t:
    d[p] += e

# remove any primes that occur less than three times overall
for p in list(d.keys()):
  if d[p] < 3:
    del d[p]
# remove any years that have factors that are not in the
# list of primes that remain
sp = set(d.keys())
for y in range(1817, 1911):
  sy = set(p for p, e in f[y])
  if not (sp & sy):
      del f[y]

# recursive solver
#
# years  --  years for coins so far
# prf    --  dictionary giving the exponent for each prime 
#            in the product so far
# f      --  dictionary of the prime factors for each year
def sol(years, prf, f):
  if len(years) == 8:
    # is the product a perfect cube?
    if all(e % 3 == 0 for e in prf.values()):
      # if so, output the years
      yield tuple(sorted(years))
  else:
    # add another year (in ascending order)
    lo = 1817 if len(years) == 5 else years[-1]
    for y in (set(range(lo + 1, 1904)) & set(f)) - set(years):
      prc = prf.copy()
      for p, e in f[y]:
        prc[p] += e
      yield from sol(years + (y,), prc, f)

soln = set()
for y1 in f:
  # one of the five remaining years must have 11 as a factor
  if y1 in yrs3 or 11 not in (p for p, e in f[y1]):
    continue
  for y2 in f:
    # another must have 17 as a factor
    if y2 in yrs3 + (y1,) or 17 not in (p for p, e in f[y2]):
      continue
    # find the cumulative prime factors for these five primes
    yrs5 = yrs3 + (y1, y2)
    dp = defaultdict(int)
    for y in yrs5:
      for p, e in f[y]:
        dp[p] += e
    # solve for the three remaining years
    for s in sol(yrs5, dp, f):
      soln.add(s)
      
for s in soln:
  print(s)

from collections import defaultdict

from number_theory import factor

# The year that is a perfect square is 1849 = 43^2. We need another

# 43 to make a product that is a cube and the only other year with

# 43 as a factor is 1892 = 2^2.11.43. These are hence two of the

# eight coins. In the years from 1817 to 1911, all primes above 43

# occur less than three times so these cannot be factors of the

# years on the coins. For the most recent year (1902 to 1910) this

# leaves only 1904. So three of the eight coins are:

# 1849 = 43^2, 1892 = 2^2.11.43, 1904 = 2^4.7.17

# So two of the remaining five coins must have 11 and 17 as factors

yrs3 = (1849, 1892, 1904)

# for each prime, find its power in the product of all years

# in the range 1817 to 1910 inclusive

d = defaultdict(int)

# map years to their prime factors as (prime, exponent)

f = defaultdict(tuple)

for y in range(1817, 1911):

f[y] = t = tuple(factor(y))

for p, e in t:

d[p] += e

# remove any primes that occur less than three times overall

for p in list(d.keys()):

if d[p] < 3:

del d[p]

# remove any years that have factors that are not in the

# list of primes that remain

sp = set(d.keys())

for y in range(1817, 1911):

sy = set(p for p, e in f[y])

if not (sp & sy):

del f[y]

# recursive solver

# years -- years for coins so far

# prf -- dictionary giving the exponent for each prime

# in the product so far

# f -- dictionary of the prime factors for each year

def sol(years, prf, f):

if len(years) == 8:

# is the product a perfect cube?

if all(e % 3 == 0 for e in prf.values()):

# if so, output the years

yield tuple(sorted(years))

else:

# add another year (in ascending order)

lo = 1817 if len(years) == 5 else years[-1]

for y in (set(range(lo + 1, 1904)) & set(f)) - set(years):

prc = prf.copy()

for p, e in f[y]:

prc[p] += e

yield from sol(years + (y,), prc, f)

soln = set()

for y1 in f:

# one of the five remaining years must have 11 as a factor

if y1 in yrs3 or 11 not in (p for p, e in f[y1]):

continue

for y2 in f:

# another must have 17 as a factor

if y2 in yrs3 + (y1,) or 17 not in (p for p, e in f[y2]):

continue

# find the cumulative prime factors for these five primes

yrs5 = yrs3 + (y1, y2)

dp = defaultdict(int)

for y in yrs5:

for p, e in f[y]:

dp[p] += e

# solve for the three remaining years

for s in sol(yrs5, dp, f):

soln.add(s)

for s in soln:

print(s)

Sunday Times Teaser 2695 – Powers Behind the Thrones

by Nick MacKinnon

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta