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 permalink1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283from collections import defaultdictfrom 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 factorsyrs3 = (1849, 1892, 1904)# for each prime, find its power in the product of all years# in the range 1817 to 1910 inclusived = 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 overallfor 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 remainsp = 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 yeardef 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 yearsyield 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] += eyield from sol(years + (y,), prc, f)soln = set()for y1 in f:# one of the five remaining years must have 11 as a factorif y1 in yrs3 or 11 not in (p for p, e in f[y1]):continuefor y2 in f:# another must have 17 as a factorif y2 in yrs3 + (y1,) or 17 not in (p for p, e in f[y2]):continue# find the cumulative prime factors for these five primesyrs5 = yrs3 + (y1, y2)dp = defaultdict(int)for y in yrs5:for p, e in f[y]:dp[p] += e# solve for the three remaining yearsfor s in sol(yrs5, dp, f):soln.add(s)for s in soln:print(s)